一种优化的多变量加密方案*

赵菲菲，魏仕民

(淮北师范大学数学科学学院，安徽淮北235000)

量子计算机的发展对目前广泛使用的公钥密码体制构成了潜在的威胁。而多变量公钥密码体制被认为是能抵御未来基于量子计算机攻击的几种公钥密码体制之一，其安全性基于有限域上求解多变量多项式方程组为一NP-C问题。体制具有较高的效率和安全性，且易于硬件实现，因此被认作量子计算机时代一种安全的密码体制和数字签名备选方案。

多变量公钥密码体制代数结构庞大。设F为有限域，公钥P=T°Q°S:Kn→Km(符号°表示映射的合成)。其中，S:u→x=MSu+CS∈Aff－1［Kn］，T:y→v=MTy+CT∈Aff－1［Km］分别为 Kn、Km上随机选取的可逆仿射变换，MS、MT分别是F上的n阶矩阵，CS、CT是F上的n维向量。它们共同掩藏中心映射Q的结构，是私钥的重要部分。

中心映射Q，也称核映射，构成中心映射的方程成为中心方程，它是n个变量m个多项式组成的方程组:

Q(x1，x2，…，xn)→(q1(x1，x2，…，xn)，q2(x1，x2，…，xn)，…，qm(x1，x2，…，xn))，Q 的结构可以公开也可以保密，三元组(T，Q，S)为私钥，对应的公钥即为:

1 MFE加密方案及其相关问题

1.1 MFE 加密方案

设K为有限域，L为其r次扩域，即中等扩域“Medium Field”。定义K-线性同构π:L→Kr，即取L在K上的一组基［θ1，θ2，…，θr］，则 π 为:π［a1θ1+a2θ2+ … +arθr］=［a1，a2，…，ar］，a1，a2，…，ar∈K。

自然地可推得两个K-线性同构π1:L12→K12r和π2:L15→K15r。MFE的私钥由定义在K12r和K15r上的两个可逆仿射变换 Φ1和 Φ3构成。Φ2:L12→L15为中心映射。中心映射 Φ2:［X1，X2，…，X12］=［Y1，Y2，…，Y15］表达如下:

其中Q1，Q2，Q3构成一个三元组［Q1，Q2，Q3］，为K4r到自身的三角形映射。加密是对公钥方程组赋值的过程，解密则依次计算 φ－11°π1°φ－12°π－12°φ－13。关键是计算 φ－12，可通过 φ2的三角结构来解决。首先将 X1，X2，…，X12，Y1，Y2，…，Y15写成 6 个 2 阶矩阵:

依次令为 M1，M2，M3，Z1，Z2，Z3，，则中心映射对应即:Z1=M1M2，Z2=M1M3，Z3=M1M4，则有:

当 M1，M2，M3均可逆，已知密文 Y4，Y5，…，Y15，由式(1)可分别得到 det M1，det M2，det M3，再由式(1)中的前3个等式可得X1，X2，X3，进而由det M1式求出X4。进而令A=(det M1)－1，则:

1.2 SOLE 攻击方法

设M*是二阶矩阵M的伴随矩阵。由:

方程关于明文分量ui为线性，密文分量vj是二次。故称之为二阶线性化方程Second Order Linearization Equation，简称 SOLE。

在唯密文攻击时，首先将足够多明密文对代入式(3)，确定出线性独立的SOLEs，然后代入已知的密文分量，通过Gauss消元法减少明文分量，再代入原公钥方程，得到具有较少变量数的新的公钥方程组。当明文分量的个数足够小时，就利用Grobner基的方法求出明文值。

2 改进的MFE加密方案及其方案分析

2.1 改进的MFE加密方案

类似的，K为特征为2的基域，L为扩域。两个K-线性同构和。重新定义中心映射:

把式(6)代入式(4)前3个等式里，可求出 X1，X2，…，X3，再由求出 X4，余下的等式求出 X5，X6，…，X12，令

2.2 性能分析

