Paper 2024/1718

Drifting Towards Better Error Probabilities in Fully Homomorphic Encryption Schemes

Abstract

There are two security notions for FHE schemes the traditional notion of IND-CPA, and a more stringent notion of IND-CPA${}^D$. The notions are equivalent if the FHE schemes are perfectly correct, however for schemes with negligible failure probability the FHE parameters needed to obtain IND-CPA$$ security can be much larger than those needed to obtain IND-CPA security. This paper uses the notion of ciphertext drift in order to understand the practical difference between IND-CPA and IND-CPA$$ security in schemes such as FHEW, TFHE and FINAL. This notion allows us to define a modulus switching operation (the main culprit for the difference in parameters) such that one does not require adapting IND-CPA cryptographic parameters to meet the IND-CPA$$ security level. Further, the extra cost incurred by the new techniques has no noticeable performance impact in practical applications. The paper also formally defines a stronger version for IND-CPA$$ security called sIND-CPA$$, which is proved to be strictly separated from the IND-CPA$$ notion. Criterion for turning an IND-CPA$$ secure public-key encryption into an sIND-CPA$$ one is also provided.