Timing leakage analysis of non-constant-time NTT implementations with Harvey butterflies

Abstract

Harvey butteries and their variants are core primitives in many optimized number-theoretic transform (NTT) implementations, such as those used by the HElib and SEAL homomorphic encryption libraries. However, these butterflies are not constant-time algorithms and may leak secret data when incorrectly implemented. Luckily for SEAL and HElib, the compilers optimize the code to run in constant-time. We claim that relying on the compiler is risky and demonstrate how a simple code modification, naive compiler misuse, or even a malicious attacker that injects just a single compiler flag can cause leakage. This leakage can reduce the hardness of the ring learning with errors (R-LWE) instances used by these libraries, for example, from 2128 to 2104.