ECCC-Report TR10-127https://eccc.weizmann.ac.il/report/2010/127Comments and Revisions published for TR10-127en-usSun, 07 Nov 2010 17:56:25 +0200
Revision 1
| Building Injective Trapdoor Functions From Oblivious Transfer |
Brett Hemenway,
Rafail Ostrovsky
https://eccc.weizmann.ac.il/report/2010/127#revision1Injective 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 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 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 IND-CCA
secure encryption.
Applying the results of Kiltz, Mohassel and O'Neill (EUROCRYPT '10), we have that Lossy Encryption with long plaintexts implies adaptive trapdoor functions.
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.
Sun, 07 Nov 2010 17:56:25 +0200https://eccc.weizmann.ac.il/report/2010/127#revision1
Paper TR10-127
| Building Injective Trapdoor Functions From Oblivious Transfer |
Brett Hemenway,
Rafail Ostrovsky
https://eccc.weizmann.ac.il/report/2010/127Injective 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 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 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 IND-CCA
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.
Fri, 13 Aug 2010 17:40:12 +0300https://eccc.weizmann.ac.il/report/2010/127