Timing Leakage Analysis of Non-constant-time NTT Implementations with Harvey Butterflies

Nir Drucker, 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.
BibTeX
@article{drucker2022timing,
  author = {Nir Drucker and Tomer Pelleg},
  title = {{Timing Leakage Analysis of Non-constant-time NTT Implementations with Harvey Butterflies}},
  journal = {IACR Cryptol. ePrint Arch.},
  year = {2022},
  doi = {10.1007/978-3-031-07689-3\_8},
}

Loading related content...

Figure