An Improved McEliece Cryptosystem Based on Polar Code

doi:10.3969/j.issn.1671-1122.2020.01.001

Abstract

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

CLC Number:

TP309

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

Figures/Tables 3

References 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