CryptoDB
Multi-Parameter Support with NTTs for NTRU and NTRU Prime on Cortex-M4
| Authors: |
|
|---|---|
| Download: | |
| Abstract: | We propose NTT implementations with each supporting at least one parameter of NTRU and one parameter of NTRU Prime. Our implementations are based on size-1440, size-1536, and size-1728 convolutions without algebraic assumptions on the target polynomial rings. We also propose several improvements for the NTT computation. Firstly, we introduce dedicated radix-(2, 3) butterflies combining Good–Thomas FFT and vector-radix FFT. In general, there are six dedicated radix-(2, 3) butterflies and they together support implicit permutations. Secondly, for odd prime radices, we show that the multiplications for one output can be replaced with additions/subtractions. We demonstrate the idea for radix-3 and show how to extend it to any odd prime. Our improvement also applies to radix-(2, 3) butterflies. Thirdly, we implement an incomplete version of Good–Thomas FFT for addressing potential code size issues. For NTRU, our polynomial multiplications outperform the state-of-the-art by 2.8%−10.3%. For NTRU Prime, our polynomial multiplications are slower than the state-of-the-art. However, the SotA exploits the specific structure of coefficient rings or polynomial moduli, while our NTT-based multiplications exploit neither and apply across different schemes. This reduces the engineering effort, including testing and verification. |
BibTeX
@article{tches-2022-32366,
title={Multi-Parameter Support with NTTs for NTRU and NTRU Prime on Cortex-M4},
journal={IACR Transactions on Cryptographic Hardware and Embedded Systems},
publisher={Ruhr-Universität Bochum},
volume={2022, Issue 4},
pages={349-371},
url={https://tches.iacr.org/index.php/TCHES/article/view/9823},
doi={10.46586/tches.v2022.i4.349-371},
author={Erdem Alkim and Vincent Hwang and Bo-Yin Yang},
year=2022
}