Paper 2022/282

Achievable CCA2 Relaxation for Homomorphic Encryption

Adi Akavia, Craig Gentry, Shai Halevi, and Margarita Vald


Homomorphic encryption (HE) protects data in-use, but can be computationally expensive. To avoid the costly bootstrapping procedure that refreshes ciphertexts, some works have explored client-aided outsourcing protocols, where the client intermittently refreshes ciphertexts for a server that is performing homomorphic computations. But is this approach secure against malicious servers? We present a CPA-secure encryption scheme that is completely insecure in this setting. We define a new notion of security, called funcCPA, that we prove is sufficient. Additionally, we show: - Homomorphic encryption schemes that have a certain type of circuit privacy -- for example, schemes in which ciphertexts can be ``sanitized''-- are funcCPA-secure. - In particular, assuming certain existing HE schemes are CPA-secure, they are also funcCPA-secure. - For certain encryption schemes, like Brakerski-Vaikuntanathan, that have a property that we call oblivious secret key extraction, funcCPA-security implies circular security -- i.e., that it is secure to provide an encryption of the secret key in a form usable for bootstrapping (to construct fully homomorphic encryption). In summary, funcCPA-security lies strictly between CPA-security and CCA2-security (under reasonable assumptions), and has an interesting relationship with circular security, though it is not known to be equivalent.

Available format(s)
Publication info
Published elsewhere. Major revision. Cryptology ePrint Archive: Report 2021/803
homomorphic encryptionchosen plaintext attackchosen ciphertext attackcryptographic protocolsattack
Contact author(s)
adi akavia @ gmail com
craigbgentry @ gmail com
shaih @ alum mit edu
margarita vald @ cs tau ac il
2022-03-02: received
Short URL
Creative Commons Attribution


      author = {Adi Akavia and Craig Gentry and Shai Halevi and Margarita Vald},
      title = {Achievable {CCA2} Relaxation for Homomorphic Encryption},
      howpublished = {Cryptology ePrint Archive, Paper 2022/282},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.