基于Polar码改进的McEliece密码体制

doi:10.3969/j.issn.1671-1122.2020.01.001

摘要/Abstract

摘要：

随着量子计算机对计算能力的提高,RSA和椭圆曲线密码等经典密码方案在量子计算机时代已经不再安全,基于编码的密码方案具有抵抗量子计算的优势,在未来具有良好的应用前景。文章研究极化码的极化性质,改进密钥存储方法,提出了基于Polar码改进的McEliece密码体制。改进后的编码加密方案不再存储整个矩阵,而是存储冻结比特对应的矩阵,其密钥大小比原始密码方案减少约63.36%。采用连续消除（SC）译码算法,译码复杂度较低,并通过实验证明了提出的密码方案达到140 bit的安全级别,可以抵抗目前已知存在的各种攻击。最后,文章进一步阐述了基于Polar码的密码方案未来的发展方向,拓宽了极化码在编码密码方案中的应用。

关键词: 编码, Polar码, McEliece密码体制, SC译码算法

Abstract:

With the improvement of computing power of quantum computers, classical cryptography schemes such as RSA and elliptic curve cryptography are no longer secure in the era of quantum computers. The code-based cryptography has the advantage of resisting quantum computing and has a good application prospect in future. This paper studies the polarization properties of Polar codes, improves the key storage method, and proposes McEliece system based on Polar codes. The improved encoding encryption scheme no longer stores the whole matrix, but stores the matrix corresponding to frozen bits. The key size is about 63.36% smaller than that of the original cryptographic scheme. The SC decoding algorithm adopted in this paper has a low decoding complexity, and it is proved that the proposed cryptography scheme reaches the security level of 140 bits and can resist various attacks that are known to exist at present. Finally, the future development direction of Polar code-based cryptography scheme is further elaborated, and the application of Polar code in coding cryptography scheme is broadened.

Key words: coding, Polar codes, McEliece cryptosystem, SC decoding algorithm

中图分类号:

TP309

韩益亮, 李喆, 李鱼. 基于Polar码改进的McEliece密码体制[J]. 信息网络安全, 2020, 20(1): 1-8.

HAN Yiliang, LI Zhe, LI Yu. An Improved McEliece Cryptosystem Based on Polar Code[J]. Netinfo Security, 2020, 20(1): 1-8.

图/表 3

参考文献 30

