立方多變量公鑰密碼體制的最小秩分析

張 棲，聶旭云

（1.電子科技大學(xué)信息與軟件工程學(xué)院，成都 610054；2.網(wǎng)絡(luò)與數(shù)據(jù)安全四川省重點實驗室（電子科技大學(xué)），成都 610054）

（*通信作者電子郵箱1106845293@qq.com）

0 引言

自1988 年Matsumoto 和Imai 首次提出具有里程碑意義的MI（Matsumoto Imai）多變量公鑰密碼體制（Multivariate Public Key Cryptosystem，MPKC）［1］以來，該密碼學(xué)原語的設(shè)計與安全性分析逐漸成為密碼學(xué)界與信息安全界的一個研究熱點。

多變量公鑰密碼體制的安全性基于求解有限域上隨機產(chǎn)生的多變量二次多項式方程組（Multivariate Quadratic，MQ）的問題，它是一個NP-困難問題。MQ 問題也可擴展為求解有限域上隨機產(chǎn)生的多變量三次多項式方程組（Multivariate Cubic，MC）的問題。多變量公鑰密碼體制一般由兩個仿射變換和一個中心映射復(fù)合而成，其中復(fù)合函數(shù)的表達式為公鑰，兩個仿射變換為私鑰。多變量公鑰密碼體制的構(gòu)造關(guān)鍵在于它的中心映射的構(gòu)造，而針對多變量公鑰密碼的安全性分析也集中在分析其中心映射。關(guān)于多變量公鑰密碼體制的更多詳細描述可參考文獻［2］。

最小秩問題（MinRank Problem，MR Problem）指的是給定正整數(shù)m、n、r、j及j個矩陣M0，M1，…，Mj-1∈Mm×n(K)，確定是否存在一組系數(shù)λ1，λ2，…，λj-1∈K，使得

這是一個NP-困難問題。

每一個多變量二次多項式中的齊二次項可用一個對稱矩陣來表示。公鑰多項式對應(yīng)的矩陣能夠表示成為中心映射多項式對應(yīng)的矩陣的線性組合。一旦中心矩陣多項式對應(yīng)的矩陣的秩較小，就可以采用最小秩攻擊（MinRank Attack，MR Attack）來嘗試恢復(fù)私鑰。事實上，最小秩攻擊，就是利用在公鑰多項式對應(yīng)的矩陣的線性組合中尋找具有最小秩矩陣來還原其私鑰-線性仿射變換U。

這一類攻擊最早是由Kipnis 等［3］提出用于分析隱藏域方程（Hidden Field Equations，HFE）加密體制的安全性。2013年，Bettale 等［4］改進了Kipnis等的攻擊方法破解了multi-HFE。Zhang等［5］利用秩攻擊破解了Yasuda等提出的一個簽名方案，并提出了一種改進方案來抵擋秩攻擊［6］。秩攻擊同樣可用于分析不平衡油醋類（Unbalanced Oil and Vinegar，UOV）簽名體制［7］。在秩攻擊的要求下，該類體制一般要求醋變量的個數(shù)是油變量個數(shù)的兩倍。Yasuda 等［8］基于彩虹體制（Rainbow）提出了一種改進的數(shù)字簽名方案，但很快就被Perlner 等［9］用最小秩攻擊所破解了，Ikematsu 等［10］借鑒了該體制的思想，提出一種基于HFE 體制的加密方案來抵抗最小秩攻擊。另外，秩攻擊還可以在其他密碼學(xué)領(lǐng)域作為安全性分析方法，如認證方案（Authentication Scheme）［11］。

Square 加密方案［12］與MI 體制和HFE 體制一樣，是屬于“小域-大域”方案，即其公鑰是有限域K上的多變量二次多項式，而其中心映射是K的擴域上的單變量平方運算。相對于HFE 體制而言，Square體制極大地縮減了加密和解密成本，但同時該體制既存在差分對稱性［13］，也具有最小秩缺陷。立方加密方案［14］是Square方案的改進。通過將中心映射改為擴域上的單變量立方運算，使得公鑰多項式的次數(shù)由二次提升到三次，來抵抗針對具有低秩中心映射的二次多變量公鑰密碼體制的最小秩攻擊。本文分析表明，立方加密方案的中心映射經(jīng)過差分過后，具有和Square 方案的一樣的低秩缺陷。因此，立方加密方案的公鑰差分后得到的系數(shù)矩陣，也具有低秩線性組合。結(jié)合改進的Kipnis-Shamir 方法［4］，即可恢復(fù)該體制的私鑰。

1 預(yù)備知識

1.1 多變量公鑰密碼體制的一般形式

令k=Fq是一個q元域，n和m是兩個正整數(shù)。U和T分別是kn和km上的兩個隨機選取的仿射變換，F(xiàn)：kn→km稱為中心映射。x=(x1，x2，…，xn)為明文變量，y=(y1，y2，…，ym)為密文變量。令

函數(shù)P=U°F°T的表達式為多變量公鑰密碼體制的公鑰，通常為一組多變量二次多項式。U和T為私鑰。

