Many-to-one Trapdoor Functions and Their Relation to Public-Key Cryptosystems

DSpace/Manakin Repository

Many-to-one Trapdoor Functions and Their Relation to Public-Key Cryptosystems

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:
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:
Terms of Use: This article is made available under the terms and conditions applicable to Other Posted Material, as set forth at
Citable link to this page:
Downloads of this work:

Show full Dublin Core record

This item appears in the following Collection(s)


Search DASH

Advanced Search