基于改进版Niederreiter的双公钥密码方案

王众 韩益亮

摘 要：基于编码的密码体制可以有效地抵抗量子计算攻击，具有较好的可操作性以及数据压缩能力，是后量子时代密码方案的可靠候选者之一。针对量子时代中计算机数据的安全保密问题，对编码密码中的Niederreiter密码方案改进版进行深入研究，提出了一种与双公钥加密方式相结合的密码方案。所提方案的安全性相比Niederreiter方案改进版以及基于准循环低密度奇偶校验码（QC-LDPC）的Niederreiter双公钥加密方案得到提升，在密钥量方面相比传统Niederreiter密码方案的公钥量至少下降了32%，相比基于QC-LDPC码的Niederreiter双公钥加密方案也有效下降，在量子时代保证计算机数据安全表现出较强的可靠性。

关键词：编码密码;Niederreiter密码体制;系统码;安全性分析;效率分析

Abstract： The code-based cryptosystem can effectively resist quantum computing attacks with good operability and data compression capability， and is one of the reliable candidates for the post-quantum era cryptographic scheme. Aiming at the security and confidentiality of computer data in the quantum era， the in-depth study of an improved Niederreiter cryptographic scheme in code-based cryptography was carried out， and a cryptographic scheme with combination of dual public-key encryption method was proposed. The security of the proposed scheme was improved compared with the improved Niederreiter scheme and the Niederreiter dual public-key encryptographic scheme based on Quasi-Cyclic Low-Density Parity-Check （QC-LDPC） code. The amount of keys in the scheme is at least 32% lower than that of traditional Niederreiter scheme， and is also effectively reduced compared with that of the Niederreiter dual public-key encryptographic scheme based on QC-LDPC code， which shows the strong reliability for ensuring computer data security in the quantum age.

Key words： code-based cryptography; Niederreiter cryptosystem; system code; security analysis; efficiency analysis

0 引言

量子技術的概念近来越来越多地进入人们的视线，量子技术的计算能力在给人们带来计算性能很强的并行计算、解决许多棘手问题的同时，也构成了不容忽视的安全威胁。密码学中的传统公钥密码在量子计算机出现后不会再像现在那么安全可靠，比如基于经典数论理论的RSA（Rivest-Shamir-Adleman）公钥加密算法、椭圆曲线密码（Elliptic Curve Cryptography， ECC）、属性基密码等，将会在量子计算机出现后不再可靠[1]。目前可以较为有效地抵抗量子计算攻击的密码体制主要有以下四种：基于编码的密码体制、基于格的密码体制LWE（Learning With Errors）、基于Hash函数的密码体制以及基于多变量的密码体制。基于编码的密码体制具有较高的计算效率以及可操作性，是量子时代一种可靠的安全选择。

基于编码的公钥密码体制是在有限域上多元多项式环上定义和运算的，此类密码体制的算法核心是对一种纠错码C的应用，主要的特征即为添加一个错误到码字中或根据码C的校验矩阵计算伴随式。1978年，美国科学家McEliece[2]第一个运用这种方法设计公钥密码算法，提出首个基于编码理论的公钥加密方案，其中私钥为一个二元不可约Goppa码，公钥为该码的生成矩阵被随机化处理之后的结果。1986年，Niederreiter[3]提出了著名的基于Goppa码的Niederreiter密码体制。该方案的安全性被证明是与McEliece体制是相同的，Niederreiter体制的主要思想是从另一个角度利用随机线性码的译码困难问题，该方案隐藏的是Goppa码的校验矩阵，Niederreiter体制相比McEliece体制，公钥存储量有所下降，而且具有更高的传信率。2018年，刘相信等[4]提出了一种对Niederreiter公钥密码系统的改进，可以隐藏明文的汉明重量来有效抵抗信息集译码（Information Set Decoding， ISD）攻击等针对编码密码体制的攻击，但是其安全性仍然可以在保障效率的前提下得到进一步提升。到目前的研究阶段，基于编码理论的公钥密码学的研究重点主要放在了对码的选择上，以保证安全性的同时，提高实用性，降低方案的密钥尺寸，由最开始的Goppa码、Reed-Solomon码[5]，到现在的准循环中密度奇偶校验（Quasi-Cyclic Medium-Density Parity-Check， QC-MDPC）码[6]、低密度奇偶校验（Low Density Parity Check， LDPC）码[7]以及准循环低密度奇偶校验（Quasi-Cyclic Low-Density Parity-Check， QC-LDPC）码[8]等，通过不断优化码字的选择，编码密码的公钥量切实得到有效减少，但是安全性并没有得到明显的提升。

