趙菲菲，魏仕民

(淮北師范大學(xué)數(shù)學(xué)科學(xué)學(xué)院，安徽淮北235000)

量子計算機的發(fā)展對目前廣泛使用的公鑰密碼體制構(gòu)成了潛在的威脅。而多變量公鑰密碼體制被認為是能抵御未來基于量子計算機攻擊的幾種公鑰密碼體制之一，其安全性基于有限域上求解多變量多項式方程組為一NP-C問題。體制具有較高的效率和安全性，且易于硬件實現(xiàn)，因此被認作量子計算機時代一種安全的密碼體制和數(shù)字簽名備選方案。

多變量公鑰密碼體制代數(shù)結(jié)構(gòu)龐大。設(shè)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的結(jié)構(gòu)，是私鑰的重要部分。

中心映射Q，也稱核映射，構(gòu)成中心映射的方程成為中心方程，它是n個變量m個多項式組成的方程組:

Q(x1，x2，…，xn)→(q1(x1，x2，…，xn)，q2(x1，x2，…，xn)，…，qm(x1，x2，…，xn))，Q 的結(jié)構(gòu)可以公開也可以保密，三元組(T，Q，S)為私鑰，對應(yīng)的公鑰即為:

1 MFE加密方案及其相關(guān)問題

1.1 MFE 加密方案

設(shè)K為有限域，L為其r次擴域，即中等擴域“Medium Field”。定義K-線性同構(gòu)π:L→Kr，即取L在K上的一組基［θ1，θ2，…，θr］，則 π 為:π［a1θ1+a2θ2+ … +arθr］=［a1，a2，…，ar］，a1，a2，…，ar∈K。

自然地可推得兩個K-線性同構(gòu)π1:L12→K12r和π2:L15→K15r。MFE的私鑰由定義在K12r和K15r上的兩個可逆仿射變換 Φ1和 Φ3構(gòu)成。Φ2:L12→L15為中心映射。中心映射 Φ2:［X1，X2，…，X12］=［Y1，Y2，…，Y15］表達如下:

其中Q1，Q2，Q3構(gòu)成一個三元組［Q1，Q2，Q3］，為K4r到自身的三角形映射。加密是對公鑰方程組賦值的過程，解密則依次計算 φ－11°π1°φ－12°π－12°φ－13。關(guān)鍵是計算 φ－12，可通過 φ2的三角結(jié)構(gòu)來解決。首先將 X1，X2，…，X12，Y1，Y2，…，Y15寫成 6 個 2 階矩陣:

依次令為 M1，M2，M3，Z1，Z2，Z3，，則中心映射對應(yīng)即:Z1=M1M2，Z2=M1M3，Z3=M1M4，則有:

當(dāng) M1，M2，M3均可逆，已知密文 Y4，Y5，…，Y15，由式(1)可分別得到 det M1，det M2，det M3，再由式(1)中的前3個等式可得X1，X2，X3，進而由det M1式求出X4。進而令A(yù)=(det M1)－1，則:

1.2 SOLE 攻擊方法

設(shè)M*是二階矩陣M的伴隨矩陣。由:

方程關(guān)于明文分量ui為線性，密文分量vj是二次。故稱之為二階線性化方程Second Order Linearization Equation，簡稱 SOLE。

在唯密文攻擊時，首先將足夠多明密文對代入式(3)，確定出線性獨立的SOLEs，然后代入已知的密文分量，通過Gauss消元法減少明文分量，再代入原公鑰方程，得到具有較少變量數(shù)的新的公鑰方程組。當(dāng)明文分量的個數(shù)足夠小時，就利用Grobner基的方法求出明文值。

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

2.1 改進的MFE加密方案

類似的，K為特征為2的基域，L為擴域。兩個K-線性同構(gòu)和。重新定義中心映射:

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

2.2 性能分析

(1)任何一個MPKC都將擁有一種不同的中心映射，而中心映射Q:Fn→Fm并非一定為雙射，為確定唯一原像可采用一些技巧，即先由一個固定的擴展函數(shù)或Hash函數(shù)將明文增加一個冗余，改進方案經(jīng)過如下擴展:

