Cryptology ePrint Archive: Report 2020/1216
Polynomial Multiplication in NTRU Prime: Comparison of Optimization Strategies on Cortex-M4
Erdem Alkim and Dean Yun-Li Cheng and Chi-Ming Marvin Chung and Hülya Evkan and Leo Wei-Lun Huang and Vincent Hwang and Ching-Lin Trista Li and Ruben Niederhagen and Cheng-Jhih Shih and Julian Wälde and Bo-Yin Yang
Abstract: This paper proposes two different methods
to perform NTT-based polynomial multiplication
in polynomial rings
that do not naturally support such a multiplication.
We demonstrate these methods
on the NTRU Prime key-encapsulation mechanism (KEM)
proposed by Bernstein, Chuengsatiansup, Lange, and Vredendaal,
which uses a polynomial ring
that is, by design, not amenable to use with NTT.
One of our approaches
is using Good's trick
and focuses on speed and supporting more than one parameter set with a single implementation.
The other approach
is using a mixed-radix NTT
and focuses on the use of smaller multipliers
and less memory.
On an ARM Cortex-M4 microcontroller,
we show that our three NTT-based implementations,
one based on Good's trick and two mixed-radix NTTs,
provide between
32% and 17% faster polynomial multiplication. For the parameter-set ntrulpr761,
this results in between 16% and 9% faster total operations (sum of key generation,
encapsulation, and decapsulation) and requires between 15% and 39% less memory
than the current state-of-the-art NTRU Prime implementation on this platform,
which is using Toom-Cook-based polynomial multiplication.
Category / Keywords: implementation / NTT, Polynomial multiplication, Cortex-M4, NTRU Prime, PQC
Original Publication (with minor differences): IACR-CHES-2021
Date: received 3 Oct 2020, last revised 26 Oct 2020
Contact author: erdemalkim at gmail com,ruben@polycephaly org,by@crypto tw
Available format(s): PDF | BibTeX Citation
Version: 20201026:122556 (All versions of this report)
Short URL: ia.cr/2020/1216
[ Cryptology ePrint archive ]