dc.contributor.author | Bellare, Mihir | |
dc.contributor.author | Halevi, Shai | |
dc.contributor.author | Sahai, Amit | |
dc.contributor.author | Vadhan, Salil | |
dc.date.accessioned | 2009-05-14T20:30:27Z | |
dc.date.issued | 1998 | |
dc.identifier.citation | Bellare, 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. | en |
dc.identifier.issn | 0302-9743 | en |
dc.identifier.uri | http://nrs.harvard.edu/urn-3:HUL.InstRepos:2958490 | |
dc.description.abstract | The 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. | en |
dc.description.sponsorship | Engineering and Applied Sciences | en |
dc.language.iso | en_US | en |
dc.publisher | Springer | en |
dc.relation.isversionof | http://dx.doi.org/10.1007/BFb0055735 | en |
dash.license | LAA | |
dc.title | Many-to-one Trapdoor Functions and Their Relation to Public-Key Cryptosystems | en |
dc.relation.journal | Lecture Notes in Computer Science | en |
dash.depositing.author | Vadhan, Salil | |
dc.identifier.doi | 10.1007/BFb0055735 | * |
dash.contributor.affiliated | Vadhan, Salil | |