双公钥的思想是对明文进行二次加密，这种方法可以很好地提高公钥密码体制的安全性。2008年，张颖等[9]就曾利用双公钥对McEliece体制进行改进，使安全性有较好的提升，但是毕竟使用了双公钥的方式加密，会使得密钥量增加，实用性不强。2016年，李冲等[10]提出了基于QC-LDPC码的双公钥Niederreiter密码方案，由于QC-LDPC码的采用，能够使得双公钥方案的密钥量有所下降，安全性有较高提升，但是，密钥量和安全性仍有较大的提升空间。本文尝试将Niederreiter体制的改进版与双公钥的加密方式相结合，并采用系统码，在增加方案安全性的同时，保证有效的实用性。

1 相关工作

1.1 SDP问题

校验子译码问题（Syndrome Decoding Problem， SDP） 给定一个（n，k）的线性码，它的最小汉明距离为d，该码的校验矩阵为H∈F（n-k）×n2，它的纠错能力为t且t满足方程d=2t+1。当给定一个向量v∈F（n-k）×n2时，寻找一个错误向量e∈Fn2，它的汉明重量要小于等于t，且与向量v以及矩阵H满足方程v=eHT，寻找错误向量e这个问题已被证明为NP困难问题[11]。

通过上述对Niederreiter密码方案改进版的阐述，可以发现许多针对Niederreiter方案的攻击方法例如像ISD攻击等的代价由于对重量t进行隐藏后变得较大，正是由于t的选择变得灵活后，那么在选码时便可选择适当的维度来避免密钥量过大，具体分析请参考文献[4]，但文献[4]若采用双公钥的加密方法能进一步加强方案的安全性，并通过选取系统码来进行构造，避免方案的密钥量过大，增加方案的实用性。

2 基于改进版Niederreiter的双公钥密码方案

2.1 参数生成

选取两个二元即约系统码G1、G2维度分别为（n，k）和（n-k，k），纠错能力分别为t1、t2，两个码对应的校验矩阵为（n-k）×n维的H1和（n-2k）×（n-k）维的H2，且H2可以拆分为H2=H3+H4，其中矩阵H3、H4为随机拆分得到的。两个码的译码算法为β1Ht（）和β2Ht（）。随机选取一个（n-k）×（n-k）维可逆矩阵S，与一个n×n的置换矩阵T，并计算H=SH1T。再随机选择三个（n-2k）×（n-2k）的可逆矩阵A、B、C，以及（n-k）×（n-k）维的置换矩阵Q，并计算H′=AH3Q，H″=BH4Q，H=CH2Q。公开密钥即为（H，H′，H″，H，t1，t2），私钥即为（S，T，A，B，C，Q， β1Ht（）， β2Ht（））。

2.2 加密过程

首先利用系统码G1所产生的公钥H对n维明文m进行第一步加密，产生密文c1，c1=mHT。此处注意，在对G2进行选择时，它的纠错能力t2需要满足t2>wt（c1），以方便后面的译码解密，且这一点在选码时易于实现。

完成第一步后，进行第二步加密。将c1看作新的明文，用G2所产生的一系列公钥对其进行加密。首先将进行拆分，c1=c2+c3，计算x1=c2H′T，x2=c2H″T，x3=c3HT，将（x1，x2，x3）作为密文，发送给接收者。

2）完成第一步解密得到c1后，第二步解密就是普通的Niederreiter密码体制的译码解密。运用私钥S，T和码G1的译码算法β1Ht（）进行解密，具体如下：

