Many-to-one Trapdoor Functions and their Relation to Public-Key Cryptosystems
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.
Extended abstract in Advances in Cryptography - CRYPTO '98, number
1462 in Lecture Notes in Computer Science, pp. 283-298, Springer, 1998.
Full version on Cryptology ePrint Archive, Record 1998/019.
[ back to
Salil Vadhan's research interests