Relations Among New CCA Security Notions for Approximate FHE

Chris Brzuska; Sébastien Canard; Caroline Fontaine; Duong Hieu Phan; David Pointcheval; Marc Renard; Renaud Sirdey

doi:10.62056/aee0iv7sf

Relations Among New CCA Security Notions for Approximate FHE

Authors

Chris Brzuska, Sébastien Canard, Caroline Fontaine, Duong Hieu Phan, David Pointcheval, Marc Renard, Renaud Sirdey

Chris Brzuska

Aalto University, Espoo, Finland
chris dot brzuska at aalto dot fi

Sébastien Canard

Télécom Paris, Institut Polytechnique de Paris, Palaiseau, France
sebastien dot canard at telecom-paris dot fr

Caroline Fontaine

Université Paris-Saclay, CNRS, ENS Paris-Saclay, Laboratoire Méthodes Formelles, Gif-sur-Yvette, France
caroline dot fontaine at cnrs dot fr

Duong Hieu Phan

Télécom Paris, Institut Polytechnique de Paris, Palaiseau, France
hieu dot phan at telecom-paris dot fr

David Pointcheval

DIENS, Ecole normale supérieure, CNRS, Inria, PSL University, Paris, France
Cosmian, Paris, France
david dot pointcheval at ens dot fr

Marc Renard

Université Paris-Saclay, CNRS, ENS Paris-Saclay, Laboratoire Méthodes Formelles, Gif-sur-Yvette, France
Université Paris-Saclay, CEA, List, Palaiseau, France
marc dot renard at cea dot fr

Renaud Sirdey

Université Paris-Saclay, CEA, List, Palaiseau, France
renaud dot sirdey at cea dot fr

Abstract

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 correct 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 known so far to be achievable by both correct and approximate FHE schemes.

References

[ABMP24]

A. Alexandru, A. Al Badawi, D. Micciancio, and Y. Polyakov. Application-Aware Approximate Homomorphic Encryption: Configuring FHE for Practical Use. Technical report number 203, IACR ePrint. 2024.

Google Scholar ePrint

[BBB⁺22]

A. Al Badawi, J. Bates, F. Bergamaschi, D. B. Cousins, S. Erabelli, N. Genise, S. Halevi, H. Hunt, A. Kim, Y. Lee, Z. Liu, D. Micciancio, I. Quah, Y. Polyakov, R. V. Saraswathy, K. Rohloff, J. Saylor, D. Suponitsky, M. Triplett, V. Vaikuntanathan, and V. Zucca. OpenFHE: Open-Source Fully Homomorphic Encryption Library. In WAHC, pages 53-63. 2022. DOI: 10.1145/3560827.3563379

Google Scholar ePrint

[BDJR97]

M. Bellare, A. Desai, E. Jokipii, and P. Rogaway. A concrete security treatment of symmetric encryption. In IEEE SFCS, pages 394-403. 1997. DOI: 10.1109/SFCS.1997.646128

Google Scholar ePrint

[BDPR98]

M. Bellare, A. Desai, D. Pointcheval, and P. Rogaway. Relations among notions of security for public-key encryption schemes. In CRYPTO, pages 26-45. 1998. DOI: 10.1007/BFb0055718

Google Scholar ePrint

[BGV12]

Z. Brakerski, C. Gentry, and V. Vaikuntanathan. (Leveled) Fully Homomorphic Encryption without bootstrapping. ACM ITCS, 2012. DOI: 10.1145/2090236.2090262

Google Scholar ePrint

[BJSW24]

O. Bernard, M. Joye, N. P. Smart, and M. Walter. Drifting Towards Better Error Probabilities in Fully Homomorphic Encryption Schemes. Technical report number 1718, IACR ePrint. 2024.

Google Scholar ePrint

[Bra12]

Z. Brakerski. Fully Homomorphic Encryption without Modulus Switching from Classical GapSVP. In CRYPTO, pages 868-886. 2012. DOI: 10.1007/978-3-642-32009-5_50

Google Scholar ePrint

[CCP⁺24]

J. H. Cheon, H. Choe, A. Passelègue, D. Stehlé, and E. Suvanto. Attacks Against the IND-CPAD Security of Exact FHE Schemes. In CCS, pages 2505 - 2519. 2024. DOI: 10.1145/3658644.3690341

Google Scholar ePrint

[CGGI16]

I. Chillotti, N. Gama, M. Georgieva, and M. Izabachène. Faster Fully Homomorphic Encryption: Bootstrapping in Less Than 0.1 Seconds. In ASIACRYPT, pages 3-33. 2016. DOI: 10.1007/978-3-662-53887-6_1

Google Scholar ePrint

[CKKS17]

J. H. Cheon, A. Kim, M. Kim, and Y. Song. Homomorphic Encryption for Arithmetic of Approximate Numbers. In ASIACRYPT, pages 409-437. 2017. DOI: 10.1007/978-3-319-70694-8_15

Google Scholar ePrint

[CSBB24]

M. Checri, R. Sirdey, A. Boudguiga, and J.-P. Bultel. On the practical CPAD security of “exact” and threshold FHE schemes. In CRYPTO, pages 3-33. 2024. DOI: 10.1007/978-3-031-68382-4_1

Google Scholar ePrint

[DNR04]