利用译码算法β1Ht（）对mTTH1T译码即可得到mTT，利用私钥T进行运算得到m=mTTTT-1。

从上述的加解密过程可以看出，加密时，先对明文进行传统的Niederreiter加密，得到密文后，采用改进版Niederreiter再进行加密。解密时，先对改进版Niederreiter解密得到第一次加密的密文，再利用传统的Niederreiter解密方式进行解密得到最后的明文即可。

3 安全性分析

3.1 直接攻击

所谓直接攻击，是指在拥有密文c和公钥H′后，通过直接求解方程c=mH′T来求得明文的攻击方法，但是Niederreiter密码体制所依赖的是SDP校验子译码问题，该问题为NP困难问题，因此直接通过方程来求解明文m是十分困难的。本文方案采用了双公钥的加密方法，使得破解的工作量至少翻倍，又由于第二次加密采用了改进的Niederreiter密码体制，使得安全性又有了新的提升。

3.2 直接译码攻击

直接译码攻击是指通过公钥H，H′，H″，H得到S，H1，T和A，H3与B，H4以及C，H2和Q，然后通过码的快速译码算法得到明文m来攻破该体制。由矩阵的相关理论可以得知，矩阵的分解不是唯一的，比如像从矩阵H中分解出S，H1，T，它們各自可能的个数分别为2（n-2k）2∏n-2ki=1（1-2-i）、1t2nt2和（n-k）！，由此可见，当n和t的取值比较大时，矩阵可能的数目十分巨大，这导致敌手在多项式时间内是难以通过公钥分解出私钥的，而本文方案有4个公钥矩阵，工作量会变为4倍，相比Niederreiter方案改进版[4]的三个公钥矩阵和基于QC-LDPC码的Niederreiter双公钥加密方案[11]的两个矩阵，工作量加倍，安全性增强。

3.3 信息集译码（ISD）攻击

李元兴等[12]指出，可以通过解线性方程组的方法来攻破Niederreiter密码体制。所谓信息集译码攻击即ISD攻击是指：给定明文m=（m1，m2，…，mn），以及加密方程c=mHT，任意选择明文m=（m1，m2，…，mn）中的k个分量，并将其删除，并相应删除公钥矩阵H中的k列，那么可得到新的方程即为c=m1×（n-k）HT（n-k）×（n-k），此时，若矩阵HT（n-k）×（n-k）可逆，那么可求得m1×（n-k）=c×HT-1（n-k）×（n-k），然后查看wt（m1×（n-k））是否为公开的汉明重量t，若为t，则在相应的k个位置上补零即可得到最后的明文m。当矩阵HT（n-k）×（n-k）不可逆或者最后求得的m1×（n-k）的汉明重量不符合要求时，需要重新选择矩阵HT（n-k）×（n-k）进行以上运算。ISD攻击对于编码密码来说是一种较为强力的攻击方法，并且还被不断深化与研究[13-17]。在文献[18]中，已经证明采用双公钥方式进行两次普通Niederreiter加密的方法可以有效抵抗此类攻击，攻击成功的工作因子为W=[（n-k）3Ckn-k-t2/Ckn]·[（n-2k）3Ckn/Ckn-t1]，因此当n，t选取较大时攻击者在多项式时间内难以攻破双公钥的Niederreiter密码体制。

