Depending on which parties can be coerced, the security level, the flavor and the number of rounds of the cryptosystem, it is possible to define a number of notions of deniable encryption. In this paper we prove that there does not exist any non-interactive receiver-deniable cryptosystem with better than polynomial security. This also shows that it is impossible to construct a non-interactive bi-deniable public-key encryption scheme with better than polynomial security. Specifically, we give an explicit bound relating the security of the scheme to how efficient the scheme is in terms of key size. Our impossibility result establishes a lower bound on the security. As a final contribution we give constructions of deniable public-key encryption schemes which establishes upper bounds on the security in terms of key length. There is a gap between our lower and upper bounds, which leaves the interesting open problem of finding the tight bounds.
Category / Keywords: public-key cryptography / deniable encryption Publication Info: Full version of an ASIACRYPT 2011 paper. Date: received 25 Jan 2011, last revised 13 Sep 2011 Contact author: jbn at cs au dk Available format(s): PDF | BibTeX Citation Version: 20110913:121655 (All versions of this report) Short URL: ia.cr/2011/046 Discussion forum: Show discussion | Start new discussion