Paper 2024/812

Relations among new CCA security notions for approximate FHE

Sébastien Canard, Télécom Paris, Institut Polytechnique de Paris, F-91120, Palaiseau, France
Caroline Fontaine, Université Paris-Saclay, CNRS, ENS Paris-Saclay, Laboratoire Méthodes Formelles, 91190, Gif-sur-Yvette, France
Duong Hieu Phan, Télécom Paris, Institut Polytechnique de Paris, F-91120, Palaiseau, France
David Pointcheval, DIENS, Ecole normale supérieure, CNRS, Inria, PSL University, Paris, France
Marc Renard, Université Paris-Saclay, CEA, List, F-91120, Palaiseau, France
Renaud Sirdey, Université Paris-Saclay, CEA, List, F-91120, Palaiseau, France

In a recent Eurocrypt'24 paper, Manulis and Nguyen have proposed a new CCA security notion, vCCA, and associated construction blueprints to leverage both CPA-secure and correct FHE beyond the CCA1 security barrier. However, because their approach is only valid under the correctness assumption, it leaves a large part of the FHE spectrum uncovered as many FHE schemes used in practice turn out to be approximate and, as such, do not satisfy the correctness assumption. In this paper, we improve their work by defining and investigating a variant of their security notion which is suitable for a more general case where approximate FHE are included. As the passive security of approximate FHE schemes is more appropriately captured by CPAD rather than CPA security, we start from the former notion to define our vCCAD new security notion. Although, we show that vCCA and vCCAD are equivalent when the correctness assumption holds, we establish that vCCAD security is strictly stronger than vCCA security in the general case. In doing so, we interestingly establish several new separation results between variants of CPAD security of increasing strength. This allows us to clarify the relationship between vCCA security and CPAD security, and to reveal that the security notions landscape is much simpler for exact FHE than when approximate ones are included --- in which case, for example, we establish that multiple challenges security notions are strictly stronger than single-challenge ones for both CPAD and vCCAD security. Lastly, we also give concrete construction blueprints, showing how to leverage some of the blueprints proposed by Manulis and Nguyen to achieve vCCAD security. As a result, vCCAD security is the strongest CCA security notion so far known to be achievable by both correct and approximate FHE schemes.

Available format(s)
Public-key cryptography
Publication info
FHECPADCCA securitySNARKVerifiability.
Contact author(s)
sebastien canard @ telecom-paris fr
caroline fontaine @ cnrs fr
hieu phan @ telecom-paris fr
david pointcheval @ ens fr
marc renard @ cea fr
renaud sirdey @ cea fr
2024-05-27: approved
2024-05-24: received
See all versions
Short URL
Creative Commons Attribution


      author = {Sébastien Canard and Caroline Fontaine and Duong Hieu Phan and David Pointcheval and Marc Renard and Renaud Sirdey},
      title = {Relations among new {CCA} security notions for approximate {FHE}},
      howpublished = {Cryptology ePrint Archive, Paper 2024/812},
      year = {2024},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.