Journal of Guangxi Normal University(Natural Science Edition) ›› 2023, Vol. 41 ›› Issue (4): 1-11.doi: 10.16088/j.issn.1001-6600.2022122001

    Next Articles

Several Kinds of Error-Correcting Codes and Related McEliece Cryptosystem

LI Zhihao1, WU Yansheng1*, ZHANG Yupeng2   

  1. 1. School of Computer Science, Nanjing University of Posts and Telecommunications, Nanjing Jiangsu 210023, China;
    2. Colloge of Computer Science and Technology/Colloge of ArtificialIntelligence/Colloge of Software, Nanjing University of Aeronautics and Astronautics, Nanjing Jiangsu 210016, China
  • Received:2022-12-20 Revised:2023-03-06 Online:2023-07-25 Published:2023-09-06

Abstract: With the rapid development of quantum computers, cryptographic algorithms against quantum attacks have become a research hotspot in cryptography. McEliece encryption system based on error-correcting codes, proposed by Robert McEliece in 1978, is an asymmetric encryption algorithm against quantum attacks. In this paper, firstly, the definitions and basic properties of several common error-correcting codes, such as Reed-Solomon codes, Goppa codes, and Twisted Reed-Solomon codes are introduced. Secondly, the encryption and decryption process of McEliece public-key encryption system based on error-correcting codes is described in detail, and the security of the encryption system is analyzed from the perspective of NP-Hard problems. Finally, on the basis of previous research results, combined with recent research hotspots, several considerations and open problems are proposed to point out the direction for future research.

Key words: error-correcting codes, Goppa codes, Reed-Solomon codes, Twisted Reed-Solomon codes, McEliece encryption system, error-correcting decoding algorithm

