About the Existence of Trapdoors in Cryptosystems

by Giuseppe Persiano

Abstract: In this paper, we present a new attack on secure cryptosystems that is made possible by the presence of trapdoors. 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 devastating.
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]