Cryptology ePrint Archive: Report 2020/1588

Deniable Fully Homomorphic Encryption

Shweta Agrawal and Shafi Goldwasser and Saleet Mossel

Abstract: We introduce the notion of Deniable Fully Homomorphic Encryption and provide constructions based on the circular-secure Learning With Errors polynomial hardness assumption. Deniable fully homomorphic encryption offers a compelling upgrade of deniable public key encryption suitable for the motivating applications of deniability, such as prevention of vote-buying in electronic voting schemes where encrypted votes can be tallied without decryption, or storing encrypted data in the cloud, to be processed securely, in a deniable way. Our constructions enjoy deniability compactness, namely both the size of the public key and the size of the ciphertext of our schemes can be bounded by a fixed polynomial, independent of the level of deniability (or faking probability) achieved by the scheme. Additionally, our constructions support large message spaces and are well suited to an online-offline model of encryption, where the bulk of computation is independent of the message and may be performed in an offline pre-processing phase. This leads to a very efficient online phase, whose running time is independent of the faking probability, whereas the offline encryption run-time grows with the inverse of the faking probability.

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