Cryptology ePrint Archive: Report 2022/094

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

Nir Drucker and Tomer Pelleg

Abstract: Harvey butterflies 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 can cause leakage, which can reduce the hardness of the ring learning with errors (R-LWE) instances used by these libraries, for example, from 2^128 to 2^104.

Category / Keywords: implementation / NTT, Harvey's Butterflies, Constant-Time Code, Compiler Optimizations, Ring-LWE, Side-Channel Attacks

Date: received 25 Jan 2022

Contact author: drucker nir at gmail com, tomer pelleg at ibm com

Available format(s): PDF | BibTeX Citation

Version: 20220131:074309 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]