Paper 2025/1088

Homomorphic Field Trace Revisited : Breaking the Cubic Noise Barrier

Abstract

We present a novel homomorphic trace evaluation algorithm $\mathsf{RevHomTrace}$, which mitigates the phase amplification problem that comes with the definition of the field trace. Our $\mathsf{RevHomTrace}$ overcomes the phase amplification with only a negligible computational overhead, thereby improving the usability of the homomorphic field trace algorithm. Moreover, our tweak also improves the noise propagation of the $\mathsf{HomTrace}$ and breaks the traditional $O(N^{3})$ variance bound in previous works into $O(N \log N)$. Our experimental results obtained by integrating $\mathsf{RevHomTrace}$ into state-of-the-art homomorphic encryption algorithms further demonstrate the usefulness of our algorithm. Specifically, $\mathsf{RevHomTrace}$ improves the noise accumulation of the (high precision) circuit bootstrapping, which also achieves maximal $1.30\times$ speedup by replacing the costly high precision trace evaluation. Also, based on our idea of $\mathsf{RevHomTrace}$, we present a low latency, high precision LWE-to-GLWE packing algorithm $\mathtt{MS}$-$\mathtt{PackLWEs}$. We also show that our $\mathtt{MS}$-$\mathtt{PackLWEs}$ significantly reduces the packing error without severe degradation of performance.