基于BRLWE的物联网后量子加密技术研究

doi:10.11959/j.issn.2096-109x.2022024

摘要/Abstract

摘要：

随着量子计算机的发展，现有的公钥加密体系无法保障物联网通信的安全性。后量子加密算法所基于的数学难题目前还不能被量子计算机攻破，因此具备良好的抗量子安全性，尤其是基于格的公钥密码体制，有望成为下一代公钥加密体系的主流。然而，后量子加密算法存在计算量大、存储空间大等问题，如果将其直接应用于物联网终端的轻量级设备中，会降低物联网环境的通信效率。为了更好地保护物联网通信安全，保障物联网通信效率，提出了Sym-BRLWE（symmetrical binary RLWE）后量子加密算法。该算法在基于二进制环上容错学习（BRLWE，binary ring-learning with errors）问题的加密算法的基础上，改进了离散均匀分布上的随机数选取方式和多项式乘法的计算方式，从而满足物联网通信的效率要求，增加了加密安全性防护性措施以保证算法在取得高效率的同时具有高安全性，更加适应于物联网轻量设备。安全性分析表明，Sym-BRLWE加密算法具有高安全性，从理论上能够抵抗格攻击、时序攻击、简单能量分析和差分能量分析；仿真实验结果表明，Sym-BRLWE加密算法具有通信效率高的优势，加密解密效率高且密钥尺寸小，在模拟8 bit微型设备的二进制运算环境下，选择140 bit的抗量子安全级别参数时，相较于其他已有的基于BRLWE的加密算法，同等加密条件下Sym-BRLWE加密算法能够在加密总时间上减少30%～40%。

关键词: 后量子密码, 物联网, 公钥加密, 基于格的加密, 环上容错学习问题

Abstract:

With the development of quantum computers, the classical public key encryption system is not capable enough to guarantee the communication security of internet of things (IoT).Because the mathematical puzzles which post-quantum encryption algorithms are based on cannot yet be broken by quantum computers, these new algorithms have good anti-quantum computing security.In particular, the lattice-based cryptography is expected to become the main technology of the next generation public key cryptosystem.However, post-quantum encryption algorithms have the disadvantages of large amount of computation and high storage space.The communication efficiency of IoT will be affected if post-quantum encryption algorithms are directly applied to the lightweight device under IoT environment.In order to better guarantee the communication security and improve the commutation efficiency of IoT, Sym-BRLWE (symmetrical binary RLWE) encryption scheme was proposed.Sym-BRLWE was improved from the existing post-quantum encryption scheme based on BRLWE (binary ringlearning with errors) problem.Specifically, Sym-BRLWE encryption algorithm met the efficiency requirements of IoT via improving the random number selection on the discrete uniform distribution and the calculation of the polynomial multiplication.Sym-BRLWE encryption algorithm achieved high efficiency and high security via adding encryption security precautions, then it is more suitable for IoT lightweight devices.From the security analysis, the proposed Sym-BRLWE encryption scheme had high security.It could theoretically resist lattice attacks, timing attacks, simple power analysis (SPA) and differential power analysis (DPA).From simulation experiments, which were carried out in a binary computing environment simulating an 8-bit micro-device, the proposed Sym-BRLWE encryption scheme has high efficiency and small key size in encryption and decryption.It could reduce the total encryption time by 30% to 40% when compared with other BRLWE-based encryption schemes with the parameter selection of the 140 bit quantum security level.

Key words: post-quantum cryptography, internet of things, public key encryption, lattice-based encryption system, ring-learning with errors

中图分类号:

TP393

高艺恬, 陈立全, 屠天扬, 高原, 陈芊叶. 基于BRLWE的物联网后量子加密技术研究[J]. 网络与信息安全学报, 2022, 8(5): 140-149.

Yitian GAO, Liquan CHEN, Tianyang TU, Yuan GAO, Qianye CHEN. Post-quantum encryption technology based on BRLWE for internet of things[J]. Chinese Journal of Network and Information Security, 2022, 8(5): 140-149.

