(2026-03) Concrete Estimation of Correctness and IND-CPA-D Security for FHE via Rare Event Simulation
2026-03-27
By construction, Fully Homomorphic Encryption schemes have probabilistic correctness due to their underlying cryptographic assumptions. The family of Learning With Errors (LWE) problems assumes that a random error term is added during encryption. Statistically, this error grows as homomorphic computation proceeds. While predicting the noise evolution was initially only a correctness issue, recent works have shown a direct link with the security of FHE schemes in the IND-CPA-D model. Here, we present a framework that provides practical guarantees that the probabilities extrapolated from theoretical models satisfy bounds as small as . We show how to obtain strong experimental guarantees that the usual Gaussian model for noise is conservative and that a refined model based on Irwin-Hall distribution is valid. This is realized through an algorithm called importance splitting, which we adapt here to the cryptographic setting. We provide a detailed study in the context of TFHE bootstrapping and its variants. We believe our framework can serve as a baseline to be extended to other schemes, thereby ensuring both correctness and security across all FHE schemes.