广西师范大学学报（自然科学版） ›› 2023, Vol. 41 ›› Issue (4): 1-11.doi: 10.16088/j.issn.1001-6600.2022122001

• 综述 •    下一篇

几类纠错码及其相关McEliece密码体制

李志豪1, 吴严生1*, 张钰芃2   

  1. 1.南京邮电大学计算机学院/软件学院/网络空间安全学院, 江苏南京 210023;
    2.南京航空航天大学计算机科学与技术学院/人工智能学院/软件学院, 江苏南京 210016
  • 收稿日期:2022-12-20 修回日期:2023-03-06 出版日期:2023-07-25 发布日期:2023-09-06
  • 通讯作者: 吴严生(1989—),男,安徽安庆人,南京邮电大学副教授,博士。E-mail:yanshengwu@njupt.edu.cn
  • 基金资助:
    国家自然科学基金青年基金(12101326);江苏省自然科学基金青年基金(BK20210575);江苏省高等学校基础科学(自然科学)面上项目(21KJB110005);南京市留学人员科技创新项目择优资助、南京邮电大学华礼人才计划、综合业务网理论及关键技术国家重点实验室开放课题(ISN23-22)

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

PDF (PC)

385

摘要： 随着量子计算机的迅速发展,抗量子攻击密码算法俨然成为密码学的研究热点。基于纠错码的McEliece公钥加密体制由Robert McEliece于1978年提出,是一种非对称抗量子攻击加密算法。本文首先介绍几种常见的纠错码——Reed-Solomon码、Goppa码、Twisted Reed-Solomon码的定义与基本性质,系统分析线性码的纠错译码算法;其次,详细阐述基于纠错码的McEliece公钥加密体制的加解密过程,并从NP-Hard问题对该加密体制进行安全性分析;最后,在前人研究成果的基础上,结合最近研究热点,提出几点思考和一些公开问题,为未来的研究提供参考。

关键词: 纠错码, Goppa码, Reed-Solomon码, Twisted Reed-Solomon码, McEliece加密体制, 纠错译码算法

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

中图分类号:  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] 徐久成, 李晓艳, 李双群, 张灵均. 基于相容粒的多层次纹理特征图像检索方法[J]. 广西师范大学学报（自然科学版）, 2011, 29(1): 186 -187 .
[2] 白德发, 徐欣, 王国长. 函数型数据广义线性模型和分类问题综述[J]. 广西师范大学学报（自然科学版）, 2022, 40(1): 15 -29 .
[3] 曾庆樊, 秦永松, 黎玉芳. 一类空间面板数据模型的经验似然推断[J]. 广西师范大学学报（自然科学版）, 2022, 40(1): 30 -42 .
[4] 张喜龙, 韩萌, 陈志强, 武红鑫, 李慕航. 面向复杂数据流的集成分类综述[J]. 广西师范大学学报（自然科学版）, 2022, 40(4): 1 -21 .
[5] 童凌晨, 李强, 岳鹏鹏. 基于CiteSpace的喀斯特土壤有机碳研究进展[J]. 广西师范大学学报（自然科学版）, 2022, 40(4): 22 -34 .
[6] 王党树, 仪家安, 董振, 杨亚强, 邓翾. 单周期控制的带纹波抑制单元无桥Boost PFC变换器研究[J]. 广西师范大学学报（自然科学版）, 2022, 40(4): 47 -57 .
[7] 喻思婷, 彭靖静, 彭振赟. 矩阵方程的秩约束最小二乘对称半正定解及其最佳逼近[J]. 广西师范大学学报（自然科学版）, 2022, 40(4): 136 -144 .
[8] 覃城阜, 莫芬梅. C3-和C4-临界连通图的结构[J]. 广西师范大学学报（自然科学版）, 2022, 40(4): 145 -153 .
[9] 阴玉栋, 柯善喆, 黄家艳, 邓梦湘, 刘观艳, 程克光. 1,3-二溴丙烷与醇羧酸和胺一锅法生成烯丙基化合物[J]. 广西师范大学学报（自然科学版）, 2022, 40(4): 154 -161 .
[10] 杜丽波, 李金玉, 张晓, 李永红, 潘卫东. 毛红椿皮的化学成分及生物活性研究[J]. 广西师范大学学报（自然科学版）, 2022, 40(4): 162 -172 .
版权所有 © 广西师范大学学报（自然科学版）编辑部
地址：广西桂林市三里店育才路15号　邮编：541004
电话：0773-5857325　E-mail: gxsdzkb@mailbox.gxnu.edu.cn
本系统由北京玛格泰克科技发展有限公司设计开发