本文采用双公钥的Niederreiter加密方式，在第一次加密时是采用的普通的Niederreiter密码方案，第二次加密时则是采用的改进的Niederreiter密码方案。改进的Niederreiter密码体制的最大特点就是对加密的消息c1的汉明重量进行了隐藏，将其进行了拆分，成为了两部分c1=c2+c3，并相应地将校验矩阵H2进行了拆分H2=H3+H4，与拆分后的明文进行加密运算。采用ISD攻击的一个关键所在就是要掌握明文的汉明重量，这样才能确认是否攻击成功。改进的Niederreiter密码体制加密后的密文为xi=ciHT的形式，并非c1，那么ci的汉明重量也就更加灵活，取值范围从0到n-k，那么攻击者也就不能判断wt（xiHT-1（n-2k）×（n-2k））是否符合要求，因此，对于一个汉明重量为ti的加密信息ci=（c1，c2，…，cn-k），右乘一个（n-k）×（n-2k）的矩阵HT，相当于在HT中选取相应的ti行，而0≤ti≤n-k，因此，采用解线性方程组攻击第二次加密的代价为C0n-k+C1n-k+C2n-k+…+Cn-k-1n-k+Cn-kn-k=2n-k。综上可知，ISD攻击针对基于改进版Niederreiter的双公钥密码方案的工作因子为W=2n-k·[（n-k）3Ckn-k-t2/Ckn]，相比基于QC-LDPC码的双公钥Niederreiter密码方案[11]有较大提升。Niederreiter改进版[4]只有一次加密的过程，它的工作因子为C0n-k+C1n-k+C2n-k+…+Cn-k-1n-k+Cn-kn-k=2n-k，从上面对本文方案工作因子的分析可以看出，二次加密的信息为第一次加密的密文，因此安全性较其有较大的提升。

4 效率分析

4.1 系统码优势

采用双公钥的加密方式，可以有效地提高系统的安全性;但是也会存在一个较为明显的弊端，就是密钥量的增加，而密钥量对于基于编码的密码体制而言，本身就是一个缺陷。Niederreiter密码体制在相同的安全性下相比McEliece体制的密钥量有所减少;但是相对传统的公钥密码像背包密码等，它的密钥量还是很大。如何有效提高编码密码体制的效率，减小公钥量是个至关重要的问题。目前基于编码理论的公钥密码学研究的重点主要放在了对码的选择上，由最开始的Goppa码、Reed-Solomon码，到现在的QC-MDPC码、LDPC（Low Density Parity Check）码以及QC-LDPC码等，来减少编码密码的公钥量。本文方案就采用系统码来有效减少密钥量。

系统码的生成矩阵或者校验矩阵，可以通过一系列行列变换变换为G=（Ik|Q）或H=（-QT|In-k），其中Q为一个k×（n-k）阶的矩阵，那么它的转置即为（n-k）×k阶矩阵，而矩阵Ik，与In-k均为单位矩阵，由此，可以看出，系统码在存储时，只需对k×（n-k）阶的矩阵Q或（n-k）×k阶矩阵-QT（负号代表矩阵中的元素为其逆元）进行存储即可，若不采用系统码构造，则需对k×n阶矩阵或（n-k）×n阶矩阵进行存储。在本文方案中，有四个公开的密钥矩阵H、H′、H″、H，除了矩阵H的维度为（n-k）×n阶，其余三个矩阵均为（n-2k）×（n-k）阶，在采用系统码后，对H进行存储的维度为（n-k）×k阶，对H进行存储的维度为（n-2k）×k阶，而对H′、H″进行存储的维度与H的维度不同，是因为H由系统码G2的校验矩阵H2通过行列变换得到的，可以节约存储，而H′、H″是由系统码G2的校验矩阵H2进行拆分得到的H3、H4通过行列变换得到，H3、H4未必满足系统码的性质，因此H′、H″的维度仍为（n-2k）×（n-k）阶。以n=1024，k=1024-10t，t=55为例，普通Niederreiter密码体制所存储公钥矩阵的尺寸为p1=（n-k）×n=56.32×104，而本文的双公钥Niederreiter密码方案的公钥尺寸为p2=（n-k）×k+（n-2k）×k+2×（n-2k）×（n-k）=38.03×104。由该例子可以看出，本文的双公钥Niederreiter密码方案由于系统码的采用不仅保证了安全性的提升，并有效降低了32%的公钥量。表1为本文方案密钥尺寸与改进版Niederreiter密码方案进行比较。

改进版Niederreiter由于可對重量t进行隐藏，因此只需选取一个维度较小的码字，而本文方案第二步采用的是改进版Niederreiter，因此可以选择维度较小的系统码，第一步选择一个符合第2章描述的系统码即可，因此相比改进版Niederreiter，密钥量只多在一个系统码上。由表1可以看出，本文方案由于采用的是系统码，因此选择两个码后，密钥尺寸会有一定增加，但是在合理范围内，并获得更高的安全性。具体的安全性优势已在第3章中进行了分析。

