Paper 1998/019

Many-to-one Trapdoor Functions and their Relation to Public-key Cryptosystems

Mihir Bellare, Shai Halevi, Amit Sahai, and Salil Vadhan


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.

Available format(s)
Publication info
Published elsewhere. Appeared in the THEORY OF CRYPTOGRAPHY LIBRARY and has been included in the ePrint Archive.
One-way functionstrapdoor functionspublic key cryptosystemstrapdoor predicatesencryption.
Contact author(s)
mihir @ cs ucsd edu
1998-06-14: received
Short URL
Creative Commons Attribution


      author = {Mihir Bellare and Shai Halevi and Amit Sahai and Salil Vadhan},
      title = {Many-to-one Trapdoor Functions and their Relation to Public-key Cryptosystems},
      howpublished = {Cryptology ePrint Archive, Paper 1998/019},
      year = {1998},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.