Download Full Text

Citable link to this page

. . . . . .

Title:	Many-to-one Trapdoor Functions and Their Relation to Public-Key Cryptosystems
Author:	Sahai, Amit; Bellare, Mihir; Halevi, Shai; Vadhan, Salil Note: Order does not necessarily reflect citation order of authors.
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.
Full Text & Related Files:	Vadhan_TrapdoorCryptosystems.pdf (346.0Kb; PDF)
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.
Published Version:	http://dx.doi.org/10.1007/BFb0055735
Terms of Use:	This article is made available under the terms and conditions applicable to Other Posted Material, as set forth at http://nrs.harvard.edu/urn-3:HUL.InstRepos:dash.current.terms-of-use#LAA
Citable link to this page:	http://nrs.harvard.edu/urn-3:HUL.InstRepos:2958490

Show full Dublin Core record

This item appears in the following Collection(s)

• FAS Scholarly Articles [5133]
  Peer reviewed scholarly articles from the Faculty of Arts and Sciences of Harvard University

Contact administrator regarding this item (to report mistakes or request changes)