On the Impossibility of Sender-Deniable Public Key Encryption

Recently, several open questions regarding the feasibility of deniable encryption have been resolved. A fundamental remaining open question is, whether it is possible to construct sender-deniable Encryption Schemes with super-polynomial security, where an adversary has negligible advantage in distinguishing real and fake openings. The primitive of simulatable Public Key Encryption (PKE), introduced by Damgard and Nielsen (CRYPTO, 2000), is a Public Key Encryption scheme with additional properties that allow oblivious sampling of public keys and cipher-texts. It is one of the low-level primitives used to construct adaptively-secure MPC protocols and was used by O'Neill et al. in their construction of bi-deniable encryption in the multi-distributional model (CRYPTO, 2011).