Basic Cryptographic Primitives

In this research 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). The 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 the 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.