Cryptology ePrint Archive: Report 2021/803

On the Privacy of Protocols based on CPA-Secure Homomorphic Encryption

Adi Akavia and Margarita Vald

Abstract: Li and Micciancio (Eurocrypt 2021) shattered a widespread misconception regarding the security of protocols based on cpa-secure homomorphic encryption (HE). They showed an attack breaking security of HE-based protocols provided that the protocol employs an HE scheme for approximate numbers, like CKKS, and the adversary sees decrypted ciphertexts. However, their attack fails when employing exact HE schemes, like BGV, or denying access to decrypted data.

We show that the Li-Micciancio attack is only the tip of the iceberg: 1)We exhibit an input-recovery attack completely breaking the privacy of a wide and natural family of HE-based protocols, including protocols using only exact HE-schemes and with an adversary exposed solely to encrypted data. This proves that cpa-security is insufficient to ensure privacy in a much broader context than previously known. 2)To address the threat exhibited by our attack we introduce sufficient conditions, on either the encryption scheme or the protocol, that do guarantee privacy: (a) Every HE scheme with a sanitization algorithm (e.g., BGV and FHEW) can be transformed into a ``sanitized" scheme so that protocols instantiated with it preserve privacy against malicious adversaries. (b) Moreover, we characterize a natural sub-family of these protocols for which cpa-security does suffice to guarantee privacy, albeit against semi-honest adversaries.

To prove (2a) we define a notion of circuit-privacy+ that lies between semi-honest and malicious circuit-privacy and realize it from existing schemes; this may be of independent interest.

Category / Keywords: foundations / homomorphic encryption and cpa-security and protocols and attack

Date: received 14 Jun 2021, last revised 16 Jun 2021

Contact author: adi akavia at gmail com, margarita vald at cs tau ac il

Available format(s): PDF | BibTeX Citation

Note: version change: added details to the bibliography list.

Version: 20210616:092806 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]