抗量子格密码体制的快速数论变换算法研究综述

doi:10.3969/j.issn.1671-1122.2021.09.007

信息网络安全 ›› 2021, Vol. 21 ›› Issue (9): 46-51.doi: 10.3969/j.issn.1671-1122.2021.09.007

抗量子格密码体制的快速数论变换算法研究综述

陶云亭¹, 孔凡玉¹(), 于佳², 徐秋亮¹

1.山东大学软件学院,济南 250101
2.青岛大学计算机科学技术学院,青岛 266071

收稿日期:2021-04-11 出版日期:2021-09-10 发布日期:2021-09-22
通讯作者: 孔凡玉 E-mail:fanyukong@sdu.edu.cn
作者简介:陶云亭（1989—）,男,山东,硕士研究生,主要研究方向为密码学与信息安全|孔凡玉（1978—）,男,山东,副教授,博士,主要研究方向为密码学与信息安全|于佳（1976—）,男,山东,教授,博士,主要研究方向为密码学与信息安全|徐秋亮（1960—）,男,山东,教授,博士,主要研究方向为密码学与安全多方计算
基金资助:
山东省重点研发计划(2020CXGC010114)

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

TAO Yunting¹, KONG Fanyu¹(), YU Jia², XU Qiuliang¹

1. School of Software, Shandong University, Jinan 250101, China
2. College of Computer Science and Technology, Qingdao University, Qingdao 266071, China

Received:2021-04-11 Online:2021-09-10 Published:2021-09-22
Contact: KONG Fanyu E-mail:fanyukong@sdu.edu.cn

摘要/Abstract

摘要：

量子计算机的迅速发展给传统的RSA密码、ECC等公钥密码体制带来严重的安全威胁。在抗量子公钥密码体制中,基于格的密码体制是重要的研究类型之一,对算法快速实现的研究具有重要意义。快速数论变换算法是格密码体制的核心运算,其运算效率是实现格密码算法的关键。文章主要对格密码体制中的快速数论变换算法的研究进展,特别是近年来在各种CPU平台上的软件实现方法的进展进行分析和综述,对快速数论变换算法在蝶形结构、负包卷积、取模运算等方面的改进算法进行分析和总结。

关键词: 抗量子密码体制, 格密码体制, 快速数论变换

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

中图分类号:

TP309

陶云亭, 孔凡玉, 于佳, 徐秋亮. 抗量子格密码体制的快速数论变换算法研究综述[J]. 信息网络安全, 2021, 21(9): 46-51.

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.

参考文献 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.

抗量子格密码体制的快速数论变换算法研究综述

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

RichHTML

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

参考文献 31

相关文章 15

编辑推荐

Metrics

本文评价

[1]	王跃东, 熊焰, 黄文超, 武建双. 一种面向5G专网鉴权协议的形式化分析方案[J]. 信息网络安全, 2021, 21(9): 1-7.
[2]	顾兆军, 姚峰, 丁磊, 隋翯. 基于半实物的机场供油自控系统网络安全测试[J]. 信息网络安全, 2021, 21(9): 16-24.
[3]	马玲, 覃亮成. 基于DCT-DQFT变换和QR分解的彩色图像盲水印算法[J]. 信息网络安全, 2021, 21(9): 25-31.
[4]	孙力. 区块链+在线教育资源联盟信息保护机制研究与应用[J]. 信息网络安全, 2021, 21(9): 32-39.
[5]	江皓臻, 江苾菲, 贺朗月, 单亦伟. 基于THD89的智能密码钥匙设计与实现[J]. 信息网络安全, 2021, 21(9): 40-45.
[6]	弋晓洋, 张健. 基于图像的网络钓鱼邮件检测方法研究[J]. 信息网络安全, 2021, 21(9): 52-58.
[7]	李彦霖, 蔡满春, 芦天亮, 席荣康. 遗传算法优化CNN的网站指纹攻击方法[J]. 信息网络安全, 2021, 21(9): 59-66.
[8]	陈庆港, 杜彦辉, 韩奕, 刘翔宇. 基于深度可分离卷积的物联网设备识别模型[J]. 信息网络安全, 2021, 21(9): 67-73.
[9]	郑海潇, 文斌. 基于图卷积网络的比特币非法交易识别方法[J]. 信息网络安全, 2021, 21(9): 74-79.
[10]	吴克河, 程瑞, 郑碧煌, 崔文超. 电力物联网安全通信协议研究[J]. 信息网络安全, 2021, 21(9): 8-15.
[11]	张永棠. 一种基于安全区域的WSN流量分析聚合方法[J]. 信息网络安全, 2021, 21(9): 80-89.
[12]	杨晓琪, 白利芳, 唐刚. 基于DSMM模型的数据安全评估模型研究与设计[J]. 信息网络安全, 2021, 21(9): 90-95.
[13]	靳姝婷, 何泾沙, 朱娜斐, 潘世佳. 基于本体推理的隐私保护访问控制机制研究[J]. 信息网络安全, 2021, 21(8): 52-61.
[14]	鲍亮, 俞少华, 唐晓婷. 基于马尔可夫链的Web业务安全分析预警[J]. 信息网络安全, 2021, 21(8): 91-96.
[15]	李群, 董佳涵, 关志涛, 王超. 一种基于聚类分类的物联网恶意攻击检测方法[J]. 信息网络安全, 2021, 21(8): 82-90.