Paper 2025/2288

Achieving CPAD security for BFV: a pragmatic approach

Abstract

Fully Homomorphic Encryption (FHE) aims at ensuring privacy of sensitive data while taking advantage of external computations and services. However, using FHE in real-world scenarios reveals new kinds of security issues. In particular, following Li&Micciancio Eurocrypt'21 seminal paper, CPAD security has emerged as a fundamental notion for FHE, unveiling a subtle interplay between security and correctness. For correct (F)HE schemes, CPA security already implies CPAD. However, all known practical FHE schemes are (R)LWE-based and, as such, are prone to decryption errors; and even if it is possible to ensure statistical correctness by selecting appropriate parameters, achieving this while maintaining malleability --- the mainspring of FHE --- still remains challenging. Moreover, practical CPAD attacks have recently been designed against most known FHE schemes. We propose in this paper a complete, simple and rigorous framework to reach CPAD security for one of them, BFV. Our approach relies on a combination of alternate average-case/worst-case noise variance monitoring --- based on dependencies tracking during the homomorphic calculations --- and on smudging. It comes with an automated parameters setting methodology, which connects it to the recently proposed Application-Aware HE paradigm while relieving libraries end-users from the burden of enforcing the paradigm's constraints by hand.

Note: Added Acknowledgements section.