一种基于扩展多变量公钥密码的新型签名方案

罗文俊　弓守朋

(重庆邮电大学计算机学院　重庆 400065)



一种基于扩展多变量公钥密码的新型签名方案

罗文俊弓守朋

(重庆邮电大学计算机学院重庆 400065)

摘要多变量公钥密码(MPKC)是未来抗量子攻击的热门候选算法之一。在研究现有扩展多变量签名体制的基础上，针对现有方案私钥空间较大的缺点，提出一个新类驯顺变换(Tame)和一个秘密仿射变换来增强原有签名体制的安全性。实验表明该方案能够抵御线性攻击、差分攻击以及代数攻击，并且具有较小的私钥空间。

关键词多变量公钥密码温驯变换仿射变换攻击私钥空间

0引言

多变量公钥密码[1]体制作为未来抗量子攻击的候选算法之一，一直是密码界研究的热点。针对多变量公钥密码体制的研究大多围绕两个方向来进行：一是，提出新的中心映射；二是，提出新的增强原始方案安全性的编码方法。

根据中心映射的不同，多变量公钥密码大致可以分为四种：MatsumotoImai体制、隐藏域方程(HFE)体制、不平衡油醋体制及三角体制(TTS)等[2]。但这些体制大多都被攻克。近年来，提出新的中心映射的成果并不多见，因为中心映射的设计要求较高。多变量公钥密码的研究热点大多围绕增强上述四种体制的安全性展开。如CycliRainbow方案[3]、Double-Layersquare[4]方案、EnhencedSTS[5]方案等。它们在安全性上都得到了不同程度的提高。2011年，王后珍等人通过引入Hash认证技术和一种类Tame变换，提出了一种扩展多变量公钥密码体制[6]，但该方案存在安全漏洞，在2013年被聂旭云等人攻克[7]。作者根据聂旭云破解方法，对王后珍等人的方案进行了改进[8],并且证明了经过改进后的方案安全性得到了提高。2014年，乔帅庭等人提出了一种新的类Tame变换[9]，并且声称比王后珍的方案具有更小的私钥空间，能够抵御线性攻击、差分攻击以及代数攻击。但是通过分析可知，其方案中公钥方程中含有四次项和三次项，使得公钥长度较大，另一方面，任何高次多项式都可以通过增加变量的方法将其转化成为二次项，因此增加多项式的系数并不能很好地提高密码系统的安全性。

本文通过引入一个新的类Tame变换和一个秘密仿射变换设计了一种新的多变量签名方案。分析表明新方案能够抵御线性攻击、差分攻击和代数攻击。

1多变量公钥密码体制

定义2设P和F是两个给定的有限域GF(q)上m个多项式n个变量的随机多变量二次多项式组，则IP问题是指求解GF(q)上的两个仿射变换U，T，使得P=T∘F∘U。

MQ问题和IP问题是完全NP问题，无论在传统计算机上还是在量子计算机上都无法在多项式时间内解决，因此这两个问题是多变量公钥密码的支撑。两个中的任何一个一旦能够在多项式时间内解决，那么多变量公钥密码体制将不复存在。

加密过程：对于任意合法明文x=(x1,x2,…,xn)，将其代入公钥方程P即可获得合法的密文y=(y1,y2,…,ym)。

签名过程相当于解密过程，得到签名信息后，代入公钥方程来验证签名的合法性。

2新扩展多变量公钥签名方案

新方案是在原始密码体制的基础上引入了一个类Tame变换L和一个秘密仿射变换S，设新方案运行在有限域GF(q)上，L的形式如下：

选取一个保密的单向哈希函数h，并将h∘S公开。由于h保密，攻击者无法从h∘S中恢复出S。

公钥方程组的获取：对于原始公钥方程组P=U∘F∘T，直接利用变换L将公钥方程组改造为P′=U∘F∘T∘L，此时公钥方程组变为n+α个输入n个输出的不定方程组，这相对于原始体制来说，其安全性已经得到了提高，具体原因详见第3节。为进一步增强签名方案的安全性，对已获得的公钥方程组采用“-”方法。假设减去方程的个数为μ，此时的公钥方程为n+α个输入，n-μ个输出的方程组。

由上述分析可知，新方案的私钥D={U-1,F-1,T-1,L,S}，如果对有限域GF(q)上长度为n-μ的信息向量(y1,y2,…,yn-μ)进行签名，具体的签名步骤如下：

第一步随机选取GF(q)上μ个随机值(yn-μ+1,yn-μ+2,…,yn)，与待签名向量构成n维向量(y1,y2,…,yn)。

第二步用私钥U-1计算得到(l1,l2,…,ln)=U-1(y1,y2,…,yn)。

