一种改进的基于奇偶校验码的McEliece变型方案

————————————————————————————————————————————————一种改进的基于奇偶校验码的McEliece变型方案作者李梦东，孙玉情，韦依儿，程思培机构北京电子科技学院；西安电子科技大学通信工程学院DOI10.3969/j.issn.1001-3695.2018.04.0349基金项目北京市支持中央高校共建项目——青年英才计划项目；中央高校基本科研业务费专项资金资助项目（2017CL06）预排期卷《计算机应用研究》2019年第36卷第11期摘要McEliece公钥加密体制是基于编码理论的公钥密码体制，其安全性可以规约到一般线性码译码问题，可以抵抗量子攻击。提出了一种改进的基于准循环中密度奇偶校验（QC-MDPC）码和准循环低密度奇偶校验（QC-LDPC）码的McEliece变型方案。主要改进是将QC-LDPC码和QC-MDPC码的奇偶校验矩阵结合作为私钥，生成二者的级联码字应用于McEliece变型方案，并且给出了改进的译码算法。分析表明在80bit安全下该体制密钥量小且实现的复杂度低，能抵抗最近提出的分别针对QC-MDPC和QC-LDPC体制的密钥恢复攻击。关键词准循环低密度奇偶校验码；准循环中密度奇偶校验码；McEliece公钥体制；比特翻转译码算法作者简介李梦东（1964-），男，山东利津人，教授，主要研究方向为密码算法及其应用；孙玉情（1990-），女，河南周口人，硕士研究生，主要研究方向为信息安全､密码学（[e-mail]）；韦依儿（1994-），女，陕西西安人，硕士研究生，主要研究方向为信息安全､密码学；程思培（1995-），男，山西长治人，硕士研究生，主要研究方向为保密通信．中图分类号TP309.7访问地址投稿日期2018年4月23日修回日期2018年7月12日发布日期2018年9月12日一种改进的基于奇偶校验码的McEliece变型方案————————————————————————————————————————————————引用格式李梦东,孙玉情,韦依儿,程思培.一种改进的基于奇偶校验码的McEliece变型方案[J/OL].2019,36(11).[2018-09-12].第36卷第11期计算机应用研究Vol.36No.11优先出版ApplicationResearchofComputersOnlinePublication——————————收稿日期：2018-04-23；修回日期：2018-07-12基金项目：北京市支持中央高校共建项目——青年英才计划项目；中央高校基本科研业务费专项资金资助项目（2017CL06）作者简介：李梦东（1964-），男，山东利津人，教授，主要研究方向为密码算法及其应用；孙玉情（1990-），女，河南周口人，硕士研究生，主要研究方向为信息安全､密码学（[e-mail]）；韦依儿（1994-），女，陕西西安人，硕士研究生，主要研究方向为信息安全､密码学；程思培（1995-），男，山西长治人，硕士研究生，主要研究方向为保密通信．一种改进的基于奇偶校验码的McEliece变型方案*李梦东1,2，孙玉情2，韦依儿2，程思培1(1.北京电子科技学院,北京100070;2.西安电子科技大学通信工程学院,西安710071)摘要：McEliece公钥加密体制是基于编码理论的公钥密码体制，其安全性可以规约到一般线性码译码问题，可以抵抗量子攻击。提出了一种改进的基于准循环中密度奇偶校验（QC-MDPC）码和准循环低密度奇偶校验（QC-LDPC）码的McEliece变型方案。主要改进是将QC-LDPC码和QC-MDPC码的奇偶校验矩阵结合作为私钥，生成二者的级联码字应用于McEliece变型方案，并且给出了改进的译码算法。分析表明在80bit安全下该体制密钥量小且实现的复杂度低，能抵抗最近提出的分别针对QC-MDPC和QC-LDPC体制的密钥恢复攻击。关键词：准循环低密度奇偶校验码；准循环中密度奇偶校验码；McEliece公钥体制；比特翻转译码算法中图分类号：TP309.7doi:10.3969/j.issn.1001-3695.2018.04.0349ImprovedMcEliecevariantschemebasedonparity-checkcodesLiMengdong1,2,SunYuqing2,WeiYier2,ChengSipei1(1.BeijingElectronicScience&TechnologyInstitute,Beijing100070,China;2.InstituteofCommunicationEngineering,XidianUniversity,Xi’an710071,China)Abstract:McEliecepublic-keycryptosystemisapublic-keycryptosystembasedoncodingtheory.Itssecuritycanbereducedtothegenerallinearcodedecodingproblemanditcanresistquantumattack.ThispaperproposedanimprovedMcEliecevariantschemebasedonquasi-cyclicmediumdensityparitycheck(QC-MDPC)codeandquasi-cycliclowdensityparitycheck(QC-LDPC)code.ThemainimprovementwasthattheparitycheckmatricesofQC-LDPCcodeandQC-MDPCcodewerecombinedasaprivatekey,andtheconcatenatedcodewordsgeneratedwereappliedtotheMcEliecevariantscheme,andanimproveddecodingalgorithmwasgiven.Theanalysisshowsthatunderthe80-bitsecurity,ithassmallsystemkeyandlow-implementcomplexity.Inaddition,thissystemcanresisttherecentlyproposedkeyrecoveryattacksonQC-MDPCandQC-LDPCrespectively.Keywords:QC-LDPC;QC-MDPC;McEliecePKC;bit-flippingdecodingalgorithm0引言近年来量子计算机发展迅速，为了避免量子攻击，选取后量子安全加密方案至关重要。基于纠错码的公钥密码体制，其安全性可以规约到一般线性码译码问题，是目前为止能够抵抗量子计算机攻击的主要方案之一，具有较好的安全性。经典的基于二元Goppa码编码的方案，例如McEliece和Niderreiter方案虽然实现速度很快，但存在密钥量大的问题。很多试图改进这一缺点的算法使用一些码代替Goppa码以得到更紧致的密钥表示，但大多已被攻破[1，2]。目前较有希望的既保持安全性又具有较短密钥长度的McEliece变型算法是采用QC-MDPC码的方案。Baldi等人[3]最早将QC-LDPC码应用在McEliece体制中。这一没有过多代数结构同时具有快速译码算法的码，使加密体制既具有更小的公钥，又具有相应的安全性。但是不久这一算法被Otmani等人[4]利用结构攻击的方法攻破，原因是其对偶码存在低维数的漏洞。之后Baldi等人[5]又对其之前的QC-LDPC方案进行了改进，提高了安全性使其能抵抗Otmani的攻击。2013年Misoczki等人[6]提出了采用QC-MDPC码的McEliece公钥密码体制，并证明其能够抵抗已知的对LDPC码的攻击，同时保持了QC-LDPC码密钥短的优点。但是在2016年，Guo等人[7]对Misoczki提出的QC-MDPC方案提出了一种密钥恢复攻击，该攻击利用大量实验寻找译码错误概率和密钥距离谱之间的关联性，对密钥进行恢复。同年Shooshtari等人[8]证实了当优先出版李梦东，等：一种改进的基于奇偶校验码的McEliece变型方案第36卷第11期Baldi改进的QC-LDPCMcEliece体制的循环矩阵的循环块为偶数时，其易遭受信息集译码攻击[8]。之后在2017年，Fabšič等人[9]将Guo等人的攻击方法应用于该体制，同样是通过大量实验寻找置换矩阵Q与译码错误概率之间的依赖，对密钥进行恢复。为了使McEliece变型体制能保持密钥短及传输率高的优点，并使其还能抵抗针对QC-LDPC与QC-MDPC变型体制的攻击，本文设计了将两种奇偶校验码结合使用的McEliece体制。利用密度不同的奇偶校验矩阵的合矩阵对生成矩阵进行定义，再对明文加密。密文为QC-LDPC和QC-MDPC码字的级联再加上随机差错图样e，即cmGe分析结果表明，在选择适当参数下，此体制可抵制Guo等人提出的密钥恢复攻击，同时也能避免针对QC-LDPC的攻击。1预备知识1.1相关定义定义1LDPC码。码字2{|0}nTCcFHc，是低密度奇偶校验码，其奇偶校验矩阵H密度较低，是个稀疏矩阵，可以用Tanner图来表示(见图1)。定义2MDPC码。它是比LDPC码密度稍高的码，一个(,,)nrw-MDPC码是一个长度为n，余维数为()rrn的线性码，其奇偶校验矩阵具有恒定的行重w。MDPC码的奇偶校验矩阵的行列密度相比于LDPC码的奇偶校验矩阵稍高；实际中应用的LDPC码的奇偶校验矩阵行重一般情况下是小于等于10的，而MDPC码的奇偶校验矩阵的行重约为(log)Onn。一般对于80比特到256比特安全参数下，MDPC码的校验矩阵选择的行重在90到644之间。定义3准循环（quasi-cyclic，QC-）码。对于一个(,)nr-线性码，若存在小整数0n（比如2、3、4等小整数），使得在这个码字集合中的每个码字每经过0n的循环移位又生成一个码字，则称该码为准循环码。定义4QC-LDPC/QC-MDPC码。当(,,)nrw-LDPC/MDPC码字也是准循环时；或者说由循环块校验矩阵定义(,,)nrw-LDPC/MDPC码时，其中0nnr，则为准循环低/中密度奇偶校验码，即QC-LDPC/QC-MDPC码。定义5循环矩阵。如果一个矩阵的行是第一行的连续循环移位，则称这个矩阵为循环矩阵。定义6矩阵的密度Hd。2rnHF的密度是指H中平均每行1的数目，即1HHdr中的数目定义7n-比特安全性。任何攻击者成功攻击所花费的代价（基本操作数）2nT；或者说任何有效的攻击成功率2n；再或者是以上两种情况的结合，即/2nT。1.2传统的McEliece体制McEliece体制[10]是在1978年由McEliece提出的基于编码理论的一种公钥密码体制。该体制加解密过程中使用到了三个矩阵，即GSP，，，其中G为可以纠正t个错误的(,,21)nkt-线性码（McEliece提出使用的线性码Goppa码）的kn阶生成矩阵；S为kk阶随机非奇异（可逆）矩阵；P为nn阶随机置换矩阵。由此计算出矩阵'GSGP和纠错能力t一起作为公钥，私钥为GSP，，。加密：'cmGe，其中e为重量小于等于t的随机差错图样；解密：等式两边同时乘1P，即11cPmSGeP，然后使用Goppa码的快速译码算法纠出差错图样1eP，计算出mS，则1mmSS。1.3LDPC/MDPC码的Tanner图表示LDPC码和MDPC码都可用Tann