C. Dwork, M. Naor, and O. Reingold. Immunizing Encryption Schemes from Decryption Errors. In EUROCRYPT, pages 342-360. 2004. DOI: 10.1007/978-3-540-24676-3_21

Google Scholar ePrint

[FV12]

J. Fan and F. Vercauteren. Somewhat Practical Fully Homomorphic Encryption. Technical report number 2012/144, IACR ePrint. 2012.

Google Scholar ePrint

[GNS23]

C. Ganesh, A. Nitulescu, and E. Soria-Vazquez. Rinocchio: SNARKs for Ring Arithmetic. J. Cryptol., 2023. DOI: 10.1007/s00145-023-09481-3

Google Scholar ePrint

[GNSJ24]

Q. Guo, D. Nabokov, E. Suvanto, and T. Johansson. Key recovery attacks on approximate Homomorphic Encryption with nonworst-case noise flooding countermeasures. In Usenix Security, pages 7447-7461. 2024.

Google Scholar ePrint

[GSCS⁺23]

A. Grivet-Sébert, M. Checri, O. Stan, R. Sirdey, and C. Gouy-Pailler. Combining Homomorphic Encryption and differential privacy in federated learning. In IEEE PST, pages 1-7. 2023. DOI: 10.1109/PST58708.2023.10320195

Google Scholar ePrint

[GSPZ⁺21]

A. Grivet-Sébert, R. Pinot, M. Zuber, C. Gouy-Pailler, and R. Sirdey. SPEED: secure, PrivatE, and efficient deep learning. Machine Learning, 2021. DOI: 10.1007/s10994-021-05970-3

Google Scholar ePrint

[GSZS⁺23]

A. Grivet-Sébert, M. Zuber, O. Stan, R. Sirdey, and C. Gouy-Pailler. A Probabilistic Design for Practical Homomorphic Majority Voting with Intrinsic Differential Privacy. In WAHC, pages 47-58. 2023. DOI: 10.1145/3605759.3625258

Google Scholar ePrint

[LM21]

B. Li and D. Miccianccio. On the Security of Homomorphic Encryption on Approximate Numbers. In EUROCRYPT, pages 648-677. 2021. DOI: 10.1007/978-3-030-77870-5_23

Google Scholar ePrint

[LMSS22]

B. Li, D. Miccianccio, M. Schultz, and J. Sorrell. Securing Approximate Homomorphic Encryption Using Differential Privacy. In CRYPTO, pages 560-589. 2022. DOI: 10.1007/978-3-031-15802-5_20

Google Scholar ePrint

[MN24]

M. Manulis and J. Nguyen. Fully Homomorphic Encryption beyond IND-CCA1 Security: Integrity through Verifiability. In EUROCRYPT, pages 63-93. 2024. DOI: 10.1007/978-3-031-58723-8_3

Google Scholar ePrint

[NY90]

M. Naor and M. Yung. Public-key cryptosystems provably secure against chosen ciphertext attacks. In ACM STOC, pages 427-437. 1990. DOI: 10.1145/100216.100273

Google Scholar ePrint

[VKH23]

A. Viand, C. Knabenhans, and A. Hithnawi. Verifiable Fully Homomorphic Encryption. Technical report number 2301.07041, arXiv. 2023.

Google Scholar ePrint

PDF Open access

DOI: https://doi.org/10.62056/aee0iv7sf

History

Submitted: 2025-01-10
Accepted: 2025-03-11
Published: 2025-04-08

How to cite

Chris Brzuska, Sébastien Canard, Caroline Fontaine, Duong Hieu Phan, David Pointcheval, Marc Renard, and Renaud Sirdey, Relations Among New CCA Security Notions for Approximate FHE. IACR Communications in Cryptology, vol. 2, no. 1, Apr 08, 2025, doi: 10.62056/aee0iv7sf.

License

Copyright is held by the author(s)

This work is licensed under a Creative Commons Attribution (CC BY) license.

@article{10.62056/aee0iv7sf,
         author={Chris Brzuska and 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}},
         volume={2},
         number={1},
         year={2025},
         date={2025-04-08},
         issn={3006-5496},
         doi={10.62056/aee0iv7sf},
         journal={{IACR} Communications in Cryptology},
         publisher={International Association for Cryptologic Research}
}

TY  - JOUR
AU  - Chris Brzuska
AU  - Sébastien Canard
AU  - Caroline Fontaine
AU  - Duong Hieu Phan
AU  - David Pointcheval
AU  - Marc Renard
AU  - Renaud Sirdey
PY  - 2025
TI  - Relations Among New CCA Security Notions for Approximate FHE
JF  - IACR Communications in Cryptology
JA  - CIC
VL  - 2
IS  - 1
DO  - 10.62056/aee0iv7sf
UR  - https://doi.org/10.62056/aee0iv7sf
AB  - <p>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 correct 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 known so far to be achievable by both correct and approximate FHE schemes. </p>
ER  -

Chris Brzuska, Sébastien Canard, Caroline Fontaine, Duong Hieu Phan, David Pointcheval, Marc Renard, and Renaud Sirdey, Relations Among New CCA Security Notions for Approximate FHE. IACR Communications in Cryptology, vol. 2, no. 1, Apr 08, 2025, doi: 10.62056/aee0iv7sf.