CLC Number:  TN918.3
[1] SHANNON C E. Communication theory of secrecy systems[J]. The Bell System technical Journal, 1949, 28(4): 656-715.
[2] DIFFIE W, HELLMAN M E. New directions in cryptography[M]//SLAYTON R. Democratizing Cryptography: the Work of Whitfield Diffie and Martin Hellman. New York: Association for Computing Machinery, 2022: 365-390.
[3] 陈仲津, 张先俊. 有纠错能力的PKC密码体制:CS码及其在电报通信中的应用[J]. 南京邮电学院学报, 1989, 9(1): 30-37.
[4] 十三届全国人大常委会. 十三届全国人大常委会第十四次会议表决通过密码法[EB/OL].(2019-10-26)[2022-12-16]. https://news.ifeng.com/c/7r5T83aT5Qe.
[5] 巫光福, 江林伟. 抗量子密码学综述[J]. 长江信息通信, 2021, 34(7): 55-60.
[6] MCELIECE R J. A public-key cryptosystem based on algebraic coding theory: DSN Progress Report[R]. Washington, D.C.:NASA, 1978: 114-116.
[7] 冯克勤. 纠错码的代数理论[M]. 北京: 清华大学出版社, 2005.
[8] 朱陆费. 基于纠错码的公钥密码体制研究[D]. 南京: 南京邮电大学, 2009.
[9] 杨淑娣, 岳勤. 一类线性码的完全重量分布[J]. 计算机工程与科学, 2019, 41(2): 281-285.
[10] 陈恭亮. 信息安全数学基础[M]. 北京: 清华大学出版社, 2004.
[11] REED I S, SOLOMON G. Polynomial codes over certain finite fields[J]. Journal of the Society for Industrial and Applied Mathematics, 1960, 8(2): 300-304.
[12] 杨庚,章韵,成卫青,等. 计算机通信与网络[M]. 北京: 清华大学出版社, 2009.
[13] LóPEZH H, MATTHEWS G L. Multivariate Goppa codes[J]. IEEE Transactions on Information Theory, 2023, 69(1): 126-137.
[14] LAVAUZELLE J, RENNER J. Cryptanalysis of a system based on twisted Reed-Solomon codes[J]. Designs, Codes and Cryptography, 2020, 88(7): 1285-1300.
[15] BLATEYANG. NP问题、NP难问题(NPH)和NP完全问题(NPC)理解[EB/OL].(2017-10-28)[2022-12-16]. https://blog.csdn.net/Blateyang/article/details/78375885.
[16] DATABATMAN. 算法中的P问题、NP问题、NP完全问题和NP难问题[EB/OL]. (2015-10-21)[2022-12-16]. https://blog.csdn.net/databatman/article/details/49304295.
[17] 曹东, 赵生妹, 宋耀良. 一种基于量子准循环LDPC码的McEliece公钥密码算法[J]. 南京邮电大学学报(自然科学版), 2011, 31(2): 64-68.
[18] 谷利泽, 郑世慧, 杨义先. 现代密码学教程[M]. 北京: 北京邮电大学出版社, 2009.
[19] BERSON T A. Failure of the McEliece public-key cryptosystem under message-resend and related-message attack[J]. Lecture Notes in Computer Science, 1997, 1294: 213-220.
[20] 李喆, 韩益亮, 李鱼, 等. 基于编码的加密体制综述[J]. 国防科技大学学报, 2020, 42(4): 134-142.
[21] RYAN J. A. Counting extended irreducible binary quartic Goppa codes[J]. IEEE Transactions on Information Theory, 2015, 61(3): 1174-1178.
[22] HUANG D T, YUE Q. Extended irreducible binary sextic Goppa codes[J]. IEEE Transactions on Information Theory, 2022, 68(1): 230-237.
[23] CHEN B C, ZHANG G H. The number of extended irreducible binary Goppa codes[EB/OL].(2022-04-05)[2022-12-16].https://arxiv.org/abs/2204.02083V1.
[24] THIONG-LY J A. Automorphisms of two families of extended non binary cyclic Goppa codes[J]. Lecture Notes in Computer Science, 1984, 229:112-121.
[25] LI Z, XING C P, YEO S L. Reducing the key size of McEliece cryptosystem from automorphism-induced Goppa codes via permutations[J]. Lecture Notes in Computer Science, 2019, 11443:599-617.
[26] BERLEKAMP E. Goppa codes[J]. IEEE Transactions on Information Theory, 1973, 19(5): 590-592.
[27] SUGIYAMA Y, KASAHARA M, HIRASAWA S. et al, A method for solving key equation for decoding Goppa codes[J]. Information and Control, 1975, 27(1): 87-99.
[28] PATTERSON N. The algebraic decoding of Goppa codes[J]. IEEE Transactions on Information Theory, 1975, 21(2): 203-207.
[29] LIM S, LEE H S, CHOI M. An efficient decoding of Goppa codes for the McEliece cryptosystem[J]. Fundamenta Informaticae, 2014, 133(4): 387-397.
[30] SHEN B Z, TZENG K K. Decoding geometric Goppa codes up to designed minimum distance by solving a key equation in a ring[J]. IEEE Transactions on Information Theory, 1995, 41(6): 1694-1702.
[31] PORTER S C, SHEN B Z, PELLIKAAN R. Decoding geometric Goppa codes using an extra place[J]. IEEE Transactions on Information Theory, 1992, 38(11): 1663-1676.
[32] HEYDTMANN A E. Sudan-decoding generalized geometric Goppa codes[J]. Finite Fields and Their Applications, 2003, 9(3): 267-285.
[33] LIU H D L, PIRCHER S, ZEH A. et al, Decoding of (interleaved) generalized Goppa codes[C]. //2021 IEEE International Symposium on Information Theory (ISIT). Piscataway, NJ:IEEE, 2021: 664-669.
[34] SUI J Z, ZHU X M, SHI X Y. MDS and near-MDS codes via twisted Reed-Solomon codes[J]. Designs,Codes and Cryptography, 2022, 90(8): 1937-1958.
[35] HUANG D T, YUE Q, NIU Y F. MDS or NMDS LCD codes from twisted Reed-Solomon codes[J]. Cryptography and Communications, 2023, 15(2): 221-237.
[36] CARLET C, MESNAGER S, TANG C M. et al. Euclidean and Hermitian LCD MDS codes[J]. Designs,Codes and Cryptography, 2018, 86(11): 2605-2618.
[37] WU Y S, HYUN J Y, LEE Y. New LCD MDS codes of non-Reed-Solomon type[J]. IEEE Transactions on Information Theory, 2021, 67(8): 5069-5078.
[38] FAUGèRE J C, OTMANI A, PERRET L. et al. Folding alternant and Goppa codes with non-trivial automorphism groups[J]. IEEE Transactions on Information Theory, 2016, 62(1): 184-198.
[39] HEYSE S. Implementation of McEliece based on quasi-dyadic Goppa codes for embedded devices[J]. Lecture Notes in Computer Science, 2011, 7071: 143-162.
No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[1] XU Jiu-cheng, LI Xiao-yan, LI Shuang-qun, ZHANG Ling-jun. Feature Images Retrieval Method of Tolerance Granular-basedMulti-level Texture[J]. Journal of Guangxi Normal University(Natural Science Edition), 2011, 29(1): 186 -187 .
[2] BAI Defa, XU Xin, WANG Guochang. Review of Generalized Linear Models and Classification for Functional Data[J]. Journal of Guangxi Normal University(Natural Science Edition), 2022, 40(1): 15 -29 .
[3] ZENG Qingfan, QIN Yongsong, LI Yufang. Empirical Likelihood Inference for a Class of Spatial Panel Data Models[J]. Journal of Guangxi Normal University(Natural Science Edition), 2022, 40(1): 30 -42 .
[4] ZHANG Xilong, HAN Meng, CHEN Zhiqiang, WU Hongxin, LI Muhang. Survey of Ensemble Classification Methods for Complex Data Stream[J]. Journal of Guangxi Normal University(Natural Science Edition), 2022, 40(4): 1 -21 .
[5] TONG Lingchen, LI Qiang, YUE Pengpeng. Research Progress and Prospects of Karst Soil Organic Carbon Based on CiteSpace[J]. Journal of Guangxi Normal University(Natural Science Edition), 2022, 40(4): 22 -34 .
[6] WANG Dangshu, YI Jiaan, DONG Zhen, YANG Yaqiang, DENG Xuan. Research on Bridgeless Boost PFC Converter with Ripple Suppression Unit Based on Single Cycle Control[J]. Journal of Guangxi Normal University(Natural Science Edition), 2022, 40(4): 47 -57 .
[7] YU Siting, PENG Jingjing, PENG Zhenyun. Rank Constraint Least Square Symmetric Semidefinite Solutions and Its Optimal Approximation of the Matrix Equation[J]. Journal of Guangxi Normal University(Natural Science Edition), 2022, 40(4): 136 -144 .
[8] QIN Chengfu, MO Fenmei. Structure ofC3-and C4-Critical Graphs[J]. Journal of Guangxi Normal University(Natural Science Edition), 2022, 40(4): 145 -153 .
[9] YIN Yudong, KE Shanzhe, HUANG Jiayan, DENG Mengxiang, LIU Guanyan, CHENG Keguang. One-pot Generation of Allylated Products from Alcohols, Carboxylic Acids and Amines with 1,3-Dibromopropane by Sodium Hydride[J]. Journal of Guangxi Normal University(Natural Science Edition), 2022, 40(4): 154 -161 .
[10] DU Libo, LI Jinyu, ZHANG Xiao, LI Yonghong, PAN Weidong. Chemical Constituents and Biological Activity from the Bark of Toona ciliata var. pubescens[J]. Journal of Guangxi Normal University(Natural Science Edition), 2022, 40(4): 162 -172 .