注意，若在大域上構(gòu)造中心映射F，需引入k-線性同構(gòu)φ：K→kn。其中K為k的n次擴域，F(xiàn)為K上的單變量多項式。公鑰形式如下：

1.2 最小秩攻擊

最小秩攻擊是一個NP-困難問題。在r比較小的時候，問題可解。

Kipnis 等［3］首先使用最小秩攻擊來分析HFE 公鑰密碼體制，其方法被稱為Kipnis-Shamir方法。

觀察P=U°φ°F°φ-1°T，P是已知的公鑰，U、T和f是未知的私鑰。在文獻［3］中，作者提出可以通過k-線性同構(gòu)φ將公鑰P提升到大域上得到P*，方法如下：

公式兩邊同時復(fù)合U*-1，可得到U*-1°P*=F°T*，由這個方程，最終可以得到“基本方程”，如下：

其中：P*k表示矩陣P*的每個元素經(jīng)過qk冪次提升，uk(k=0，1，…，n-1)表示矩陣U的第一列元素。如果矩陣F的秩r是有界的，那么P'的秩也是有界的。當(dāng)秩r足夠小時，恢復(fù)uk就可以規(guī)約到求解最小秩問題。

如何求解最小秩問題，Kipnis 和Shamir 提出了Kipnis-Shamir模型［3］。對于一個秩為r的線性組合，它一定存在n-r維的左核，可以根據(jù)已知的k個齊次公鑰矩陣和確定的秩r，得到一個由r(n-r)+k個變量n(n-r)個方程組成的多項式系統(tǒng)。

注意，Kipnis-Shamir 方法需要使用k-線性同構(gòu)將公鑰矩陣從小域提升到大域，這導(dǎo)致后續(xù)最小秩問題求解的成本增加。Bettale 等［4］基于Kipnis-Shamir 方法提出了一種改進方法，不需要將公鑰從小域提升到大域，可以直接求解最小秩問題，極大地提升了最小秩問題的求解速度。本文實驗部分也是采用這種方法。

1.3 Square加密方案

Square 加密方案［12］是Baena 等根據(jù)HFE 方案的設(shè)計思想設(shè)計而成。令k為特征值為q的有限域，K是k的n次擴域。φ：K→kn是標準k-線性同構(gòu)，φ-1為它的逆。Square體制的中心映射為：F：Y=X2。為了保證該映射可逆，需滿足gcd(2，qn-1)=1。

和多變量公鑰密碼體制的一般形式一樣，它的公鑰P=U°f°T=U°φ°F°φ-1°T，私鑰為U，T和F。對明文變量加密是通過求解P(x)=y完成，解密是通過對三個映射U、T和F的求逆完成。

根據(jù)它的中心映射的形式，可確定其對應(yīng)系數(shù)矩陣的秩為1。也就是說，該體制的公鑰在經(jīng)過同構(gòu)變換從小域映射到大域后，所對應(yīng)的系數(shù)矩陣存在在一組秩為1 的線性組合，形式如下：

使用Kipnis-Shamir 模型，求解即可得到uk。完整的私鑰恢復(fù)過程可參考文獻［3］。

1.4 立方加密方案

立方加密方案是根據(jù)Square 加密方案改進而成，該方案的中心映射為：F：Y=X3。為了保證該映射可逆，需滿足gcd(3，qn-1)=1，這就要求q≡2(mod 3)且q為奇數(shù)。設(shè)d為滿 足3t≡1(mod(qn-1)) 的整數(shù)，則F-1為X=F-1(Y)=。

相較于Square 加密方案，該方案中心映射的次數(shù)由2 增加到3，它的公鑰矩陣也由二維矩陣擴展到三維矩陣。盡管最小秩問題可以由二維矩陣擴展到三維矩陣，但如何確定一個三維矩陣的秩是非常困難的，甚至很難知道一個三維矩陣可能有的最大秩［15］。

2 立方加密方案的最小秩分析

雖然立方加密方案可以抵抗針對二維矩陣的最小秩攻擊，但經(jīng)過分析，可發(fā)現(xiàn)該體制的中心映射差分過后具有和Square方案中心映射相似的性質(zhì)，在A點的差分結(jié)果如下：

差分過后齊二次項對應(yīng)矩陣和Square方案中心映射對應(yīng)矩陣的秩相等，并且立方加密方案的公鑰經(jīng)過差分后，逆向推導(dǎo)的中心映射F'的性質(zhì)和DF(X，A)相似，關(guān)系如下：

其中a∈kn，F(xiàn)'是秩為1 的二次多項式，DP(x，a)表示公鑰多項式P1，P2，…，Pn在a點的差分。對于這種低秩中心映射，可以使用最小秩攻擊恢復(fù)其私鑰。同時，為了降低計算成本，本文采用一種擴展的Kipnis-Shamir 方法［4］。這種方法通過將k-線性同構(gòu)φ及它的逆φ-1表示成矩陣形式，不需引入另外的φ，可直接在小域上求解最小秩問題。