图/表 6

表1

Sym-BRLWE加密时间Table 1 Encryption time of Sym-BRLWE"

算法环节	理论时间
密钥生成	$9 n T_{random} + T_{add} + T_{mul}$
加密	$n T_{shift} + 3 n T_{random} + (2 + m) T_{add} + 2 T_{mul}$
解密	$n T_{shift} + T_{mul} + T_{add}$

表1

表2

表3

表4

表5

图1

参考文献 23

[1]	SCHNEIER B . IoT cybersecurity:what's plan B[R]. 2017.
[2]	朱小伶 . 2020年量子计算技术发展综述[J]. 无人系统技术, 2021,4(2): 26-32.
	ZHU X L . Survey of quantum computing technology in 2020[J]. Unmanned Systems Technology, 2021,4(2): 26-32.
[3]	张成磊, 付玉龙, 李晖 ,等. 6G网络安全场景分析及安全模型研究[J]. 网络与信息安全学报, 2021,7(1): 28-45.
	ZHANG C L , FU Y L , LI H ,et al. Research on security scenarios and security models for 6G networking[J]. Chinese Journal of Network and Information Security, 2021,7(1): 28-45.
[4]	陈璐, 汤红波, 游伟 ,等. 移动边缘计算安全防御研究[J]. 网络与信息安全学报, 2021,7(1): 130-142.
	CHEN L , TANG H B , YOU W ,et al. Research on security defense of mobile edge computing[J]. Chinese Journal of Network and Information Security, 2021,7(1): 130-142.
[5]	LYUBASHEVSKY V , PEIKERT C , REGEV O . On ideal lattices and learning with errors over rings[M]. Advances in Cryptology –EUROCRYPT 2010. Berlin,Heidelberg: Springer Berlin Heidelberg, 2010: 1-23.
[6]	P?PPELMANN T , GüNEYSU T , . Towards efficient arithmetic for lattice-based cryptography on reconfigurable hardware[M]. Progress in Cryptology-LATINCRYPT 2012. Berlin,Heidelberg: Springer Berlin Heidelberg, 2012: 139-158.
[7]	ROY S S , VERCAUTEREN F , MENTENS N ,et al. Compact ring-LWE cryptoprocessor[C]// Cryptographic Hardware and Embedded Systems – CHES 2014. 2014: 371-391.
[8]	FRITZMANN T , SEPúLVEDA J ,, . Efficient and flexible low-power NTT for lattice-based cryptography[C]// Proceedings of 2019 IEEE International Symposium on Hardware Oriented Security and Trust. 2019: 141-150.
[9]	DE CLERCQ R , ROY S S , VERCAUTEREN F ,et al. Efficient software implementation of ring-LWE encryption[C]// Proceedings of Design,Automation ＆ Test in Europe Conference ＆ Exhibition (DATE). 2015: 339-344.
[10]	BOORGHANY A , SARMADI S B , JALILI R . On constrained implementation of lattice-based cryptographic primitives and schemes on smart cards[J]. ACM Transactions on Embedded Computing Systems, 2015,14(3): 1-25.
[11]	LIU Z , AZARDERAKHSH R , KIM H ,et al. Efficient software implementation of ring-LWE encryption on IoT processors[J]. IEEE Transactions on Computers, 2020,69(10): 1424-1433.
[12]	SEO H , KWON H , KWON Y ,et al. Fast number theoretic transform for ring-LWE on 8-bit AVR embedded processor[J]. Sensors, 2020,20(7): 2039.
[13]	BUCHMANN J , G?PFERT F , GüNEYSU T ,et al. High- performance and lightweight lattice-based public-key encryption[C]// Proceedings of the 2nd ACM International Workshop on IoT Privacy,Trust,and Security. 2016: 2-9.
[14]	AYSU A , ORSHANSKY M , TIWARI M . Binary Ring-LWE hardware with power side-channel countermeasures[C]// Proceedings of 2018 Design,Automation ＆ Test in Europe Conference ＆ Exhibition (DATE). 2018: 1253-1258.
[15]	EBRAHIMI S , BAYAT-SARMADI S , MOSANAEI-BOORANI H . Post-quantum cryptoprocessors optimized for edge and resource-constrained devices in IoT[J]. IEEE Internet of Things Journal, 2019,6(3): 5500-5507.
[16]	EBRAHIMI S , BAYAT-SARMADI S . Lightweight and DPA-resistant post-quantum cryptoprocessor based on binary ring-LWE[C]// Proceedings of 2020 20th International Symposium on Computer Architecture and Digital Systems (CADS). 2020: 1-6.
[17]	EBRAHIMI S , BAYAT-SARMADI S , . Lightweight and fault-resilient implementations of binary ring-LWE for IoT devices[J]. IEEE Internet of Things Journal, 2020,7(8): 6970-6978.
[18]	XIE J F , HE P Z , WEN W J . Efficient implementation of finite field arithmetic for binary ring-LWE post-quantum cryptography through a novel lookup-table-like method[C]// Proceedings of 2021 58th ACM/IEEE Design Automation Conference. 2021: 1279-1284.
[19]	HE P Z , GUIN U , XIE J F . Novel low-complexity polynomial multiplication over hybrid fields for efficient implementation of binary ring-LWE post-quantum cryptography[J]. IEEE Journal on Emerging and Selected Topics in Circuits and Systems, 2021,11(2): 383-394.
[20]	FERNáNDEZ-CARAMéS T M . From pre-quantum to post-quantum IoT security:a survey on quantum-resistant cryptosystems for the Internet of Things[J]. IEEE Internet of Things Journal, 2020,7(7): 6457-6480.
[21]	BUCHMANN J , G?PFERT F , PLAYER R ,et al. On the hardness of LWE with binary error:Revisiting the hybrid lattice-reduction and meet-in-the-middle attack[C]// International Conference on Cryptology in Africa. 2016: 24-43.
[22]	PARK A , HAN D G . Chosen ciphertext simple power analysis on software 8-bit implementation of ring-LWE encryption[C]// Proceedings of 2016 IEEE Asian Hardware-Oriented Security and Trust (AsianHOST). 2016: 1-6.
[23]	KOCHER P , JAFFE J , JUN B ,et al. Introduction to differential power analysis[J]. Journal of Cryptographic Engineering, 2011,1(1): 5-27.

