Manytoone Trapdoor Functions and their Relation to PublicKey Cryptosystems
Mihir Bellare,
Shai
Halevi,
Amit Sahai,
and Salil Vadhan
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.,onetoone).
Our first result is somewhat surprising: we show that noninjective trapdoor
functions (with superpolynomial preimage size) can be constructed from
any oneway function (and hence it is unlikely that they suffice for public
key encryption). On the other hand, we show that trapdoor functions with
polynomial preimage size are sufficient for public key encryption. Together,
these two results indicate that the preimage 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 randomoracle model one can
construct injective trapdoor functions from any public key cryptosystem.
Versions

Extended abstract in Advances in Cryptography  CRYPTO '98, number
1462 in Lecture Notes in Computer Science, pp. 283298, Springer, 1998.

Full version on Cryptology ePrint Archive, Record 1998/019.
[compressed
postscript] [postscript]
[ back to
Salil Vadhan's research interests
]