Paper 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.
Metadata
- Available format(s)
-
PDF
- Category
- Implementation
- Publication info
- Preprint. MINOR revision.
- Keywords
- NTTHarvey's ButterfliesConstant-Time CodeCompiler OptimizationsRing-LWESide-Channel Attacks
- Contact author(s)
-
drucker nir @ gmail com
tomer pelleg @ ibm com - History
- 2022-01-31: received
- Short URL
- https://ia.cr/2022/094
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2022/094,
author = {Nir Drucker and Tomer Pelleg},
title = {Timing leakage analysis of non-constant-time {NTT} implementations with Harvey butterflies},
howpublished = {Cryptology {ePrint} Archive, Paper 2022/094},
year = {2022},
url = {https://eprint.iacr.org/2022/094}
}