数据内容	存储空间/bit
私钥	n
公钥	16n
明文	mn
密文	16 mn

加密方案	安全级别/bit	n	q
RBLWE-I	84/73	256	256
RBLWE-II	190/140	512	256
注：安全级别中的“/”前后数字表示表示传统安全级别和量子安全级别。

加密算法	参考文献	密钥生成时间/ms	加密时间/ms	解密时间/ms
R-BinLWE-I	文献[13]	21.54	57.525	41.94
R-BinLWE -II	文献[13]	78.455	144.18	69.705
B-RLWE-I	文献[14]	50.275	92.365	92.765
B-RLWE-II	文献[14]	201.315	379.715	181.745
InvRBLWE-I	文献[16]	59.8	112.735	112.065
InvRBLWE-II	文献[16]	237.86	446.9	218.275
Sym-BRLWE-I	本文算法	47.89	84.795	71.65
Sym-BRLWE-II	本文算法	148.655	263.005	122.74

加密算法	参考文献	私钥大小/byte	公钥大小/byte	密文大小/byte
R-BinLWE-I	文献[13]	511	2 051.82	2 740.15
R-BinLWE -II	文献[13]	1023	4 111.325	3 652.6
B-RLWE-I	文献[14]	127	2 051.97	2 740.98
B-RLWE-II	文献[14]	255	4 110.85	3 655.005
InvRBLWE-I	文献[16]	127	2 051.46	2 739.625
InvRBLWE-II	文献[16]	255	4 110.91	3 655.685
Sym-BRLWE-I	本文算法	127	2 053.495	2 740.245
Sym-BRLWE-II	本文算法	255	4 112.455	3 656.85