Failure Probability in FHE Measured with Rare Event Simulation w/ Mathieu Ballandras
#Abstract
The security of homomorphic encryption schemes based on the Learning With Errors problem requires the presence of a noise term in ciphertext. This noise can grow during homomorphic operations and can lead to decryption failure. The probability of such an event is called the failure probability.
In the IND-CPA-D security model, failures are not only an inconvenience but also a security issue as they leak information about the secret key. It is therefore essential to enforce low failure probabilities.
In TFHE, these probabilities are usually predicted theoretically by assuming the noise follows a Gaussian distribution.
We use a technique of rare event simulation called importance splitting to experimentally measure the failure probability. We obtain strong experimental guarantees that for several standard variants of TFHE, the usual Gaussian model for noise is conservative and that a refined model based on Irwin--Hall distribution is valid.
These experiments confirm the IND-CPA-D security of the scheme.
#About the Speaker
Mathieu Ballandras is a researcher at Zama, his research focuses on TFHE.
#More Information
Want more information, recordings of the presentations, slides, and other resources from the meetup? Visit this meetup's resource page at https://fhe.org/meetups/087
#Never Miss an Update
The newsletter where we post community announcements: https://fheorg.substack.com/
The discord server where you can discuss FHE related topics with the community: https://discord.fhe.org
Make sure to join either (or both) of these to stay informed about future events!