(1)任何一个MPKC都将拥有一种不同的中心映射，而中心映射Q:Fn→Fm并非一定为双射，为确定唯一原像可采用一些技巧，即先由一个固定的扩展函数或Hash函数将明文增加一个冗余，改进方案经过如下扩展:

然后又具体到一般，将其总结，得到一般的明文长度为4n(n≥3)的高次MFE加密方案，同时得到的扩展的长度为2n2－n(n≥3)，这样就可以保证密文得到唯一的原文。

(2)在特征为2的域上进行乘、逆运算时，常常把域扩张看成幂形式的二次扩张。扩张的次数越多，该域上计算量也呈非线性的增大。由于新方案是由五次多变量多项式方程组构成，因而可取更小的域K和L。密钥大小:设n=12r，m=15r，私钥即映射φ1，φ3及Qi中方程的系数，约n2+m2。公钥大小为公钥方程φ2的系数量。虽然新方案的公钥长度有所增加，但是可以取更小的参数r和K使运算在更小的域上进行，就可以在一定程度上平衡由于公钥量的增大所带来的开销，同时可进一步提高其运算速度。

2.3 安全性分析

2.3.1 SOLE 攻击

在式(3)中的二阶线性化方程，关于密文分量为二次，明文分量为一次，因此等式中应包含中某两个的乘积。不妨设等式左端包含，即:

2.3.2 秩攻击

秩攻击包括高秩攻击、低秩攻击和分离的油醋攻击。它们都是MQ方案基陷门STS或UOV的基本攻击。其中高秩攻击和低秩序攻击的基本思想是将公钥方程的二次项部分写成对称矩阵的形式，通过寻找具有某些特殊秩的矩阵的线性组合来恢复私钥。但是新方案公钥方程为五次，目前为止还无有效办法把五次项转化为对称矩阵的形式。因此秩攻击无效。

2.3.3 Grobner基攻击

求解一族多变量方程组的经典算法是构造Grobner基利用Buchberger算法来解决。该算法是按一定次序将单项式排序，通过适当系数的两个多项式将首项单项式消掉，不断执行该过程进行消元，直至最后一个变量。但随着消项过程的不断进行剩余单项式的次数将急速增长。分析表明，该算法复杂度平均为单指数级，最差达到双指数级，故仅适用于中等数值个变量。尽管目前对高次方程组算法复杂度尚不清楚。

3 结论

MFE是第一个定义在较小域上的MPKC，因此相对于以往定义在大域的体制来说具有更快的加密体制，遗憾的是其中心映射不一定是双射，而且不能抵抗SOLE攻击和秩攻击。在原有的基础上，通过重新设计中心映射，提出一种改进方案。新方案不仅能抵抗各种攻击，而且对一定固定的明文长度都可以进行加密，安全性更高，保证了可以确定唯一原像。同时如果能使公钥方程组为稀疏多项式，则更能有效的减少公钥大小，进一步提高算法效率。

［1］王鑫，张美玲，王新梅.高次MFE多变量加密方案［J］.四川大学学报:工程科学版，2009，41(4):171-174

［2］王志伟，郑世慧，杨义先，等.改进的Medium-Field多变量公钥加密方案［J］.电子科技大学学报，2007，36(6):1152-1159

［3］吕文刚，王尚平.MFE多变量加密方案研究［D］.西安:西安理工大学

［4］DOUGLASR S.Cryptography Theory and Practice Third Edition［M］.Canada:Electronics Industry，2011

［5］万哲先.代数和编码［M］.3版.北京:高等教育出版社:2009

［6］王后珍，张焕国，管海明，等.多变量代数理论及其在密码学中的应用［J］.北京:北京工业大学学报，2010，36(5):627-634

［7］袁峰，胡予濮，欧海文，等.多变量公钥密码中等价密钥问题［J］.北京:北京邮电大学学报，2010，33(3):97-101

［8］孙小雁，张茂胜.多模式多变量公钥密码体制［J］.计算机工程与设计，2012，33(11):4095-4099