<abstract xmlns="http://www.w3.org/1999/xhtml">

<p>In this article, we describe the principles and advantages of using the Number-Theoretic Transform (NTT) in post-quantum cryptography. We deal with usages of NTT in post-quantum algorithms included in the competition announced by the National Institute of Standards and Technology. Attention is paid to the fast multiplication of polynomials using NTT and negacyclic convolution. We also focus on the existing implementation of NTT and its modifications to analyze the effectiveness of individual modifications. Separate attention is paid to the Constant Time implementation of NTT because the constant computation time of the transformation decreases a possibility of side channel attack. We describe measurements performed on OS Linux Ubuntu 20.04 LTS environment in Linux kernel mode, with the highest attention to the measurement executed on a microcontroller with an ARM 32-bit core. Measurements performed on microcontroller units are done using 32-bit and 16-bit arithmetic to demonstrate how to achieve constant computation time of the transformation. We present the results and analysis of measurements performed using modified implementations.</p>
</abstract>

In this article, we describe the principles and advantages of using the Number-Theoretic Transform (NTT) in post-quantum cryptography. We deal with usages of NTT in post-quantum algorithms included in the competition announced by the National Institute of Standards and Technology. Attention is paid to the fast multiplication of polynomials using NTT and negacyclic convolution. We also focus on the existing implementation of NTT and its modifications to analyze the effectiveness of individual modifications. Separate attention is paid to the Constant Time implementation of NTT because the constant computation time of the transformation decreases a possibility of side channel attack. We describe measurements performed on OS Linux Ubuntu 20.04 LTS environment in Linux kernel mode, with the highest attention to the measurement executed on a microcontroller with an ARM 32-bit core. Measurements performed on microcontroller units are done using 32-bit and 16-bit arithmetic to demonstrate how to achieve constant computation time of the transformation. We present the results and analysis of measurements performed using modified implementations.

Number-Theoretic Transform with Constant Time Computation for Embedded Post-Quantum Cryptography

Department of Electronics and Multimedia Telecommunications, Faculty of Electrical Engineering and Informatics

Acta Electrotechnica et Informatica

This work is licensed under the Creative Commons Attribution 4.0 International License.

In this article, we describe the principles and advantages of using the Number-Theoretic Transform (NTT) in post-quantum cryptography. We deal with usages of...

Number-Theoretic Transform with Constant Time Computation for Embedded Post-Quantum Cryptography

Published Online: Jan 24, 2023

Page range: 30 - 37

Received: Sep 12, 2022

Accepted: Dec 08, 2022

DOI: https://doi.org/10.2478/aei-2022-0020

Keywords
NTT transformation, post-quantum cryptography, negacyclic convolution, microcontroller, Montgomery reduction

© 2022 Eva Kupcová et al., published by Sciendo

This work is licensed under the Creative Commons Attribution 4.0 International License.

Number-Theoretic Transform with Constant Time Computation for Embedded Post-Quantum Cryptography

Published Online: Jan 24, 2023

Page range: 30 - 37

Received: Sep 12, 2022

Accepted: Dec 08, 2022

DOI: https://doi.org/10.2478/aei-2022-0020

KeywordsNTT transformation, post-quantum cryptography, negacyclic convolution, microcontroller, Montgomery reduction

© 2022 Eva Kupcová et al., published by Sciendo

This work is licensed under the Creative Commons Attribution 4.0 International License.

Keywords
NTT transformation, post-quantum cryptography, negacyclic convolution, microcontroller, Montgomery reduction