Paper 2024/812

Relations among new CCA security notions for approximate FHE

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

Note: Added clarifications in Sect. 6 (Construction blueprints): more detailed proofs for Propositions 16 and 17; formalization of the CCA2-companion-ciphertext blueprint as a proof system (Lemma 3); explicitation of the (new) compact and public key Encrypt-then-Prove blueprint (Proposition 18 is new); modification of the claim and proof of Prop. 17 and 18 to account for the notion of Strong CPAD introduced in ePrint 2024/1718. Added new separation result between (q,l)-CPAD and (q,l+1)-CPAD in Sect. D. Added a number of more minor precisions and clarifications in various places. We also added Chris Brzuska as a co-author for his contributions to this new version of this paper.