第三步利用中心映射的逆得到(r1,r2,…,rn)=F-1(l1,l2,…,ln)。

第四步利用私钥T-1计算得到(t1,t2,…,tn)=T-1(r1,r2,…,rn)。

签名验证首先利用公开的h∘S验证xn+α+1=h∘S(x1,x2,…,xn)是否成立，若成立则继续下一步验证，否则拒绝。

其次将(x1,x2,…,xn+α)代入到公钥方程，验证公钥方程组是否成立，若成立则正确，否则拒绝。

3安全性分析

由第2节可知，新方案的核心在于引入了一个类Tame变换来增加原始公钥方程中变量的个数。在签名过程中又通过仿射变换S消除了冗余变量的个数。可以说利用Tame变换来实现对公钥方程的外在改变，通过仿射变换来消除冗余变量或生成部分签名信息。

证明：由于引入了冗余变量，攻击者在利用原始破解方法得到的签名信息的基础上，还需保证签名信息满足秘密仿射变换S，即需要满足如下方程组：

每个变量选对的概率为1/q，那么选取变量满足此方程组的概率为1/qn，即还需花费的代价为O(qn)，利用乘积密码的性质可得破解新方案的代价为O(qm+n)。由上述分析可知，新方案很好地提高了原始签名方案的安全性。

在聂旭云[6]的攻击方案中，其核心是利用对角矩阵的特殊结构，求出不含扩展变量(冗余变量)的公钥方程，将破解难度降低到不含有扩展变量的难度，从而破解王后珍等人的方案，具体的分析过程可见作者的成果[7]。新方案中Tame变换选取的可逆矩阵A无法通过聂旭云的攻击方法获得。即使能够获得可逆矩阵A，由于不知道秘密仿射变换S也无法破解新方案。

线性攻击方法是多变量公钥密码体制的一种常见攻击方法。它是在1988年被Patarin首次提出的。主要针对的是MI体制。在原始MI体制中明文和密文之间存在着如下线性关系式：

其中X=(x1,x2,…,xn),Y=(y1,y2,…,yn)为明密文对，在给出足够多的明密文对后，就可求出方程组中全部系数，从而达到破译的目的。新方案中由于引入一个新的类Tame变换，就可以得到如下n个二次多项式方程组：

在这个关系中由于ti未知，所以在获取足够明密文的情况下无法获取上述方程组中的系数，从而无法破译新方案。新的签名方案中也采取了“-”方法，即删除公钥方程组中的后μ个方程。它是Patarin改进原始MI体制采用的，并且根据该方法提出了SFLASH签名算法，并成为NESSIE的签名标准。新方案在引入Tame变换的基础上又采取了“-”方法，消除了线性攻击的可能性。

差分攻击是多变量公钥密码中的另一种常见攻击方法[10]，该方法主要针对于采用了“-”方法的MI体制，其核心思想就是利用中心映射的特性，构造μ个二次方程，与公钥n-μ个方程一起重新构成一个完整的MI公钥多项式，这样转换后，就可以利用上述的线性攻击破解。

对于函数F(x)，定义在a点出的差分为：DF(a,x)=F(x+a)-F(x)-F(a)+F(0)，传统MI体制中心映射F(X)=Xqθ+1，则其差分函数为：DF(a,x)=axqθ+aqθx，它有一个特殊的性质：

DF(εa,x)+DF(a,εx)=(ε+εθ)DF(a,x)。同理，MI体制的公钥函数Y=T∘F∘U的差分函数DY满足如下关系式：

DY(a,εx)+DY(εa,x)=T∘DF(U(a),εU(x))+

T∘DF(εU(a),U(x))=T∘(ε+εqθ)∘T-1(DY(a,x))

若使用减方法后，原始MI公钥变为了Y′=T-∘F∘U，则可利用Y′和利用上述特性构造出的μ个二次方程形成一个新的MI算法，然后再利用线性方程攻击方法得到n-μ个公钥方程的原像，从而成功伪造签名。而新方案对原始MI密码体制进行了改进，由于引入了非线性的Tame变换L，设U″=U∘L，新方案的公钥形式变为了Y″=T∘F∘U″，可以看出U″不可逆，即∀x,ε∈GF(qn),εU″(x)≠U″(εx)，于是：

DY″(a,εx)+DY(εa,x)=T∘DF(U″(a),εU″(x))+

T∘DF(εU″(a),U″(x))≠T∘(ε+εqθ)∘T-1(DY(a,x))

可以看出引入的L破坏了传统MI体制的对称性，即新方案能够抵御差分攻击。