4.2 重量t优势

本文的双公钥Niederreiter密码方案另一个优势特点就是在第二步加密时采用的改进版Niederreiter密码方案，如3.3节所述，它可以很好地将加密信息的汉明重量进行隐藏，所达到的效果就是使得ISD攻击的代价对于（n，k，t）维的码为C0n+C1n+C2n+…+Cn-1n+Cnn=2n，这相比传统Niederreiter密码方案在安全性方面有很大的提升。为了提高方案的使用效率，就可以考虑在选码时降低汉明重量t的选择，没有必要再去选择t过大的码，而可以达到同样的安全性要求，这就相比基于QC-LDPC码的双公钥Niederreiter密码方案[10]在选择码时可以减小码的维度，以达到降低公钥尺寸的目的。将第二步加密时的选码与基于QC-LDPC码的双公钥Niederreiter密码方案[10]的第二步选码进行比较，结果如表2所示。

由表2可以看出，本文方案相比QC-LDPC码方案可以选择较小维度的码字以达到同QC-LDPC码方案同样的安全级别，使得公钥的尺寸有很大幅度的下降，如表1中在80b安全级下，本文方案密钥尺寸为5040b而QC-LDPC码方案为28408b。

由于最后的密文是由G2码的公钥产生，因此G1码在选择时也可以选择较小的汉明重量t，而不会影响到整个双公钥体系的安全，但是G1、G2码的选择由于解密时还要考虑译码问题，如2.2节所述，需要结合实际情况进行选择。结合4.1节的分析，可以看出本文的双公钥Niederreiter密码方案不仅安全性得到较大的提升，而且在公钥尺寸这两处的表述有疑问，“公钥尺寸”此处是否应该为“效率”，因為后面已经提及了“公钥尺寸”是下降的。回复：直接删除“公钥尺寸方面也有一定的提升”直接连接“公钥尺寸相比……”一句方面也有一定的提升，公钥尺寸相比基于QC-LDPC码的双公钥Niederreiter密码方案有效降低下降这处的表述不严谨，降低是否应为下降？请明确，相比传统的Niederreiter密码方案至少下降了32%，能够在更多的场景中有效运用。

5 结语

基于编码的密码体制是抗量子计算时代的优良候选者之一，双公钥的加密方式旨在增加密码方案的安全性。本文对改进版Niederreiter密码方案以及双公钥加密方式进行深入研究，将二者进行结合，并采用系统码，提出了一个双公钥Niederreiter密码方案。本文方案在安全性方面相比改进版Niederreiter得到显著提升，可以良好地抵抗ISD等针对编码密码体制的攻击。本文方案在公钥量方面，相比Niederreiter密码方案至少下降了32%，而相比基于QC-LDPC码的双公钥Niederreiter密码方案也有效降低。优良的性质使得本文方案在今后的抗量子密码时代能够为计算机安全提供可靠的安全保障，但是需要注意的一点便是在选择系统码时要结合实际情况以及应用场景选择合适的参数，以保证方案的正确性。

参考文献 （References）

[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] McELIECE R J. A public-key cryptosystem based on algebraic coding theory [J]. DSN Progress Report， 1978， 42（44）： 114-116.

[3] NIEDERREITER H. Knapsack-type cryptosystems and algebraic coding theory [J]. Problems of Control and Information Theory， 1986， 15（2）： 159-166.

[4] 刘相信，杨晓元.Niederreiter公钥密码方案的改进[J].计算机应用，2018，38（7）：1956-1959.（LIU X X， YANG X Y. Improvement of the Niederreiter public key system [J]. Journal of Computer Applications， 2018， 38（7）： 1956-1959.）

[5] 张俊.编码的构造与译码问题及其在密码学中的应用[D].天津：南开大学，2014：23-39.（ZHANG J. The problem of coding construction and decoding and its application in cryptography [D]. Tianjin： Nankai University， 2014： 23-39.）

