New Techniques for Fast and Shallow FHE Bootstrapping and Beyond

The main barrier to practical fully homomorphic encryption remains the latency and cost of bootstrapping, the ciphertext refresh step that enables unbounded computation. We design new methods that reduce both the latency and the circuit depth of bootstrapping in the FHEW/TFHE framework, which represents the state-of-the-art for lightweight bootstrapping and for computing deep and unstructured Boolean functions over encrypted data.

Our first contribution leverages LWE with a sparse small-norm secret, an assumption known to be equivalent to standard LWE and already widely used in FHE constructions. For an LWE secret of dimension $n$ and Hamming weight $h$, we obtain bootstrapping procedures whose arithmetic complexity decreases from $\tilde O(n^2)$ to $\tilde O(n h)$ $\mathbb{Z}_q$ multiplications while preserving the same asymptotic number of additions. Concretely, this yields a $4.5$--$7.5\times$ practical speedup for gate and functional bootstrapping over the state-of-the-art OpenFHE implementation.

Our second contribution introduces a new RLWE variant with structured secrets, called **, and uses it to significantly reduce the circuit depth of FHEW/TFHE bootstrapping via a new relinearization-free BV multiplication technique. In concrete parameter settings, this reduces the number of sequential NTT/INTT layers required for bootstrapping to just 3, compared to more than 500 in standard FHEW/TFHE, while keeping the overall number of unit 32 or 64-bit word operations comparable to standard FHEW/TFHE bootstrapping. This substantial depth reduction suggests the potential for significantly lower bootstrapping latency on parallel, high-throughput architectures such as GPUs.

Finally, we analyze the security of the new RLWE assumption underlying our depth reduction, including worst-case-to-average-case and search-to-decision reductions, as well as evaluations against concrete attacks.