Refined Error Management for Gate Bootstrapping
摘要
Ducas and Micciancio introduced FHEW-like gate bootstrapping in \([ \text {Eurocrypt15} ]\) , which necessitates noise refreshing after each gate operation. Noise management is crucial in this process, as it directly affects both computational efficiency and key size. This paper optimizes noise management from three perspectives to improve gate bootstrapping efficiency and reduce key size. We refine the noise management using the three methods mentioned above, and present more compact parameters for gate bootstrapping. We then present an NTRU-based gate bootstrapping instantiation to validate the effectiveness of our refined noise management. Additionally, we optimize the gate bootstrapping performance by leveraging key unrolling and block binary keys, reducing the number of iterations in the blind rotation operation and thereby improving efficiency. Finally, we incorporate AVX instructions to further improve the performance of NTRU-based gate boostrapping. Experimental results demonstrate that our NTRU-based gate bootstrapping achieves a \(2.4\times \) speedup over the state-of-the-art LLW+ [TCHES24], while reducing the key size by \(15.2\times \) compared to LLW+ [TCHES24], \(18\times \) compared to TFHE [ASIACRYPT16], and \(122.6\times \) compared to FHEW [Eurocrypt15].