Homomorphic Field Trace Revisited : Breaking the Cubic Noise Barrier

We present a novel homomorphic trace evaluation algorithm RevHomTrace, which mitigates the phase amplification problem that comes with the definition of the field trace. Our 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 HomTrace and breaks the traditional O (N3) variance bound in previous works into O (N log N). Our experimental results obtained by integrating RevHomTrace into state-of-theart homomorphic encryption algorithms further demonstrate the usefulness of our algorithm. Specifically, RevHomTrace improves the noise accumulation of the (high precision) circuit bootstrapping, which also achieves maximal 1.30× speedup by replacing the costly high precision trace evaluation. Also, based on our idea of RevHomTrace, we present a low latency, high precision LWE-to-GLWE packing algorithm MS-PackLWEs. We also show that our MS-PackLWEs significantly reduces the packing error without severe degradation of performance.