Paper 2024/1052

A New Fine Tuning Method for FHEW/TFHE Bootstrapping with IND-CPAD Security

Abstract

Fully homomorphic encryption (FHE) schemes enable computation on encrypted data, making them a crucial component of privacy-enhancing technologies. The availability of encrypted computation arises a new security notion, so-called $(c,s)$-security, proposed by Li et al. (CRYPTO'22), which considers both computational and statistical security. The key challenge is that, unlike computational security (commonly fixed at 128, 192, or 256 bits), statistical security requirements depend heavily on the application (e.g., circuit shape or number of queries). Thus, smooth control over the statistical security parameter $s$ is essential. FHEW-like schemes offer the best latency and smallest key sizes. However, Cheon et al. (CCS'24) showed a key-recovery attack that exploits failure events during legitimate evaluation queries. Consequently, achieving a sufficiently low bootstrapping failure probability, proportional to $2^{-s}$, is critical for the statistical security of FHEW-like schemes. A major limitation is that FHEW’s parameter sets are sparse, and suitable parameters achieving the exact target failure probability often do not exist. This typically forces the use of unnecessarily large parameters, leading to excessive computational costs. Recently, Bernard et al. (Eurocrypt'25) introduced a method that significantly reduces bootstrapping failure probability with minimal overhead, but their parameter sets remain sparse. In this work, we propose a new bootstrapping technique, cutoff blind rotation, which provides an additional axis of parameter optimization by enabling a smooth trade-off between computation and failure probability. This technique allows nearly continuous control of the bootstrapping failure probability in FHEW-like schemes without extra client-side overhead. We further provide concrete parameter sets achieving various failure probabilities ($2^{-64}$, $2^{-96}$, and $2^{-128}$) in our OpenFHE implementation. The implementation results show that the bootstrapping runtime can be reduced by refining the failure probability.