Survey of Number Theoretic Transform Algorithms for Quantum-resistant Lattice-based Cryptography

doi:10.3969/j.issn.1671-1122.2021.09.007

Abstract

Abstract:

With the rapid development of quantum computers, the traditional RSA cryptography, elliptic curve cryptography and other public key cryptosystems have been threatened seriously. In quantum-resistant cryptosystem, lattice-based cryptosystem is one of the important types and the research on its efficient implementation makes great significance. Number theoretic transform(NTT) is the important operation in lattice-based cryptosystems, and its efficiency is the key problem for efficient implementation of lattice-based cryptography. In this paper, the research progress of number theoretic transform algorithms in lattice-based cryptosystems is summarized and analyzed especially in software implementations on various CPU platforms. The improvements of NTT algorithm in butterfly structure, negative wrapped convolution and modulo reduction are analyzed and summarized. This paper can provide a research support for efficient implementation of quantum-resistant cryptographic algorithms.

Key words: quantum-resistant cryptography, lattice-based cryptography, number theoretic transform

CLC Number:

TP309

TAO Yunting, KONG Fanyu, YU Jia, XU Qiuliang. Survey of Number Theoretic Transform Algorithms for Quantum-resistant Lattice-based Cryptography[J]. Netinfo Security, 2021, 21(9): 46-51.

References 31

[1]	ARUTE F, ARYA K, BABBUSH R, et al. Quantum Supremacy Using a Programmable Superconducting Processor[J]. Nature, 2019, 574(7779): 505-510. doi: 10.1038/s41586-019-1666-5 URL
[2]	ZHONG Hansen, WANG Hui, DENG Yuhao, et al. Quantum Computational Advantage Using Photons[J]. Science, 2020, 370(6523): 1460-1463. doi: 10.1126/science.abe8770 URL
[3]	SHOR P W. Polynomial-time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer[J]. SIAM Review, 1999, 41(2): 303-332. doi: 10.1137/S0036144598347011 URL
[4]	ALAGIC G, ALPERIN-SHERIFF J, APON D, et al. Status Report on the Second Round of the NIST Post-quantum Cryptography Standardization Process[R]. US Department of Commerce, NIST, NISTIR 8309, 2020.
[5]	KATSUMATA S, MATSUDA T, TAKAYASU A. Lattice-based Revocable(hierarchical) IBE with Decryption Key Exposure Resistance[EB/OL]. https://www.sciencedirect.com/science/article/abs/pii/S0304397519307650, 2020-12-12.
[6]	SUSILO W, DUONG D H, LE H Q. Efficient Post-quantum Identity-based Encryption with Equality Test [C]//IEEE. 26th International Conference on Parallel and Distributed Systems (ICPADS), December 2-4, 2020, Hong Kong, China. New Jersey: IEEE, 2020: 633-640.
[7]	CHILLOTTI I, GAMA N, GEORGIEVA M, et al. TFHE: Fast Fully Homomorphic Encryption over the Torus[J]. Journal of Cryptology, 2020, 33(1): 34-91. doi: 10.1007/s00145-019-09319-x URL
[8]	WANG Yukun, WANG Mingqiang. A New Fully Homomorphic Signatures from Standard Lattices [C]//Springer. 15th International Conference on Wireless Algorithms, Systems, and Applications, September 13-15, 2020, Qingdao, China. Heidelberg: Spring, 2020: 494-506.
[9]	LYUBASHEVSKY V, MICCIANCIO D, PEIKERT C, et al. SWIFFT: A Modest Proposal for FFT Hashing [C]//Springer. 15th International Workshop on Fast Software Encryption, February 10-13, 2008, Lausanne, Switzerland. Heidelberg: Spring, 2008: 54-72.
[10]	HARVEY D, Faster Arithmetic for Number-theoretic Transforms[EB/OL]. https://www.sciencedirect.com/science/article/pii/S0747717113001181, 2020-12-20.
[11]	LONGA P, NAEHRIG M. Speeding up the Number Theoretic Transform for Faster Ideal Lattice-based Cryptography [C]//Springer. 15th International Conference on Cryptology and Network Security, November 14-16, 2016, Milan, Italy. Heidelberg: Spring, 2016: 124-139.
[12]	HUA Siliang, ZHANG Huiguo, WANG Shuchang. Optimization and Implementation of Number Theoretical Transform Multiplier Butterfly Operation for Fully Homomorphic Encryption[J]. Journal of Electronics & Information Technology, 2021, 43(5): 1381-1388.
	华斯亮, 张惠国, 王书昶. 用于全同态加密的数论变换乘法蝶形运算优化及实现[J]. 电子与信息学报, 2021, 43(5): 1381-1388.
