Paper 2021/803

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

Adi Akavia and Margarita Vald


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.

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

Available format(s)
Publication info
Preprint. MINOR revision.
Contact author(s)
adi akavia @ gmail com
margarita vald @ cs tau ac il
2021-06-16: last of 2 revisions
2021-06-14: received
See all versions
Short URL
Creative Commons Attribution


      author = {Adi Akavia and Margarita Vald},
      title = {On the Privacy of Protocols based on CPA-Secure Homomorphic Encryption},
      howpublished = {Cryptology ePrint Archive, Paper 2021/803},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.