然后又具體到一般，將其總結(jié)，得到一般的明文長度為4n(n≥3)的高次MFE加密方案，同時得到的擴展的長度為2n2－n(n≥3)，這樣就可以保證密文得到唯一的原文。

(2)在特征為2的域上進行乘、逆運算時，常常把域擴張看成冪形式的二次擴張。擴張的次數(shù)越多，該域上計算量也呈非線性的增大。由于新方案是由五次多變量多項式方程組構(gòu)成，因而可取更小的域K和L。密鑰大小:設(shè)n=12r，m=15r，私鑰即映射φ1，φ3及Qi中方程的系數(shù)，約n2+m2。公鑰大小為公鑰方程φ2的系數(shù)量。雖然新方案的公鑰長度有所增加，但是可以取更小的參數(shù)r和K使運算在更小的域上進行，就可以在一定程度上平衡由于公鑰量的增大所帶來的開銷，同時可進一步提高其運算速度。

2.3 安全性分析

2.3.1 SOLE 攻擊

在式(3)中的二階線性化方程，關(guān)于密文分量為二次，明文分量為一次，因此等式中應(yīng)包含中某兩個的乘積。不妨設(shè)等式左端包含，即:

2.3.2 秩攻擊

秩攻擊包括高秩攻擊、低秩攻擊和分離的油醋攻擊。它們都是MQ方案基陷門STS或UOV的基本攻擊。其中高秩攻擊和低秩序攻擊的基本思想是將公鑰方程的二次項部分寫成對稱矩陣的形式，通過尋找具有某些特殊秩的矩陣的線性組合來恢復(fù)私鑰。但是新方案公鑰方程為五次，目前為止還無有效辦法把五次項轉(zhuǎn)化為對稱矩陣的形式。因此秩攻擊無效。

2.3.3 Grobner基攻擊

求解一族多變量方程組的經(jīng)典算法是構(gòu)造Grobner基利用Buchberger算法來解決。該算法是按一定次序?qū)雾検脚判颍ㄟ^適當(dāng)系數(shù)的兩個多項式將首項單項式消掉，不斷執(zhí)行該過程進行消元，直至最后一個變量。但隨著消項過程的不斷進行剩余單項式的次數(shù)將急速增長。分析表明，該算法復(fù)雜度平均為單指數(shù)級，最差達到雙指數(shù)級，故僅適用于中等數(shù)值個變量。盡管目前對高次方程組算法復(fù)雜度尚不清楚。

3 結(jié)論

MFE是第一個定義在較小域上的MPKC，因此相對于以往定義在大域的體制來說具有更快的加密體制，遺憾的是其中心映射不一定是雙射，而且不能抵抗SOLE攻擊和秩攻擊。在原有的基礎(chǔ)上，通過重新設(shè)計中心映射，提出一種改進方案。新方案不僅能抵抗各種攻擊，而且對一定固定的明文長度都可以進行加密，安全性更高，保證了可以確定唯一原像。同時如果能使公鑰方程組為稀疏多項式，則更能有效的減少公鑰大小，進一步提高算法效率。

［1］王鑫，張美玲，王新梅.高次MFE多變量加密方案［J］.四川大學(xué)學(xué)報:工程科學(xué)版，2009，41(4):171-174

［2］王志偉，鄭世慧，楊義先，等.改進的Medium-Field多變量公鑰加密方案［J］.電子科技大學(xué)學(xué)報，2007，36(6):1152-1159

［3］呂文剛，王尚平.MFE多變量加密方案研究［D］.西安:西安理工大學(xué)

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

［5］萬哲先.代數(shù)和編碼［M］.3版.北京:高等教育出版社:2009

［6］王后珍，張煥國，管海明，等.多變量代數(shù)理論及其在密碼學(xué)中的應(yīng)用［J］.北京:北京工業(yè)大學(xué)學(xué)報，2010，36(5):627-634

［7］袁峰，胡予濮，歐海文，等.多變量公鑰密碼中等價密鑰問題［J］.北京:北京郵電大學(xué)學(xué)報，2010，33(3):97-101

［8］孫小雁，張茂勝.多模式多變量公鑰密碼體制［J］.計算機工程與設(shè)計，2012，33(11):4095-4099