We study the relationships among some of the most fundamental
primitives and protocols in cryptography: public-key encryption
(i.e. trapdoor predicates), oblivious transfer (which is equivalent to
general secure multi-party computation), key agreement, trapdoor
functions, and trapdoor permutations. In spite of the importance of
these primitives, only little was known about the relationships among
them. We resolve all the missing relationships, with respect to
black-box reductions. In particular, we show that public-key
encryption and oblivious transfer are incomparable under black-box
reductions. Furthermore, relative to black-box reductions, neither
oblivious transfer nor 1:1 trapdoor functions imply trapdoor
permutations. Finally, we show that there is no black-box reduction
from trapdoor functions to public-key encryption. Our negative
results follow the oracle separation paradigm introduced by
Impagliazzo and Rudich, as well as a new related model of separation.
One way to interpret our results is as an indication that obtaining a
simple and clean view of cryptography is even further beyond our reach
than might have been previously suspected, as the picture of
cryptography is not likely to simplify in some of its most central
concepts. Borrowing from the terminology of Impagliazzo, our results
demonstrate that there are many possible worlds that lie between
Minicrypt
(the world that has only one-way functions and primitives implied by
them)
and Cryptomania (the world that contains trapdoor permutations and the
rich cryptographic possibilities that they offer).
This talk is mostly based on joint work with Y. Gertner, S. Kannan,
and M. Viswanathan (FOCS 2000), and with Yael Gertner (FOCS 2001).
Copyright. All Rights Reserved.