Paper 2024/202

Fully Homomorphic Encryption beyond IND-CCA1 Security: Integrity through Verifiability

Mark Manulis, Universität der Bundeswehr München
Jérôme Nguyen, Universität der Bundeswehr München
Abstract

We focus on the problem of constructing fully homomorphic encryption (FHE) schemes that achieve some meaningful notion of adaptive chosen-ciphertext security beyond CCA1. Towards this, we propose a new notion, called security against verified chosen-ciphertext attack (vCCA). The idea behind it is to ascertain integrity of the ciphertext by imposing a strong control on the evaluation algorithm. Essentially, we require that a ciphertext obtained by the use of homomorphic evaluation must be "linked" to the original input ciphertexts. We formalize the vCCA notion in two equivalent formulations; the first is in the indistinguishability paradigm, the second follows the non-malleability simulation-based approach, and is a generalization of the targeted malleability introduced by Boneh et al. in 2012. We strengthen the credibility of our definitions by exploring relations to existing security notions for homomorphic encryption schemes, namely CCA1, RCCA, FuncCPA, CCVA, and HCCA. We prove that vCCA security is the strongest notion known so far, that can be achieved by an FHE scheme; in particular, vCCA is strictly stronger than CCA1. Finally, we provide a general transformation, that takes any CPA-secure FHE scheme and makes it vCCA-secure. Our transformation first turns an FHE scheme into a CCA2-secure scheme where a part of the ciphertext retains the homomorphic properties and then extends it with a succinct non-interactive argument of knowledge (SNARK) to verifiably control the evaluation algorithm. In fact, we obtain four general variation of this transformation. We handle both the asymmetric and the symmetric key FHE schemes, and for each we give two variations differing in whether the ciphertext integrity can be verified publicly or requires the secret key. We use well-known techniques to achieve CCA security in the first step of our transformation. In the asymmetric case, we use the double encryption paradigm, and in the symmetric case, we use Encrypt-then-MAC techniques. Furthermore, our transformation also gives the first CCA-secure FHE scheme based on bootstrapping techniques.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published by the IACR in EUROCRYPT 2024
Keywords
Fully homomorphic encryptionChosen-ciphertext attackBootstrappingvCCACiphertext integrityVerifiable FHE
Contact author(s)
mark @ manulis eu
jerome nguyen @ unibw de
History
2024-02-12: approved
2024-02-09: received
See all versions
Short URL
https://ia.cr/2024/202
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2024/202,
      author = {Mark Manulis and Jérôme Nguyen},
      title = {Fully Homomorphic Encryption beyond IND-CCA1 Security: Integrity through Verifiability},
      howpublished = {Cryptology ePrint Archive, Paper 2024/202},
      year = {2024},
      note = {\url{https://eprint.iacr.org/2024/202}},
      url = {https://eprint.iacr.org/2024/202}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.