Basic Cryptographic Primitives

Trapdoor Functions and Public-Key Cryptosystems (Crypto '98), by 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 endeavour to get a better understanding of the nature of "trapdoorness" and its relation to public key cryptosytems, by broadening the scope of the investigation: we look at general trapdoor functions (ie.~ones that are not necessarily injective). Our first result is somewhat surprising: we show that (non-injective) trapdoor functions 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 demonstrate that the injectivity condition can be relaxed, by showing that trapdoor functions with polynomial size pre-images are still sufficient for public key encryption. 


We then turn our attention to the converse, and provide some evidence that injective one-way functions are necessary for public key encryption by proving that in the random-oracle model one can construct injective trapdoor functions from public key encryption. However, we demonstrate that proving the same without the random-oracle may be difficult, by showing a failure of a "natural" extension of the proof.