[13]	HE Shiyang, LI Hui, LI Fenghua. A Survey on High-efficiency Hardware Implementation for Lattice-based Cryptosystem[J]. Journal of Cryptologic Research, 2020, 7(1): 1-19.
[14]	REGEV O. On Lattices, Learning with Errors, Random Linear Codes, and Cryptography[J]. Journal of the ACM, 2009, 56(6): 1-40.
[15]	SZE T W. Schönhage-strassen Algorithm with MapReduce for Multiplying Terabit Integers [C]//ACM. 2011 International Workshop on Symbolic-numeric Computation, June 7-9, 2011, San Jose, California. New York: ACM, 2012: 54-62.
[16]	ROY S S, VERCAUTEREN F, MENTENS N, et al. Compact Ring-LWE Cryptoprocessor [C]//Springer. 16th International Workshop on Cryptographic Hardware and Embedded Systems, September 23-26, 2014, Busan, South Korea. Heidelberg: Spring, 2014: 371-391.
[17]	PÖPPELMANN T, ODER T, GÜNEYSU T. High-performance Ideal Lattice-based Cryptography on 8-bit ATxmega microcontrollers [C]//Springer. 4th International Conference on Cryptology and Information Security in Latin America, August 23-26, 2015, Guadalajara, Mexico. Heidelberg: Spring, 2015: 346-365.
[18]	SHOUP V. Number Theory Library (Version 11.4.4)[EB/OL]. http://www.shoup.net/ntl, 2021-01-11.
[19]	HART W, NOVOCIN A, BACHMANN T, et al. Fast Library for Number Theory(Version 2.7)[EB/OL]. http://www.flintlib.org, 2021-01-22.
[20]	AGUILAR-MELCHOR C, BARRIER J, GUELTON S, et al. NFLlib: NTT-based Fast Lattice Library [C]//Springer. Cryptographer’s Track at the RSA Conference 2016, February 29-March 4, 2016, San Francisco, CA, USA. Heidelberg: Spring, 2016: 341-356.
[21]	DE CLERCQ R, ROY S S, VERCAUTEREN F, et al. Efficient Software Implementation of Ring-LWE Encryption [C]//IEEE. 2015 Design, Automation & Test in Europe Conference & Exhibition (DATE), March 9-13, 2015, Grenoble, France. New Jersey: IEEE, 2015: 339-344.
[22]	LIU Zhe, SEO H, ROY S, et al. Efficient Ring-LWE Encryption on 8-bit AVR Processors [C]//Springer. 17th International Workshop on Cryptographic Hardware and Embedded Systems, September 13-16, 2015, Saint-Malo, France. Heidelberg: Spring, 2015: 663-682.
[23]	BUCHMANN J, GÖPFERT F, GÜNEYSU T, et al. High-performance and Lightweight Lattice-based Public-key Encryption [C]//ACM. 2nd ACM International Workshop on IoT Privacy, Trust, and Security, May 30, 2016, Xi’an, China. New York: ACM, 2016: 2-9.
[24]	XU Jiming, WANG Yujian, LIU Juan, et al. A General-purpose Number Theoretic Transform Algorithm for Compact RLWE Cryptoprocessors [C]//IEEE. 2020 IEEE 14th International Conference on Anti-counterfeiting, Security, and Identification, October 30-November 1, 2020, Xiamen, China. New Jersey: IEEE, 2020: 1-5.
[25]	YIN Yanzhao, WU Liji, ZHANG Xiangmin, et al. Method to Construct Extension Field for NTT of Polynomial Multiplication with Small Modulus[J]. Journal of Cryptologic Research, 2021, 8(2): 260-272.
	殷彦昭, 乌力吉, 张向民, 等. 一种用于小模数多项式乘法快速数论变换的扩域方法[J]. 密码学报, 2021, 8(2): 260-272.
[26]	BOS J W, COSTELLO C, NAEHRIG M, et al. Post-quantum Key Exchange for the TLS Protocol from the Ring Learning with Errors Problem [C]//IEEE. 2015 IEEE Symposium on Security and Privacy, May 18-20, 2015, NW Washington, DC, USA. New Jersey: IEEE, 2015: 553-570.
[27]	ALKIM E, JAKUBEIT P, SCHWABE P. Newhope on Arm Cortex-m [C]//Springer. 6th International Conference on Security, Privacy, and Applied Cryptography Engineering, December 14-18, 2016, Hyderabad, India. Heidelberg: Spring, 2016: 332-349.
[28]	YANG Yingshan, GU Xiaozhuo, WANG Bin, et al. Efficient Password-authenticated Key Exchange from RLWE Based on Asymmetric Key Consensus [C]//Springer. 15th International Conference on Information Security and Cryptology, December 4-6, 2019, Seoul, Korea. Heidelberg: Spring, 2019: 31-49.
[29]	ODER T, PÖPPELMANN T, GÜNEYSU T. Beyond ECDSA and RSA: Lattice-based Digital Signatures on Constrained Devices [C]//IEEE. 51st ACM/EDAC/IEEE Design Automation Conference (DAC), June 1-5, 2014, San Francisco, California, USA. New Jersey: IEEE, 2014: 1-6.
[30]	DUCAS L, LEPOINT T, LYUBASHEVSKY V, et al. Crystals-dilithium: Digital Signatures from Module Lattices[EB/OL]. https://csrc.nist.gov/projects/post-quantum-cryptography/round-2-submissions, 2021-01-22.
[31]	FOUQUE P A, HOFFSTEIN J, KIRCHNER P. Fast-fourier Lattice-based Compact Signatures over NTRU[EB/OL]. https://csrc.nist.gov/projects/post-quantum-cryptography/round-2-submissions, 2021-01-22.