Oblivious Transfer (OT) protocol is nowadays recognised as a generic primitive for all cryptographic protocols since it is one of the strongest primitives for secure multiparty computation (MPC). To design hardware-assisted OT protocols, Physically Unclonable Functions (PUFs) have been thoroughly studied in the literature. PUF-based OT protocols, however, necessitate the physical transfer of PUF devices, rendering them inappropriate in situations where the physical transfer of devices is not secure. Additionally, two-party secure computation protocols, in general, are performed between two distrusting parties. Yet, the PUF-based OT protocols require the PUF receiver to trust the PUF sender to behave honestly. Recent works have considered malicious PUF models resulting in more complex protocols. To avoid these drawbacks, we in this work rely on the concept of Physically Related Functions (PReFs), a pair of PUF devices that allow two PUF devices to generate similar responses over a "related" input set. XOR composition of PReFs, also called XOR_PReF, is an improved construction that eliminates the need for any trusted party and generates a "related" input set securely and independently. With the help of this new primitive, we propose 1-out-of-2 OT protocols using XOR_PReF in semi-honest as well as malicious settings keeping the protocol secure even after switching the roles of OT-sender and OT-receiver. Our protocols can be integrated into hardware-assisted MPC protocols and provide a safe and valuable solution for all OT-based techniques, notably Private Set Intersection (PSI), Private Information Retrieval (PIR), and Password Authenticated Key Exchange (PAKE).
Oblivious Transfer (OT) protocol is nowadays recognised as a generic primitive for all cryptographic protocols since it is one of the strongest primitives for secure multiparty computation (MPC). To design hardware-assisted OT protocols, Physically Unclonable Functions (PUFs) have been thoroughly studied in the literature. PUF-based OT protocols, however, necessitate the physical transfer of PUF devices, rendering them inappropriate in situations where the physical transfer of devices is not secure. Additionally, two-party secure computation protocols, in general, are performed between two distrusting parties. Yet, the PUF-based OT protocols require the PUF receiver to trust the PUF sender to behave honestly. Recent works have considered malicious PUF models resulting in more complex protocols. To avoid these drawbacks, we in this work rely on the concept of Physically Related Functions (PReFs), a pair of PUF devices that allow two PUF devices to generate similar responses over a "related" input set. XOR composition of PReFs, also called XOR_PReF, is an improved construction that eliminates the need for any trusted party and generates a "related" input set securely and independently. With the help of this new primitive, we propose 1-out-of-2 OT protocols using XOR_PReF in semi-honest as well as malicious settings keeping the protocol secure even after switching the roles of OT-sender and OT-receiver. Our protocols can be integrated into hardware-assisted MPC protocols and provide a safe and valuable solution for all OT-based techniques, notably Private Set Intersection (PSI), Private Information Retrieval (PIR), and Password Authenticated Key Exchange (PAKE).
Oblivious transfer (OT) protocol is an essential tool in cryptography that provides a wide range of applications such as secure multi-party computation, private information retrieval, private set intersection, contract signing, and privacy-preserving location-based services. The OT protocol has different variants such as one-out-of-2, one-out-of- n , k -out-of- n , and OT extension. In the OT (one-out-of-2, one-out-of- n , and OT extension) protocol, the sender has a set of messages, whereas the receiver has a key. The receiver sends that key to the sender in a secure way; the sender cannot get any information about the received key. The sender encrypts every message by operating on every message using the received key and sends all the encrypted messages to the receiver. The receiver is able to extract only the required message using his key. However, in the k -out-of- n OT protocol, the receiver sends a set of k keys to the sender, and in replay, the sender sends all the encrypted messages. The receiver uses his keys and extracts the required messages, but it cannot gain any information about the messages that it has not requested. Generally, the OT protocol requires high communication and computation cost if we transfer millions of oblivious messages. The OT extension protocol provides a solution for this, where the receiver transfers a set of keys to the sender by executing a few numbers of OT protocols. Then, the sender encrypts all the messages using cheap symmetric key cryptography with the help of a received set of keys and transfers millions of oblivious messages to the receiver. In this work, we present different variants of OT protocols such as one-out-of-2, one-out-of- n , k -out-of- n , and OT extension. Furthermore, we cover various aspects of theoretical security guarantees such as semi-honest and malicious adversaries, universally composable, used techniques, computation, and communication efficiency aspects. From the analysis, we found that the semi-honest adversary-based OT protocols required low communication and computation costs as compared to malicious adversary-based OT protocols.
Commitment schemes are one of the basic building blocks to construct secure protocols for multi party computation. Many recent works are exploring hardware primitives like physically unclonable functions to build keyless cryptographic protocols, with minimal assumptions. The asymmetric nature and non-invertibility property of PUFs are widely exploited to build oblivious transfer protocols that are extended to build bit-commitment schemes. However, these schemes require the physical transfer of the PUF device between the interacting parties. In this work, we introduce a new class of hardware-based primitives called physically related functions that enable hardware circuits to securely communicate with each other over insecure channels. We propose a bit-commitment protocol based on this hardware primitive without needing any physical transfer. Our scheme is statistically hiding and computationally binding, requiring only one round of communication while being practically deployable. We explore the security properties of physically related functions, under which we prove the security of our scheme. We experimentally show that it is impossible to break the security of the scheme with more than negligible probability.
Secure two-party computation allows two parties to evaluate a function on their private inputs while keeping all information private except what can be inferred from the outputs. A major building block and the foundation for many efficient secure computation protocols is oblivious transfer (OT). In an OT protocol a sender inputs two messages (x_{0}, x_{1}) while a receiver with choice bit c wants to receive message x_{c}.The OT protocol execution guarantees that the sender learns no information about c and the receiver learns no information about x_{1−c}. This thesis focuses on the efficient generation of OTs and their use in secure computation. In particular, we show how to compute OTs more efficiently, improve generic secure computation protocols which can be used to securely evaluate any functionality, and develop highly efficient special-purpose protocols for private set intersection (PSI). We outline our contributions in more detail next. More Efficient OT Extensions. The most efficient OT protocols are based on public-key cryptography and require a constant number of exponentiations per OT. However, for many practical applications where millions to billions of OTs need to be computed, these exponentiations become prohibitively slow. To enable these applications, OT extension protocols [Bea96, IKNP03] can be used, which extend a small number of public-key-based OTs to an arbitrarily large number using cheap symmetric-key cryptography only. We improve the computation and communication efficiency of OT extension protocols and show how to achieve security against malicious adversaries, which can arbitrarily deviate from the protocol, at low overhead. Our resulting protocols can compute several million of OTs per second and we show that, in contrast to previous belief, the local computation overhead for computing OTs is so low that the main bottleneck is the network bandwidth. Parts of these results are published in: • G. Asharov, Y. Lindell, T. Schneider, M. Zohner. More Efficient Oblivious Transfer and Extensions for Faster Secure Computation. In 20th ACM Conference on Computer and Communications Security (CCS’13). • G. Asharov, Y. Lindell, T. Schneider, M. Zohner. More Efficient Oblivious Transfer Extensions with Security for Malicious Adversaries. In 34th Advances in Cryptology – EUROCRYPT’15. • G. Asharov, Y. Lindell, T. Schneider, M. Zohner. More Efficient Oblivious Transfer Extensions. To appear in Journal of Cryptology. Online at http://eprint.iacr.org/2016/602. Communication-Efficient Generic Secure Two-Party Computation. Generic secure two-party computation techniques allow to evaluate a function, represented as a circuit of linear (XOR) and non-linear (AND) gates. One of the most prominent generic secure two-party computation protocols is Yao’s garbled circuits [Yao86], for which many optimizations have been proposed. Shortly after Yao’s protocol, the generic secure protocol by Goldreich-Micali-Wigderson (GMW) [GMW87] was introduced. The GMW protocol requires a large number of OTs and was believed to be less efficient for secure two-party computation than Yao’s protocol [HL10, CHK+12]. We improve the efficiency of the GMW protocol and show that it can outperform Yao’s garbled circuits protocol in settings with low bandwidth. Furthermore, we utilize the flexibility of OT and outline special-purpose constructions that can be used within the GMW protocol and which improve its efficiency even further. Parts of these results are published in: • T. Schneider, M. Zohner. GMW vs. Yao? Efficient Secure Two-Party Computation with Low Depth Circuits. In 17th International Conference on Financial Cryptography and Data Security (FC’13). • D. Demmler, T. Schneider, M. Zohner. ABY - A Framework for Efficient Mixed-Protocol Secure Two-Party Computation. In 22th Network and Distributed System Security Symposium (NDSS’15). • G. Dessouky, F. Koushanfar, A.-R. Sadeghi, T. Schneider, S. Zeitouni, M. Zohner. Pushing the Communication Barrier in Secure Computation using Lookup Tables. In 24th Network and Distributed System Security Symposium (NDSS’17). Faster Private Set Intersection (PSI). PSI allows two parties to compute the intersection of their private sets without revealing any element that is not in the intersection. PSI is a well-studied problem in secure computation and many special-purpose protocols have been proposed. However, existing PSI protocols are several orders of magnitude slower than an insecure naive hashing solution that is used in practice. In addition, many protocols were compared in a biased fashion, which makes it difficult to identify the most promising solution for a particular scenario. We systematize the progress made on PSI protocols by reviewing, optimizing, and comparing existing PSI protocols. We then introduce a novel PSI protocol that is based on our efficiency improvements in OT extension protocols and which outperforms existing protocols by up to two orders of magnitude. Parts of these results are published in: • B. Pinkas, T. Schneider, M. Zohner. Faster Private Set Intersection Based on OT Extension. In 23th USENIX Security Symposium (USENIX Security’14). • B. Pinkas, T. Schneider, G. Segev, M. Zohner. Phasing: Private Set Intersection using Permutation-based Hashing. In 24th USENIX Security Symposium (USENIX Security’15). • B. Pinkas, T. Schneider, M. Zohner. Scalable Private Set Intersection Based on OT Extension. Journal paper. In submission. Online at http://iacr.eprint.org/2016/930.
We investigate the power of physical unclonable functions (PUFs) as a new primitive in cryptographic protocols. Our contributions split into three parts. Firstly, we focus on the realiza bility of PUF-protocols in a special type of stand-alone setting (the “stand-alone, good PUF setting”) under minimal assumptions. We provide new PUF definitions that require only weak average security properties of the PUF, and prove that these definitions suffice to realize secure PUF-based oblivious transfer (OT), bit com mitment (BC) and key exchange (KE) in said setting. Our protocols for OT, BC and KE are partly new, and have certain practicality and security advantages compared to existing schemes. In the second part of the paper, we formally prove that there are very sharp limits on the usability of PUFs for OT and KE beyond the above stand-alone, good PUF scenario. We introduce two new and realistic attack models, the so-called posterior access model (PAM) and the bad PUF model, and prove several impossibility results in these models. First, OT and KE protocols whose security is solely based on PUFs are generally impossible in the PAM. More precisely, one-time access of an adversary to the PUF after the end of a single protocol (sub-)session makes all previous (sub-)sessions provably insecure. Second, OT whose security is solely based on PUFs is impossible in the bad PUF model, even if only a stand alone execution of the protocol is considered (i.e., even if no adversarial PUF access after the protocol is allowed). Our impossibility proofs do not only hold for the weak PUF definition of the first part of the paper, but even apply if ideal rand omness and unpredictability is assumed in the PUF, i.e., if the PUF is modeled as a random permutation oracle. In the third part, we investigate the feasibility of PUF-based bit commitment beyond the stand-alone, good PUF setting. For a number of reasons, this case is more complicated than OT and KE. We first prove that BC is impossible in the bad PUF model if players have got access to the PUF between the commit and the reveal phase. Again, this result holds even if the PUF is “ideal” and modeled as a random permutation oracle. Secondly, we sketch (without proof) two new BC-protocols, which can deal with bad PUFs or with adversarial access between the commit and reveal phase, but not with both. We hope that our results can contribute to a clarification of the usability of PUF s in cryptographic protocols. They show that new hardware properties such as offline certifiability and the erasure of PUF responses would be required in order to make PUFs a broadly applicable cryptographic tool. These features have not yet been realized in practical PUF-implementations and generally seem hard to achieve at low costs. Our findings also show that the question how PUFs can be modeled comprehensively in a UC-setting must be considered at least partly open.
Oblivious transfer (OT) is one of the most fundamental primitives in cryptography and is widely used in protocols for secure two-party and multi-party computation. As secure com-putation becomes more practical, the need for practical large scale oblivious transfer protocols is becoming more evident. Oblivious transfer extensions are protocols that enable a relatively small number of “base-OTs ” to be utilized to compute a very large number of OTs at low cost. In the semi-honest setting, Ishai et al. (CRYPTO 2003) presented an OT extension protocol for which the cost of each OT (beyond the base-OTs) is just a few hash function operations. In the malicious setting, Nielsen et al. (CRYPTO 2012) presented an efficient OT extension protocol for the setting of active adversaries, that is secure in the random oracle model. In this work, we present an OT extension protocol for the setting of malicious adversaries that is more efficient and uses less communication than previous works. In addition, our protocol can be proven secure in both the random oracle model, and in the standard model with a type of correlation robustness. Given the importance of OT in many secure computation protocols, increasing the efficiency of OT extensions is another important step forward to making secure
Oblivious Transfer (OT) is a fundamental cryptographic primitive enabling privacy-preserving computation and constitutes a core building block for secure multi-party computation while supporting a wide range of security-sensitive applications: private information retrieval, zero-knowledge proofs, and password-authenticated key exchange, to cite a few. While recent advances in OT extension have significantly reduced amortised costs, their reliance on batches of random base OTs and substantial pre-computation phases limits their practicality in scenarios where the number of transfers is modest or where communication latency and client-side computation are critical constraints. In such settings, efficient base OT protocols remain both relevant and necessary. In this work, we introduce I-(OT)2, a novel base 1-out-of-2 OT protocol grounded in the quadratic residuosity problem, specifically designed to minimise receiver-side computation and interaction. Our construction is particularly appealing on client--server architectures in which the receiver operates on low-power hardware, such as Internet of Things (IoT) devices. Through a lightweight offline pre-computation phase, I-(OT)2 shifts the on-transfer computational burden almost entirely to the Sender, while reducing online communication to only six messages and four digests exchanged. We provide a detailed description of the protocol, accompanied by a formal proof of its security. Moreover, to demonstrate the viability of I-(OT)2, we also present an open-source proof-of-concept implementation (in C language) evaluated on real IoT hardware. Results are staggering: for 128-bit security using a 3072-bit RSA modulus, the receiver incurs an average online cost per OT as low as 2.80 μs on desktop platforms and 39.90 μs on IoT devices, more than 10× faster than the well known SimplestOT.