Cryptology ePrint Archive: Report 2022/282

Achievable CCA2 Relaxation for Homomorphic Encryption

Adi Akavia and Craig Gentry and Shai Halevi and Margarita Vald

Abstract: 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.

Category / Keywords: foundations / homomorphic encryption, chosen plaintext attack, chosen ciphertext attack, cryptographic protocols, attack

Original Publication (with major differences): Cryptology ePrint Archive: Report 2021/803

Date: received 2 Mar 2022

Contact author: adi akavia at gmail com, craigbgentry at gmail com, shaih at alum mit edu, margarita vald at cs tau ac il

Available format(s): PDF | BibTeX Citation

Version: 20220302:142503 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]