[6] 李泽慧，杨亚涛，李子臣.基于QC-MDPC码的公钥密码方案设计[J].计算机应用研究，2015，32（3）：881-884.（LI Z H， YANG Y T， LI Z C. Design of public key cryptography based on QC-MDPC code [J]. Application Research of Computers， 2015， 32（3）： 881-884.）

[7] 曹东，赵生妹，宋耀良.一种基于量子准循环LDPC码的McEliece公钥密码算法[J].南京邮电大学学报（自然科学版），2011，31（2）：64-68.（CAO D， ZHAO S M， SONG Y L. A McEliece public key cryptography algorithm based on quantum quasi-cyclic LDPC Code[J]. Journal of Nanjing University of Posts and Telecommunications （Natural Science Edition）， 2011， 31（2）： 64-68.）

[8] 王延丽.基于QC-LDPC码的McEliece公钥密码体制研究[D].西安：西安电子科技大学，2013：1-5.（WANG Y L. Research on McEliece public key cryptosystem based on QC-LDPC code [D]. Xian： Xidian University， 2013： 1-5.）

[9] 张颖，岳殿武.基于代数几何码的公钥密码体制[J].通信学报，2008，29（6）：75-81.（ZHANG Y， YUE D W. Public key cryptosystem based on algebraic geometry codes [J]. Journal on Communications， 2008， 29（6）： 75-81.）

[10] 李沖，韩益亮.基于QC-LDPC码的双公钥Niederreiter密码方案[J].计算机应用研究，2016，33（11）：3446-3449.（LI C， HAN Y L. Double public key Niederreiter cryptography scheme based on QC-LDPC code [J]. Application Research of Computers， 2016， 33（11）： 3446-3449.）

[11] 范武英，任方.基于校验子译码问题的伪随机序列研究综述[J].西安邮电大学学报，2017，22（2）：1-6.（FAN W Y， REN F. Review of pseudo-random sequence based on syndrome decoding problem[J]. Journal of Xian University of Posts and Telecommunications， 2017， 22（2）： 1-6.）

[12] 李元兴，王新梅.关于代数码Niederreiter公钥密码体制的安全性及参数优化[J].电子学报，1993，21（7）：33-36.（LI Y X， WANG X M. On the security and parameter optimization of algebraic Niederreiter public key cryptography [J]. Acta Electronica Sinica， 1993， 21（7）： 33-36.）

[13] PRANGE E. The use of information sets in decoding cyclic codes[J]. IRE Transactions on Information Theory， 1962， 8（5）： 5-9.

[14] MAY A， OZEROV I. On computing nearest neighbors with applications to decoding of binary linear codes[C]// EUROCRYPT 2015： Proceedings of the 2015 Annual International Conference on the Theory and Applications of Cryptographic Techniques. Berlin： Springer， 2015： 203-228.

[15] 李梦东，蔡坤锦，邵玉芳.信息集攻击算法的改进[J].密码学报，2016，3（5）：505-515.（LI M D， CAI K J， SHAO Y F. An improved algorithm of information set decoding [J]. Journal of Cryptologic Research， 2016， 3（5）： 505-515.）

[16] TORRES R C， SENDRIER N. Analysis of information set decoding for a sub-linear error weight [C]// PQCrypto2016： Proceedings of the 2016 International Workshop on Post-Quantum Cryptography. Berlin： Springer， 2016： 144-161.

[17] KACHIGAR G， TILLICH J P. Quantum information set decoding algorithms[C]// PQCrypto 2017： Proceedings of the 2017 International Workshop on Post-Quantum Cryptography. Berlin： Springer， 2017： 69-89.

[18] 杨磊鑫，杜伟章.利用双公钥的Niederreiter公钥密码体制的改进[J].长沙理工大学学报（自然科学版），2010，7（4）：74-77.（YANG L X， DU W Z. Improvement of Niederreiter public key cryptosystem using double public key [J]. Journal of Changsha University of Science and Technology （Natural Science）， 2010， 7（4）： 74-77.）