Cryptology ePrint Archive: Report 2011/144

Deniable Encryption from the McEliece Assumptions

Bernardo M. David and Anderson C. A. Nascimento

Abstract: The first construction of sender-deniable encryption with negligible detection probability and a single encryption scheme was introduced by Duermuth and Freeman. Their construction is based on samplable public key encryption, which mainly differs from general semantically secure cryptosystems in that it allows the owner of a secret key to extract the randomness used in generating a given ciphertext. However, it was left as an open problem to construct samplable public key encryption based on assumptions other then the hardness of factoring.

We show that a semantically secure variant of the McEliece cryptosystem is samplable. Being based on the McEliece assumptions, our scheme is the first not to rely on the hardness of factoring and the first to achieve post quantum security. Our construction takes advantage of specific properties of a semantically secure variant of the McEliece cryptosystem introduced by Nojima et al., which allows us to construct a randomness extraction algorithm.

Category / Keywords: public-key cryptography /

Publication Info: Deniable encryption, McEliece assumptions, multi-party computation, electronic voting

Date: received 22 Mar 2011, last revised 22 Mar 2011, withdrawn 5 Apr 2011

Contact author: bernardo david at redes unb br

Available formats: (-- withdrawn --)

Version: 20110405:202707 (All versions of this report)

Discussion forum: Show discussion | Start new discussion