线性攻击和差分攻击大多针对于不同结构的多变量密码体制，而另外一种代数攻击方法适用于所有体制的多变量密码体制。所谓代数攻击就是直接从公钥出发，求解方程的过程。根据变量个数和方程个数之间的关系分为三种关系：置换方程组，超定方程组和不定方程组。其中在置换方程组中变量个数与方程个数相等，超定方程组中变量个数小于方程个数，不定方程组中变量个数大于方程个数。新方案由于采用了“-”方法，公钥方程组属于不定方程。根据现有的研究成果[11]，求解不定方程组的复杂度约为O(qm)，q为有限域的阶(有限域内元素的个数)，m为变量个数。通常认为攻击复杂度超过O(280)的方案是安全的，所以只要在新方案中选择合适的有限域和变量个数就可以有效地抵御代数攻击。

4公私钥尺寸

新方案中公钥是不定方程组，其长度约为(n-μ)(n+∂+1)(n+∂+2)/2，其中n表示变量的个数，∂表示新增变量的个数，μ表示原方程组中去掉方程的个数。

新方案的私钥主要包括两个可逆变换T,U及其逆矩阵，引入的Tame变换L和秘密仿射变换S，经计算其大小约为5n2+2n∂+2∂2+2∂+n，其中n表示变量的个数，∂表示新增变量的个数。在保证安全性的前提下，新方案与王后珍等人的签名方案(Wang方案)之间公私钥大小对比，如图1所示，可以看出新方案在与Wang方案有同等规模的公钥尺寸时，具有较小的私钥空间，可以说是对Wang方案的一种改进。

图1　新方案与王方案私钥大小比较

5结语

本文通过了一个新的Tame变换和一个仿射变换，设计出了一个新的基于扩展多变量公钥密码的签名方案。新的签名方案可以说是对王后珍等人的签名方案的一种改进，新方案在保持原有安全性的基础上缩小了私钥空间。是否存在一个新的攻击方法有待进一步的研究，而且新方案尚不能用于加密，这也是未来工作的一个研究重点。

参考文献

[1]DingJT,JasonEGower.MultivariatePublicKeyCryptosystems[M].NewYork:Springer,2006.

[2]DingJT,YangBY.MultivariatePublicKeyCryptography[M].BerlinSpringerVerlag,2009.

[3]Petzoldt,Bulygin,BuchmannJ.CyclicRainbow-AMultivariateSignatureSchemewithaPartiallyCyclicPublicKey[M].ProgressinCryptology-INDOCRYPT,2010.

[4]CloughCL,DingJ.Securevariantsofthesquareencryptionscheme[C]//Post-QuantumCryptography,2010:153-164.

[5]Tsuijii,Gotaishi.ProposalofasignatureschemebasedonSTStrapdoor[C]//Post-QuantumCryptography,2010:201-217.

[6] 王后珍,张焕国,王张宜.一类具有安全加密功能的扩展MQ公钥加密体制[J].中国科学,2011,41(11):1297-1309.

[7] 聂旭云,徐赵虎,廖永建,等.多变量公钥密码扩展方案的安全性分析[J].计算机学报,2013,36(6):1177-1182.

[8] 罗文俊,弓守朋.多变量公钥密码体制扩展方案的改进[J].计算机科学,2014,41(6A):361-364.

[9] 乔帅庭,李益发,韩文报.新扩展多变量公钥密码方案[J].通信学报,2014,35(4):148-153.

[10]DuboisV,FouquePA,ShamirA.PracticalCryptanalysisofSFLASH[J].ProceedingsofCrypto,2007,46(22):1-12.

[11]ThomaeE,WolfC.Solvingunderdeterminedsystemsofmultivariatequadraticequationsrevisited[C]//Proceedingsofthe15thInternationalConferenceonPracticeandTheoryinPublicKeyCryptography,2012:156-171.

A NEW SIGNATURE SCHEME BASED ON EXTENDED MULTIVARIATEPUBLICKEYCRYPTOSYSTEM

Luo WenjunGong Shoupeng

(School of Computer Science and Technology,Chongqing University of Posts and Telecommunications,Chongqing 400065,China)

AbstractMultivariate public key cryptosystems (MPKC) is one of the hot candidates for post-quantum cryptography. On the basis of analysing the existing extended multivariate signature system, we proposed a new signature scheme, targeted at the defect of current scheme in big private key size, being enhanced by a new type of “tame transformation” and a secret affine transformation. Experiment showed that this new scheme is able to resist linear attack, differential attack and algebraic attack. What’s more, its private key size becomes smaller as well.

KeywordsMPKCTame transformationAffine transformationAttackPrivate key size

收稿日期：2015-01-17。国家社科基金项目(14CTQ026)；重庆市自然科学基金项目(cstc2014jcyjA40028)。罗文俊，教授，主研领域：信息安全。弓守朋，硕士生。

中图分类号TP309

文献标识码A

DOI:10.3969/j.issn.1000-386x.2016.06.074