In this paper, we present a new attack on
secure cryptosystems that is made possible by the presence of
Roughly speaking, knowledge of a trapdoor allows one to
partially break the security of the cryptosystem. For example,
if the trapdoor relative to a non-malleable cryptosystem
E is revealed then E ceases to be non-malleable but retains
its cpa-security (or even its cca1-security).
The impact of a trapdoor on the security of a protocol can be
We show that known constructions of secure cryptosystems (including the Cramer-Shoup cryptosystem and the general techniques based on NIZK by Naor-Yung, Dolev-Dwork-Naor, and Sahai) give, or can be instantiated to give, cryptosystems prone to this kind of attack. We call such cryptosystems trapdoor cryptosystems. We also introduce the notion of a strong trapdoor cryptosystem.
We leave as an open problem to show the existence of a secure cryptosystem that is not trapdoor or to show that the existence of a trapdoor is an intrinsic drawback of secure cryptosystems.
Status: work in progress.
Availability: [PS], [PDF]