Cryptology ePrint Archive: Report 2015/1024

Parallel Implementation of Number Theoretic Transform

Hwajeong Seo and Zhe Liu and Yasuyuki Nogami and Jongseok Choi and Taehwan Park and Howon Kim

Abstract: Number Theoretic Transform (NTT) based polynomial multiplication is the most important operation for Lattice-based cryptography. In this paper, we implement the parallel NTT computation over ARM-NEON architecture. Our contributions include the following optimizations: (1) we vectorized the Iterative Number Theoretic Transform, (2) we propose the 32-bit wise Shifting-Addition-Multiplication-Subtraction-Subtraction (SAMS2) techniques for speeding up the modular coefficient multiplication, (3) we exploit the incomplete arithmetic for representing the coefficient to ensure the constant time modular reduction. For medium-term security level, our optimized NTT implementation requires only 27; 160 clock cycles. Similarly for long-term security level, it takes 62; 160 clock cycles. These results are faster than the state-of-art sequential implementations by 31% and 34% respectively.

Category / Keywords: implementation /

Date: received 22 Oct 2015, withdrawn 23 Oct 2015

Contact author: hwajeong84 at gmail com

Available format(s): (-- withdrawn --)

Version: 20151023:220919 (All versions of this report)

Short URL: ia.cr/2015/1024

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]