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.
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.
In the first part of this work, Chapter 3 we present new and general constructions of lossy encryption schemes.
The Selective Opening problem is as follows: suppose an adversary receives n commitments (or encryptions) of (possibly) correlated messages, and now the adversary can choose n/2 of the messages, and receive de-commitments (or decryptions and the randomness used to encrypt them). Do the unopened commitments (encryptions) remain secure? A protocol achieving this type of security is called secure against a selective opening adversary (SOA). This question arises naturally in the context of Byzantine Agreement and Secure Multiparty Computation, where an active adversary is able to eavesdrop on all the wires, and then choose a subset of players to corrupt. Unfortunately, the traditional definitions of security (IND-CPA, IND-CCA) do not guarantee security in this setting. In this paper: · We formally define re-randomizable encryption and show that every re-randomizable encryption scheme gives rise to efficient encryptions secure against a selective opening adversary. (Very informally, an encryption is re-randomizable, if given any ciphertext, there is an efficient way to map it to an almost uniform re-encryption of the same underlying message). · We show that statistically-hiding 2-round Oblivious Transfer (OT) implies Lossy Encryption and so do smooth hash proof systems, as defined by Cramer-Shoup. Combining this with known results immediately shows that Private Information Retrieval and homomorphic encryption both imply Lossy Encryption, and thus Selective Opening Secure Public Key Encryption.
In the second part of this work, Chapter 4, we focus on constructing lossy trapdoor functions.
Lossy trapdoor functions (LTDFs) were introduced by Peikert and Waters in STOC '08. Since their introduction, lossy trapdoor functions have found many uses in cryptography. In the work of Peikert and Waters, lossy trapdoor functions were used to give an efficient construction of a chosen-ciphertext secure (IND-CCA2) cryptosystem. Lossy trapdoor functions were then shown to imply deterministic encryption by Boldyreva, Fehr and O'Neill in CRYPTO '08. In TCC '09, Rosen and Segev showed that lossy trapdoor functions are correlated product secure, meaning that they remain one-way even when evaluated on correlated inputs.
In this section we extend the notion of smooth hash proof systems as defined by Cramer and Shoup in Eurocrypt '02, to include an additional homomorphic property. We call this primitive smooth homomorphic hash proof systems . We show that smooth homomorphic projective hash proof systems include all Diverse Group Systems, as defined by Cramer and Shoup. Using this definition, we show that · Smooth homomorphic hash proof systems imply LTDFs. · Diverse group systems as defined in [CS02] imply LTDFs. These are the first known generic constructions of LTDFs. · Applying our generic construction the specific constructions of smooth hash proof systems given by Cramer and Shoup, we obtain the first construction of fully lossy trapdoor functions from the quadratic residuosity (QR) assumption. We also obtain a novel construction of LTDFs from Paillier's decisional composite residuosity (DCR) assumption. · Applying the black-box separation results of Rosen and Segev, we show that there is a black-box separation between smooth homomorphic hash proof systems and one-way trapdoor permutations.
In the third part of this work, Chapter 5, we examine in what situations we can construct lossy trapdoor functions from the seemingly weaker primitive lossy encryption.
Injective one-way trapdoor functions are one of the most fundamental cryptographic primitives. In this section 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 semi-honest oblivious transfer (OT) for strings longer than the sender randomness implies the existence of injective one-way trapdoor functions. This is perhaps surprising 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. (Abstract shortened by UMI.)
Abstract We initiate the study of one-wayness under correlated products. We are interested in identify-ing necessary and sufficient conditions for a function f and a distribution on inputs (x1,..., xk),so that the function ( f (x1),..., f (xk)) is one-way. The main motivation of this study is theconstruction of public-key encryption schemes that are secure against chosen-ciphertext attacks (CCA). We show that any collection of injective trapdoor functions that is secure under a verynatural correlated product can be used to construct a CCA-secure public-key encryption scheme. The construction is simple, black-box, and admits a direct proof of security.We provide evidence that security under correlated products is achievable by demonstrating that lossy trapdoor functions (Peikert and Waters, STOC '08) yield injective trapdoor functionsthat are secure under the above mentioned correlated product. Although we currently base security under correlated products on existing constructions of lossy trapdoor functions, weargue that the former notion is potentially weaker as a general assumption. Specifically, there is no fully-black-box construction of lossy trapdoor functions from trapdoor functions that aresecure under correlated products.
We initiate the study of one-wayness under correlated products. We are interested in identifying necessary and sufficient conditions for a function f and a distribution on inputs (x1,…,xk) so that the function (f(x1),…,f(xk)) is one-way. The main motivation of this study is the construction of public-key encryption schemes that are secure against chosen-ciphertext attacks (CCAs). We show that any collection of injective trapdoor functions that is secure under a very natural correlated product can be used to construct a CCA-secure public-key encryption scheme. The construction is simple, black-box, and admits a direct proof of security. It can be viewed as a simplification of the seminal work of Dolev, Dwork, and Naor [SIAM J. Comput., 30 (2000), pp. 391–437], while relying on a seemingly incomparable assumption. We provide evidence that security under correlated products is achievable by demonstrating that lossy trapdoor functions [Peikert and Waters, Proceedings of the 40th Annual ACM Symposium on Theory of Computing, 2008, pp. 187–196] yield injective trapdoor functions that are secure under the above-mentioned correlated product. Although we currently base security under correlated products on existing constructions of lossy trapdoor functions, we argue that the former notion is potentially weaker as a general assumption. Specifically, there is no fully black-box construction of lossy trapdoor functions from trapdoor functions that are secure under correlated products.
In this paper we study the relationships among some of the most fundamental primitives and protocols in cryptography: public-key encryption (i.e. trapdoor predicates), oblivious transfer (which is equivalent to general secure multi-party computation), key agreement and trapdoor permutations. Our main results show that public-key encryption and oblivious transfer are incomparable under black-box reductions. These separations are tightly matched by our positive results where a restricted (strong) version of one primitive does imply the other primitive. We also show separations between oblivious transfer and key agreement. Finally, we conclude that neither oblivious transfer nor trapdoor predicates imply trapdoor permutations. Our techniques for showing negative results follow the oracle separations of R. Impagliazzo and S. Rudich (1989).
Abstract. Lossy Trapdoor Functions (LTDFs), introduced by Peikert and Waters (STOC 2008) have been useful for building many cryptographic primitives. In particular, by using an LTDF that loses a (1 − 1/ω(log n)) fraction of all its input bits, it is possible to achieve CCA security using the LTDF as a black-box. Unfortunately, not all candidate LTDFs achieve such a high level of lossiness. In this paper we drastically improve upon previous results and show that an LTDF that loses only a non-negligible fraction of a single bit can be used in a black-box way to build numerous cryptographic primitives, including oneway injective trapdoor functions, CPA secure public-key encryption (PKE), and CCA-secure PKE. We then describe a novel technique for constructing such slightly-lossy LTDFs and give a construction based on modular squaring.
We propose a general cryptographic primitive called lossy trapdoor functions (lossy TDFs), and we use it to develop new approaches for constructing several important cryptographic tools, including (injective) trapdoor functions, collision-resistant hash functions, oblivious transfer, and chosen ciphertext-secure cryptosystems (in the standard model). All of these constructions are simple, efficient, and black-box. We realize lossy TDFs based on a variety of cryptographic assumptions, including the hardness of the decisional Diffie–Hellman (DDH) problem and the hardness of the “learning with errors” problem (which is implied by the worst-case hardness of various lattice problems). Taken together, our results resolve some long-standing open problems in cryptography. They give the first injective TDFs based on problems not directly related to integer factorization and provide the first chosen ciphertext-secure cryptosystem based solely on worst-case complexity assumptions.