[1]	RIVEST R L, SHAMIR A, ADLEMAN L.A Method for Obtaining Digital Signatures and Public-Key Cryptosystems[J]. Communications of the ACM, 1978, 21(2): 120-126.
[2]	ICART T, CORON J S. Cryptography on An Elliptical Curve: U. S. Patent 10, 027, 483[P].2018-7-17.
[3]	CHEN Yuhang, JIAHuihui, JIANG Liying, et al.ECC Scanning Attack Based on Grover Algorithm[J]. Netinfo Security, 2016, 16(2): 28-32.
[4]	CHEN L, JORDAN S, et al.Report on Post-Quantum Cryptography[M]. Washington: US Department of Commerce, National Institute of Standards and Technology, 2016.
[5]	ALAGIC G, ALPERIN J, et al.Status Report on the First Round of the NIST Post-Quantum Cryptography Standardization Process[M]. Washington: US Department of Commerce, National Institute of Standards and Technology, 2019.
[6]	MCELIECE R J.A Public-key Cryptosystem Based on Algebraic Coding Theory[J]. DSN Progress Report, 1978, 42(44): 114-116.
[7]	CHIZHOV I V, BORODIN M A.The Failure of McEliece PKC Based on Reed-Muller Codes[J]. IACR Cryptology ePrint Archive, 2013, 13(8): 287.
[8]	BALDI M, BIANCHI M, CHIARALUCE F, et al.Enhanced Public Key Security for the Mceliece Cryptosystem[J]. Journal of Cryptology, 2016, 29(1): 1-27.
[9]	LIU Mingye, HAN Yiliang, YANG Xiaoyuan.Research on Signage Scheme Based on Quasi-Cyclic Low-Density Parity Code[J]. Netinfo Security, 2016, 16(11): 66-72.
[10]	MAURICH I V, ODER T, GÜNEYSU T. Implementing QC-MDPC Mceliece Encryption[J]. ACM Transactions on Embedded Computing Systems(TECS), 2015, 14(3): 44.
[11]	NIEDERREITER H.Knapsack-Type Cryptosystems and Algebraic Coding Theory[J]. Prob. Control and Inf. Theory, 1986, 15(2): 159-166.
[12]	SHRESTHA S R, KIM Y S.New Mceliece Cryptosystem Based on Polar Codes as A Candidate for Post-Quantum Cryptography[C]//IEEE. 2014 14th International Symposium on Communications and Information Technologies(ISCIT), September 24-26, 2014, Incheon, South Korea. New York: IEEE, 2014: 368-372.
[13]	RASHWAN H, GABIDULIN E M.Security of The GPT Cryptosystem and Its Applications to Cryptography[J]. Security and Communication Networks, 2011, 4(8): 937-946.
[14]	GABORIT P, ZÉMOR G. On the Hardness of the Decoding and the Minimum Distance Problems for Rank Codes[J]. IEEE Transactions on Information Theory, 2016, 62(12): 7245-7252.
[15]	ARIKAN E.Channel Polarization: A Method for Constructing Capacity Achieving Codes for Symmetric Binary-Input Memoryless Channels[J]. IEEE Transactions on Information Theory, 2009, 55(7): 3051-3073.
[16]	MAHDAVIFAR H, VARDY A.Achieving the Secrecy Capacity of Wiretap Channels Using Polar Codes[J]. IEEE Transactions on Information Theory, 2011, 57(10): 6428-6443.
[17]	HOOSHMAND R, AREF M R, EGHLIDOS T.Secret Key Cryptosystem Based on Non-Systematic Polar Codes[J]. Wireless Personal Communications, 2015, 84(2): 1345-1373.
[18]	HOOSHMAND R, AREF M R.Polar Code-Based Secure Channel Coding Scheme with Small Key Size[J]. IET Communications, 2017, 11(15): 2357-2361.
[19]	HOOSHMAND R, AREF M R, EGHLIDOS T.Physical Layer Encryption Scheme Using Finite Length Polar Codes[J]. IET Communications, 2015, 9(15): 1857-1866.
[20]	HOOSHMAND R, AREF M R.Efficient Polar Code-Based Physical Layer Encryption Scheme[J]. IEEE Wireless Communications Letters, 2017, 6(6): 710-713.
[21]	HOOSHMAND R, SHOOSHTARI M K, EGHLIDOS T, et al.Reducing the Key Length of McEliece Cryptosystem Using Polar Codes[C]// IEEE. 2014 11th International ISC Conference on Information Security and Cryptology, September 3-4, 2014, Tehran, Iran. New York: IEEE, 2014: 104-108.
[22]	TILLICH J P.Cryptanalysis of the McEliece Public Key Cryptosystem Based on Polar Codes[C]// Springer. Post-Quantum Cryptography: 7th International Workshop, PQCrypto 2016, February 24-26, 2016, Fukuoka, Japan. Switzerland: Springer, 2016: 118-143.
[23]	BERNSTEIN D J, LANGE T, PETERS C.Wild McEliece[C]// Springer. International Workshop on Selected Areas in Cryptography, August 12-13, Waterloo, ON, Canada. Berlin: Springer, 2010: 143-158.
[24]	CAYREL P L, GUEYE C T, NDIAYE O, et al.Critical Attacks in Code-Based Cryptography[J]. International Journal of Information and Coding Theory, 2015, 3(2): 158-176.
[25]	FAUGERE J C, GAUTHIER V, OTMANI A, et al.A Distinguisher for High-Rate McEliece Cryptosystems[J]. IEEE Transactions on Information Theory, 2013, 59(10): 6830-6844.
[26]	JOUNDAN I A, NOUH S, NAMIR A.A New Powerful Scheme Based on Self Invertible Stabilizer Multiplier Permutation to Find the Minimum Distance for large BCH Codes[J]. American Journal of Computer Science and Technology, 2018, 1(2): 39-43.
[27]	WANG Y. Method and Apparatus for Public Key Encryption Scheme RLCE and IND-CCA2 Security: U. S. Patent Application 15/840, 121[P].2018-6-21.
[28]	KOSOLAPOV Y V, TURCHENKO O Y.On the Construction of A Semantically Secure Modification of the McEliece Cryptosystem[J]. 2019,19(45): 33-43.
[29]	GUO Q, JOHANSSON T, WAGNER P S.A Key Recovery Reaction Attack on QC-MDPCcodes[J]. IEEE Transactions on Information Theory, 2018, 65(3): 1845-1861.
[30]	BALDI M, SANTINI P, CANCELLIERI G.Post-Quantum Cryptography Based on Codes: State of The Art and Open Challenges[C]// IEEE. 2017 AEIT International Annual Conference, September 20-22. 2017, Cagliari, Italy. New York: IEEE, 2017: 1-6.

比较方案	Code	(n,k)	M_pub	M_sec
McEliece方案	Goppa	(1024,524)	67.07 KB	102.5 KB
本文方案	Polar	(1024,768)	24.58 KB	4.42 KB