In contrast, all prior constructions even in the context of deniable public key encryption without homomorphic properties, encoded large messages bit by bit, where the ciphertext for each bit grew inversely with the faking probability. Indeed, all previous constructions from polynomial hardness assumptions have both the public key and ciphertext size that grows with the inverse of the faking probability achieved by the scheme. This limitation dates back to the seminal work of Canetti, Dwork, Naor and Ostrovsky (CRYPTO 1997) which introduced the notion of deniable encryption, and has been inherited by all subsequent work (excepting one by Sahai and Waters (STOC 2013) which is based on indistinguishability obfuscation. Indeed Canetti et al. argued that this dependence ``seems inherent''. Our constructions imply deniable public key encryption with deniability compactness, showing that this dependence is not inherent. However, the running time of our encryption algorithm does depend on the inverse of the faking probability, thus falling short of achieving simultaneously negligible deniability and polynomial encryption time.
At the heart of our constructions is a new way to use bootstrapping to obliviously generate FHE ciphertexts so that it supports faking under coercion.
Category / Keywords: public-key cryptography / LWE, Fully Homomorphic Encryption, Deniable Encryption Date: received 19 Dec 2020 Contact author: shweta a at cse iitm ac in,shafi goldwasser@gmail com,saleet@mit edu Available format(s): PDF | BibTeX Citation Version: 20201221:074820 (All versions of this report) Short URL: ia.cr/2020/1588