Abstract. We consider the problem of extending oblivious transfers: Given a small number of oblivious transfers “for free, ” can one implement a large number of oblivious transfers? Beaver has shown how to extend oblivious transfers given a one-way function. However, this protocol is inefficient in practice, in part due to its non-black-box use of the underlying one-way function. We give efficient protocols for extending oblivious transfers in the random oracle model. We also put forward a new cryptographic primitive which can be used to instantiate the random oracle in our constructions. Our methods suggest particularly fast heuristics for oblivious transfer that may be useful in a wide range of applications. 1
Abstract. We consider the problem of extending oblivious transfers: Given a small number of oblivious transfers “for free, ” can one implement a large number of oblivious transfers? Beaver has shown how to extend oblivious transfers given a one-way function. However, this protocol is inefficient in practice, in part due to its non-black-box use of the underlying one-way function. We give efficient protocols for extending oblivious transfers in the random oracle model. We also put forward a new cryptographic primitive which can be used to instantiate the random oracle in our constructions. Our methods suggest particularly fast heuristics for oblivious transfer that may be useful in a wide range of applications. 1
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
In the random oracle model, the parties are given oracle access to a random member of a (typically huge) function family, and are assumed to have unbounded computational power (though they can only make a bounded number of oracle queries). This model provides powerful properties that allow proving the security of many protocols, even such that cannot be proved secure in the standard model (under any hardness assumption). The random oracle model is also used to show that a given cryptographic primitive cannot be used in a black-box way to construct another primitive; in their seminal work, Impagliazzo and Rudich [STOC ’89] showed that in the random function model – when the function family is the set of all functions – it is impossible to construct (secure) key-agreement protocols, yielding that key-agreement cannot be black-box reduced to one-way functions. Their work has a long line of followup works (Simon [EC ’98], Gertner et al. [STOC ’00] and Gennaro et al. [SICOMP ’05], to name a few), showing that given oracle access to a certain type of function family (e.g., the family that “implements ” public-key encryption) is not sufficient for building a given cryptographic primitive (e.g., oblivious transfer). Yet, in the more general sense, the following fundamental question remained open: What is the exact power of the random oracle model, and more specifically, of the random function model? We make progress towards answering the above question, showing that any (no private input) semi-honest two-party functionality that can be securely implemented in the random function model, can be securely implemented information theoretically (where parties are assumed to be all powerful, and no oracle is given). We further generalize the above result to function families that provide some natural combinatorial property. To exhibit the power of our result, we use the recent information theoretic impossibility result of McGregor et al. [FOCS ’10], to show the existence of functionalities (e.g., inner product) that cannot be computed both accurately and in a differentially private manner in the random function model; yielding that protocols for computing these functionalities cannot be black-box reduced to the existence of one-way functions.
Oblivious Transfer has played a crucial role in the design of secure multi party computation. Nevertheless, there are not many practical solutions that achieve simulation based security and at the same time instantiable based on different assumptions. In this work, we consider a simulation based security notion that we call endemic security. We show how to construct highly efficient oblivious transfer in the random oracle model that achieves endemic security under a wide range of assumptions, among them DDH, CDH, LWE and coding based assumptions. We construct a secure oblivious transfer based on DDH that takes only a single communication round which allows significant performance gains. We also instantiate our oblivious transfer with the Crystals.Kyber key agreement. Our implementation shows that both instantiations can be computed in under one millisecond. Further, we revisit, correct and improve existing oblivious transfer extension techniques. We provide an implementation of an oblivious transfer extension protocol in the ideal cipher model that is actively secure, processing up to 23 million OTs per second and up to 10 times faster than previous secure implementations. We also show that our framework can compute endemically secure OT extension and the base OTs in just two rounds.
Oblivious transfer is one of the most basic and important building blocks in cryptography. As such, understanding its cost is of prime importance. Beaver (STOC 1996) showed that it is possible to obtain poly(n) oblivious transfers given only n actual oblivious transfer calls and using one-way functions, where n is the security parameter. In addition, he showed that it is impossible to extend oblivious transfer information theoretically. The notion of extending oblivious transfer is important theoretically (to understand the complexity of computing this primitive) and practically (since oblivious transfers can be expensive and thus extending them using only one-way functions is very attractive). Despite its importance, very little is known about the feasibility of extending oblivious transfer, beyond the fact that it is impossible information theoretically. Specifically, it is not known whether or not one-way functions are actually necessary for extending oblivious transfer, whether or not it is possible to extend oblivious transfers with adaptive security, and whether or not it is possible to extend oblivious transfers when starting with just a few. In this paper, we address these questions and provide almost complete answers to all of them. We show that the existence of any oblivious transfer extension protocol with security for static semihonest adversaries implies one-way functions, that an oblivious transfer extension protocol with adaptive security implies oblivious transfer with static security, and that the existence of an oblivious transfer extension protocol from only O(log n) oblivious transfers implies oblivious transfer itself.
Abstract. We study an adaptive variant of oblivious transfer in which a sender has N messages, of which a receiver can adaptively choose to re-ceive k one-after-the-other, in such a way that (a) the sender learns noth-ing about the receiver’s selections, and (b) the receiver only learns about the k requested messages. We propose two practical protocols for this primitive that achieve a stronger security notion than previous schemes with comparable efficiency. In particular, by requiring full simulatabil-ity for both sender and receiver security, our notion prohibits a subtle selective-failure attack not addressed by the security notions achieved by previous practical schemes. Our first protocol is a very efficient generic construction from unique blind signatures in the random oracle model. The second construction does not assume random oracles, but achieves remarkable efficiency with only a constant number of group elements sent during each transfer. This second construction uses novel techniques for building efficient simulat-able protocols. 1
Injective one-way trapdoor functions are one of the most fundamental cryptographic primitives. In this work we give a novel construction of injective trapdoor functions based on oblivious transfer for long strings. Our main result is to show that any 2-message statistically sender-private semihonest oblivious transfer (OT) for strings longer than the sender randomness implies the existence of injective one-way trapdoor functions. This is perhaps surprising given given the black box separation of injective one-way trapdoor functions from many common cryptographic protocols, e.g. IND-CCA encryption. As a tool for creating injective one-way trapdoor functions, we define a new notion of security for a public key encryption scheme called Randomness Dependent Message (RDM) security, and use it as a stepping stone for creating injective one-way trapdoor functions. Our main result has a number of interesting corollaries: • Applying the results of Mol and Yilek (PKC ’10), we also show that Lossy Encryption with long plaintexts implies correlated product secure functions and INDCCA secure encryption. • Lossy encryption with long plaintexts implies a weak form of RDM security. In addition, Hemenway, Libert, Ostrovsky and Vergnaud (ePrint ’09) showed that statistically-hiding 2-round Oblivious Transfer (OT) is equivalent to Lossy Encryption, where if OT uses randomness shorter than the message so does Lossy Encryption and vice versa. Thus, our main result also implies an injective one-way trapdoor function from any lossy encryption with short randomness. This is somewhat surprising since injective trapdoor functions are deterministic and, given the trapdoor, allow recovery of a complete inverse, while public-key encryptions are probabilistic and recover only the plaintext and not necessarily the randomness used in the encryption process. Our result corroborates the previous result of Bellare, Halevi, Sahai and Vadhan (CRYPTO ’98) showing that IND-CPA secure encryption implies injective one-way trapdoor permutations in the random oracle model. We stress that in our work we do not make use of a random oracle.