2.1 改進的Kipnis-Shamir方法

命題1［4］設(shè)(θ1，θ2，…，θn)∈Kn為域K基于域k上的一組基，Mn∈Kn×n是一個由這組基經(jīng)過Frobenius 變換得到的矩陣，形式如下：

k-線性同構(gòu)φ：K→kn可以表示成如下形式：

它的逆φ-1可表示成：

(v1，v2，…，vn)?Mn[1]表示該向量第一個元素。

命 題2［4］設(shè)矩陣A=[ai，j]∈kn×n，矩 陣B=[bi，j]=A?Mn∈Kn×n，則矩陣B的各列存在如下關(guān)系：

在得到Mn后，即可使用矩陣乘積來表示復(fù)合映射DP(x，a)=U°φ°F'°φ-1°T。首先取多項式組DP(x，a)的齊二次項系數(shù)矩陣，得到G1，G2，…，Gn。令h1，h2，…，hn=φ-1°F'°φ表示基域多項式組，它們的系數(shù)矩陣為H1，H2，…，Hn。根據(jù)式（4）和（5），可以用矩陣Mn來表示這組系數(shù)矩陣，形式如下：

其中：F*k表示中心映射F'的qk次冪的系數(shù)矩陣，它的元素表示為。復(fù)合映射的矩陣表示過程如下：

將式（6）代入，得：

令(s0，0，s1，0，…，sn-1，0)為矩陣S的第一列元素，則根據(jù)式（8），可得到“基本方程”，如下：

由前文分析可知，矩陣F'的秩r為1，則恢復(fù)si，0(0 ≤i≤n-1)可以規(guī)約到最小秩問題的求解。

2.2 實驗步驟及結(jié)果

完整的實驗過程可在普通PC上用MAGMA實現(xiàn)，PC的配置為：Inter Core i5-4300U CPU，2.50 GHz，8 GB 內(nèi)存。給定q，n，秩r=1，具體實驗步驟如下：

步驟1 對于給定公鑰P1，P2…，Pn，依次求解出差分，得到差分過后二次項所對應(yīng)系數(shù)矩陣G1，G2，…，Gn。

步驟2 生成一個(n-r) ×n的矩陣KM，形式如下：

矩陣行向量是線性無關(guān)的。根據(jù)式（7），存在非零向量(s0，0，s1，0，…，sn-1，0)，使 得。求解得到(s0，0，s1，0，…，sn-1，0)，根據(jù)命題2，即可恢復(fù)完整的矩陣S：

步驟3 在恢復(fù)U后，令(w0，0，w1，0，…，wn-1，0)為矩陣W的第一列元素，矩陣K為的左核，可得到如下方程組：

其中l(wèi)=1，2，…，r，F(xiàn)robi(K)表示K的每列元素經(jīng)過Frobenius變換［4］后得到的矩陣。求解出這個方程組后，根據(jù)命題2，即可恢復(fù)W：

步驟4 公鑰已知，在成功恢復(fù)矩陣MU和MT后，根據(jù)P=U°φ°F°φ-1°T，逆向恢復(fù)中心映射F。

文獻［14］中的推薦參數(shù)為n=15，q=59，r=1。根據(jù)文獻［16］，該攻擊的計算復(fù)雜度主要由最小秩問題求解決定，為：

由于域的大小并不會影響理論分析的結(jié)果，因此，在實驗中，令q=5，n的大小不超過30。實驗運行時間和復(fù)雜度估計如表1 所示。從表1中可以看出，攻擊的效率較高，符合理論分析的結(jié)果。

表1 不同參數(shù)下最小秩攻擊的代價和破解時間的比較Tab.1 Comparison of cost and cracking time of MinRank attack under different parameters

為了能夠讓該體制抵抗最小秩攻擊，同時考慮到效率問題，本文建議使用減方法來提高該體制的安全性，減去的公鑰多項式個數(shù)為s=2。

2.3 實例

為了更清楚闡述攻擊流程，在本節(jié)展示一個具體實例。同時為了簡化計算流程，本實例采用可逆線性變換而不是仿射變換。令q=5，n=7，線性變換U和T的系數(shù)矩陣MU、MT分別為：

恢復(fù)得到的U，T，F(xiàn)即為一組等價密鑰。

3 結(jié)語

本文結(jié)合差分方法和最小秩攻擊方法，對立方多變量公鑰加密體制進行了安全性分析，發(fā)現(xiàn)該體制中心映射經(jīng)過差分后具有低秩缺陷，利用本文的攻擊方法可成功地恢復(fù)體制的私鑰。對立方多變量公鑰加密體制使用減方法增強后可得到立方多變量公鑰簽名體制。減方法在減去一定個數(shù)的公鑰多項式后，剩余的公鑰多項式差分后所對應(yīng)的系數(shù)矩陣不能構(gòu)成差分后中心映射對應(yīng)矩陣的線性組合，使得最小秩攻擊無法對其產(chǎn)生作用。未來的工作中，將進一步分析該簽名體制的安全性。