Many-to-one Trapdoor Functions and Their Relation to Public-Key Cryptosystems
MetadataShow full item record
CitationBellare, Mihi, Shai Halevi, Amit Sahai, and Salil Vadhan. 1998. Many-to-one trapdoor functions and their relation to public-key cryptosystems. In Advances in Cryptology--Proceedings of CRYPTO '98, 18th Annual International Conference, Santa Barbara, California,August 23-27, 1998, ed. Hugo Krawczyk, Berlin: Springer.H. Krawczyk, editor, 283-299. Advances in Cryptology - CRYPTO `98, Lecture Notes in Computer Science 1462. Berlin: Springer.
AbstractThe heart of the task of building public key cryptosystems is viewed as that of "making trapdoors;" in fact, public key cryptosystems and trapdoor functions are often discussed as synonymous. How accurate is this view? In this paper we endeavor to get a better understanding of the nature of "trapdoorness" and its relation to public key cryptosystems, by broadening the scope of the investigation: we look at general trapdoor functions; that is, functions that are not necessarily injective (ie., one-to-one). Our first result is somewhat surprising: we show that non-injective trapdoor functions (with super-polynomial pre-image size) can be constructed from any one-way function (and hence it is unlikely that they suffice for public key encryption). On the other hand, we show that trapdoor functions with polynomial pre-image size are sufficient for public key encryption. Together, these two results indicate that the pre-image size is a fundamental parameter of trapdoor functions. We then turn our attention to the converse, asking what kinds of trapdoor functions can be constructed from public key cryptosystems. We take a first step by showing that in the random-oracle model one can construct injective trapdoor functions from any public key cryptosystem.
Citable link to this pagehttp://nrs.harvard.edu/urn-3:HUL.InstRepos:2958490
- FAS Scholarly Articles