We describe efficient constructions for two oblivious twoparty computation problems: l-out-of-N Oblivious Transfer &d 'Oblivious Poly&nial Evaluation.The oblivious polynomial evaluation protocol is based on a new intractability assumption which is closely related to noisy polynomial re construction.A direct corollary of the l-out-of-N OT protccol is an efficient transformation of any Private Information Retrieval (PIR) protocol to a Symmetric PIR (SPIR) prc-tow1 without increasing the number of databases.The new construction for l-out-of-N OT is highly efficient -it requires only log N executions of a l-out-of-2 OT protocol.We also present a construction for k-out-of-N OT which is more efficient than k repetitions of l-out-of-N OT.The efficiency of the new OT protocols makes them useful for a variety of applications.These include oblivious sampling which can be used to securely compare the sizes of web search engines, protocols for privately solving the list intersection problem and for mutually authenticated key exchange based on (possibly weak) passwords, and protocols for anonymity preserving web usage metering.
We describe efficient constructions for two oblivious twoparty computation problems: l-out-of-N Oblivious Transfer &d 'Oblivious Poly&nial Evaluation.The oblivious polynomial evaluation protocol is based on a new intractability assumption which is closely related to noisy polynomial re construction.A direct corollary of the l-out-of-N OT protccol is an efficient transformation of any Private Information Retrieval (PIR) protocol to a Symmetric PIR (SPIR) prc-tow1 without increasing the number of databases.The new construction for l-out-of-N OT is highly efficient -it requires only log N executions of a l-out-of-2 OT protocol.We also present a construction for k-out-of-N OT which is more efficient than k repetitions of l-out-of-N OT.The efficiency of the new OT protocols makes them useful for a variety of applications.These include oblivious sampling which can be used to securely compare the sizes of web search engines, protocols for privately solving the list intersection problem and for mutually authenticated key exchange based on (possibly weak) passwords, and protocols for anonymity preserving web usage metering.
Abstract—Oblivious polynomial evaluation is a protocol involving two parties, a sender whose input is a polynomial P, and a receiver whose input is a value x. At the end of the protocol, the receiver learns P (x) and nothing more about P, while the sender remains oblivious of both x and P (x). It is used as a primitive in many applications including protocols for private comparison of data, for mutually authenticated key exchange based on (possibly weak) passwords, and for anonymous coupons. In this paper, we describe a novel unconditionally secure oblivious polynomial evaluation protocol. Keywords—Multi-Party Computation, Oblivious Transfer, Oblivious Polynomial Evaluation.
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.
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.
In this paper, we present a new application for , n 1 oblivious transfer, which i s a n i n teractive protocol between two parties Alice and Bob, where Alice has n secrets and Bob has a query i.A t the end of the protocol Bob has the ith secret and no other information about Alice's other secrets, while Alice does not get any information about i.This new application is the Secure Database Access problem.Motivated by this application, we propose an OT scheme which a c hieves low communication complexity and information theoretic security.We use a distributed model for , n 1 oblivious transfer, where Bob interacts with multiple \Alices".In this model, we base our scheme on any PIR scheme, which i s a s c heme where only the privacy of Bob is considered, and use it to construct an OT scheme, private for both parties, without paying too much i n communication complexity.This results in the rst sublinear information theoretic scheme for , n 1 OT.Further motivated by the application of , n 1 OT for polynomial n, w e raise the issue of repetition in , n 1 OT, where both security and eciency are important.We show that previous protocols for , n 1 oblivious transfer fail in this setting.
The problem of two-party oblivious polynomial evaluation(OPE)is studied,where one party(Alice)has a polynomial P(x)and the other party(Bob)with an input x wants to learn P(x)in such an oblivious way that Bob obtains P(x)without learning any additional information about P except what is implied by P(x)and Alice does not know Bob's input x.The former OPE protocols are based on an intractability assumption except for OT protocols.In fact,evaluating P(x)is equivalent to computing the product of the coefficient vectors(a0,...,an)and(1,...,xn).Using this idea,an efficient scale product protocol of two vectors is proposed first and then two OPE protocols are presented which do not need any other cryptographic assumption except for OT protocol.Compared with the existing OPE protocol,another characteristic of the proposed protocols is the degree of the polynomial is private.Another OPE protocol works in case of existence of untrusted third party.
We develop a new multi-party generalization of Naor-Nissim indirect indexing, making it possible for many participants to simulate a RAM machine with only poly-logarithmic blow-up. Underlying our approach is a new multi-party variant of oblivious transfer which may be of independent interest. Our most efficient instantiation (built from length-flexible additively homomorphic public key encryption) improves the communication complexity of secure multi-party computation for a number of problems in the literature. We explore, in depth, some of these applications, including private distributed constraint satisfaction problems, private stable bipartite matching, and private longest common subsequence.
In the case of the private bipartite stable matching (stable marriage) problem, we follow-up the work of Golle (Financial Crypto 2006) who motivates the application and introduces a novel framework for the solving the problem. We show that the communication complexity of Golle’s main protocol is substantially greater than what was claimed, in part due to surprising pathological behavior of Golle’s variant of the Gale-Shapley stable matching algorithm. We develop new secure protocols in Golle’s basic framework with greatly reduced communication complexity.
In the case of the longest common subsequence problem, we design communication efficient two-party and multi-party protocols for several variants of this and related problems. Our protocols achieve the first improvement to the communication complexity for this application over generic results (such as Yao’s garbled circuit protocol). As such, this result is interesting as a contribution to the theory of communication efficiency for secure two-party and multi-party applications. We benefit from the felicitous interplay of an efficient block-retrieval PIR (Gentry-Ramzan, ICALP 2005) with the classic “four Russians” algorithmic design. We believe this technique will be useful for privately implementing a variety of “efficiently encodable” dynamic programming applications.