Drifting Towards Better Error Probabilities in Fully Homomorphic Encryption Schemes
摘要
There are two security notions for FHE schemes: the traditional notion of IND-CPA and a more stringent notion of IND-CPAD. These notions are equivalent when FHE schemes are perfectly correct. However, for schemes with negligible failure probability, the FHE parameters required to achieve IND-CPAD 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-CPAD 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-CPAD 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-CPAD security called sIND-CPAD, which is proved to be strictly separated from the IND-CPAD notion. Criterion for turning an IND-CPAD secure public-key encryption scheme into an sIND-CPAD one is also provided.