Show simple item record

dc.contributor.authorBellare, Mihir
dc.contributor.authorHalevi, Shai
dc.contributor.authorSahai, Amit
dc.contributor.authorVadhan, Salil
dc.date.accessioned2009-05-14T20:30:27Z
dc.date.issued1998
dc.identifier.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.en
dc.identifier.issn0302-9743en
dc.identifier.urihttp://nrs.harvard.edu/urn-3:HUL.InstRepos:2958490
dc.description.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.en
dc.description.sponsorshipEngineering and Applied Sciencesen
dc.language.isoen_USen
dc.publisherSpringeren
dc.relation.isversionofhttp://dx.doi.org/10.1007/BFb0055735en
dash.licenseLAA
dc.titleMany-to-one Trapdoor Functions and Their Relation to Public-Key Cryptosystemsen
dc.relation.journalLecture Notes in Computer Scienceen
dash.depositing.authorVadhan, Salil
dc.identifier.doi10.1007/BFb0055735*
dash.contributor.affiliatedVadhan, Salil


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record