多變量公鑰密碼進展

韓益亮

（武警工程大學(xué) 密碼工程學(xué)院，陜西 西安710086）

0 引言

近年來，量子計算理論與量子計算機不斷取得新的進展，現(xiàn)代公鑰密碼面臨的威脅日益嚴(yán)峻。由于對抗量子密碼的迫切需求，在2006年比利時召開的第一屆國際抗量子密碼學(xué)會議上，多變量公鑰密碼、基于格的密碼、基于糾錯碼的密碼和基于散列函數(shù)的簽名等被作為抗量子攻擊的候選方案。相比于其他抗量子密碼，多變量公鑰密碼的研究起步相對較早，現(xiàn)已有較多成熟的多變量公鑰密碼算法。多變量公鑰密碼的安全性是建立在有限域上多元非線性方程組的求解問題上的。該問題的最普通形式即：求解在只有兩個元素的有限域上的二次方程組，這被證明是一個NP困難問題。在這個問題的求解上，量子計算機比起傳統(tǒng)電子計算機也并沒有明顯的優(yōu)勢，多變量公鑰密碼可以良好地抵抗量子計算。它相比于其他抗量子密碼具有加解密速度快、消耗資源少的優(yōu)良特點，但是其公鑰尺寸一般較大。

1 多變量公鑰密碼研究現(xiàn)狀

多變量公鑰密碼系統(tǒng)[1-3]的研究，最早在1984年Ong和 Schnorr發(fā)表的文章[4]中就有所涉及。而從完整體制的角度來講，文獻[5]提出的MI（或稱為C*）加密體制才算是真正意義上的多變量公鑰密碼系統(tǒng)，MI方案的提出開啟了多變量公鑰密碼研究和發(fā)展的大門。

雖然在1995年，Patarin提出的線性化方程攻擊攻破了MI體制，但在此之后又產(chǎn)生了很多新方案。1996年P(guān)atarin在攻破MI方案后，提出了隱藏域方程（Hidden Field Equation，HFE）方 案[6]， 但 是 緊 接 著HFE方案又被Kipnis和Shamir[7]分析證明不安全。于是，1997年P(guān)atarin利用線性化方程攻擊的思想，設(shè) 計 了 油 醋（Oil-Vinegar，OV）簽 名 算 法[8]。 然 后 ，Kipnis和Shamir用油醋分離方法攻擊了OV方案，并進一步改進OV方案提出了不平衡油醋（Unbalance Oil-Vinegar，UOV）方案[9]。只要參數(shù)選擇合適，UOV方案將會是一個安全的多變量簽名方案。另一方面，研究人員通過各種變形的方法，如加方法、減方法以及內(nèi)部擾動方法，對 MI、HFE方案進行了改進，提出了很多安全性得到提高的新方案，這方面比較著名的變形方案有：SFLASH簽名方案[10]、Rainbow 簽 名 方 案[11]、PMI（Perturbated MI）[12]、PMI+[13]、HFE±[6]、HFE-[6]、IPHFE（Internal Perturbation of HFE）[14]、HFEv[9，14]以及 Quartz[15]等。 這些年來，無 論是 國 內(nèi)還是國外的學(xué)者，針對多變量公鑰密碼的核心映射構(gòu)造問題，又提出了很多新方案，如2012年Huang等人通過研究新的多變量二次假設(shè)提出了可證明安全的多變量加密方案[16]；2013年 Yasuda等人提出了用二次型構(gòu)造的多變量簽名方案[17]，Gao等人[18]提出了以求解多項式環(huán)上diophantine方程為基礎(chǔ)的多變量密碼系統(tǒng)，Tao等人以矩陣構(gòu)造核心映射提出的 Simple Matrix[19]方案，Shen等人提出基于身份的多變量密碼方案 IBUOV[20]，Yasuda等人提出私鑰更短的 Rainbow方案[21]；2014年 Zhang等人提出新的擾動方法構(gòu)造的 MI簽名方案[22]，Yasuda等人提出的NT-Rainbow[23]以及使用稀疏私鑰的新Rainbow變種方案[24]，Ding等人提出的 Cubic Simple Matrix方案[25]以及 Porras等人提出的 ZHFE方案[26]等。到目前為止，雖然新方案很多，但是根據(jù)它們構(gòu)造的特點，主要可以歸納為以下四種體制：MI體制、隱藏域方程組（HFE）體制、平衡油醋（OV）體制和三角體 制（Triangular Systems，TS，包 括 STS），具 體 將 在 下一章節(jié)將進行介紹。

當(dāng)然，除了以上針對核心映射構(gòu)造所做的工作以外，還有對多變量公鑰密碼的密碼攻擊分析研究，比較常見的攻擊方法大致可以分為兩種類型：結(jié)構(gòu)攻擊和直接攻擊。結(jié)構(gòu)攻擊方法主要是線性化方程攻擊、高秩攻擊[27]、低秩攻擊[28]、分離油醋攻擊[8]、差分攻擊[29]、Kipnis-Shamir攻擊[7]、擴域結(jié)構(gòu)攻擊等；直接攻擊方法主要是窮舉搜索、解非線性方程攻擊[30]（包括 XL 算法和 Gr?bner基算法）、Zhuang-zi算法[31]等，其中秩攻擊、差分攻擊和解非線性方程攻擊都已經(jīng)是比較成熟的攻擊方法，是研究人員分析新方案是否安全的有效手段。另外，對多變量公鑰密碼系統(tǒng)的攻擊，除了利用結(jié)構(gòu)攻擊、直接攻擊兩種方法以外，結(jié)合以上幾種具體方法也能起到很好的作用，如Wolf等人利用多種攻擊相結(jié)合的方法攻破了STS、TTS方案[32]，所以這也是分析多變量公鑰密碼方案的另外一種有效手段。另一方面，為了說明多變量密碼系統(tǒng)的可用性，安全問題是第一個需要考慮的問題，而除了一般的攻擊分析之外，借助合理理論假設(shè)證明方案的安全性也是一種很重要的研究方法，所以在安全性分析中還可以用到形式化安全證明的相關(guān)理論。

2 多變量密碼基礎(chǔ)知識

2.1 有限域上多元多項式方程組

（1）多元多項式方程組的一般形式

設(shè)有限域 F=GF（q），x1，x2，…，xn是其中的 n 個變量，關(guān)于n個變量的任意一個多項式可以表示為f1，多項式的次數(shù)為d，一個多項式組可以由m個這樣的多項式構(gòu)成，以 F 表示：F:=（f1，f2，…，fm）。 其中fi=∑aj∏xj，1≤j≤m，1≤j≤n。

以 y1，y2，…，ym表示 F上的 m個元素，則有限域上的多元多項式方程組可以表示為：

（2）二次多變量多項式方程組

當(dāng)上文中的d=2時，則稱為二次多變量多項式方程組，一般形式如下：

其 中 x1，x2， … ，xn∈F，y1，y2， … ，ym∈F，ai，j，k∈F 為二次項系數(shù)，bi，j∈F 為一次項系數(shù)，ci∈F 為常數(shù)項。

（3）MQ問題與IP問題

定義MQ問題：給定一組有限域F上的含n個變量，m個多項式的二次多變量多項式方程組，其結(jié)構(gòu) 式（2）所述 ，由 一 組 已 知 的 y1，y2，… ，ym∈F 及方程變換，求解出一組解 x1，x2，…，xn∈F以滿足方程組。

1979年Garey和Johnson證明了在二元域上的MQ問題是 NPC問題，Patarin等[33]于 1997年證明了任意域上的 MQ問題是 NP完全問題。即由 y1，y2，…，ym∈F及方程變換等信息得出方程組的解在計算上是不可行的。2016年Szepieniec A和Ding等人通過取消擴展域（EFC）介紹了MQ公鑰加密體制的新的中心陷門，它允許加密與簽名。2017年，Szepieniec等人實現(xiàn)將MQ簽名應(yīng)用于PKI中。

定義IP問題：設(shè)F和P是給定有限域F=GF（q）上包含m個多項式和n個變量的隨機多變量二次多項式方程組，在有限域F上尋找兩個可逆仿射變換 S∈Fm×∈Fm和 T∈Fn×∈Fn，使 F和 P滿足關(guān)系：F=S?P?T，則稱尋找這兩個可逆仿射變換的問題為IP問題。

2.2 多變量公鑰密碼的一般構(gòu)造

多變量公鑰密碼系統(tǒng)通常是建立在龐大的代數(shù)結(jié)構(gòu)之上，設(shè)F=GF（q）為有限域，則其公鑰為一組有限域F上的多變量多項式方程組構(gòu)成Φ：Fn→Fm

其具體陷門構(gòu)造方式如圖1所示。

圖1 陷門構(gòu)造方式

公鑰Φ可以看作是三個映射的合成Φ=L1?Φ?L2。L1和 L2為域 F上隨機選取的可逆仿射變換，其作用是將中心映射Φ′的結(jié)構(gòu)隱藏起來，中心映射Φ′同樣由一組n個變量m個方程的多變量多項式方程組構(gòu)成。則多變量公鑰密碼系統(tǒng)的私鑰為三元組（L1，Φ′，L2），一般情況下映射 Φ′保 密，也可以 公開；公鑰為 Φ（x1，x2，…，xn）=（f1，f2，…，fm）。

加密過程：對給定消息 x1，x2，…，xn加密，可得到 密 文 y1，y2， … ，ym，對 應(yīng) 每 一 個 yi，有 ：yi=fi（x1，x2，…，xn）。

映射Φ是公開的，則每個人都能完成對消息的加密。

解密過程：解密過程是加密過程的逆，即求Φ-1，通過私鑰信息可以很容易得到 Φ-1，則（x1，x2，…，xn）=Φ-1（y1，y2，…，ym）。

由于此過程當(dāng)中涉及用戶私鑰，則解密只能由持有私鑰的用戶來完成。

在多變量公鑰密碼系統(tǒng)當(dāng)中，核心映射Φ′的設(shè)計是關(guān)鍵，其安全性主要依賴于核心映射的安全性。為了更好地在實際中應(yīng)用，一般將核心映射選定為二次的，以節(jié)省存儲空間。仿射變換L1和L2的應(yīng)用分別用來隱藏中心映射的結(jié)構(gòu)和明文信息。

2.2.1 雙極系統(tǒng)

目前的多變量密碼方案可分為雙極（bipolar）系統(tǒng)和混合（mixed）系統(tǒng)，雙極系統(tǒng)設(shè)有限域F=GF（q），在一個雙極多變量密碼系統(tǒng)當(dāng)中，公鑰為Fn→Fm的映射Φ：

其中 f1為 F[x1，x2，…，xn]中的 n 元多項式。

其中心映射為Φ′，構(gòu)造過程如下：

（1）Φ ′（x′1，x′2， … ，x′n）=（f′1，f′2， … ，f′m）， 其 中f′i∈F[x1，x2，… ，xn]；

（2）對 于 映 射 Φ′（x′1，x′2， … ，x′n）=（y′1，y′2， … ，y′m）的計算可以很容易解決，相應(yīng)地也可以快速地找 到（y′1，y′2， … ，y′m）對 應(yīng) 的 唯 一 原 象（x′1，x′2， … ，x′n），即 Φ-1（y′1，y′2，… ，y′m）。

在這里Φ-1僅意味著求解原象，并不是說對Φ′求逆，即Φ′并不一定是可逆的。一旦找到符合要求的中心映射 Φ′，隨機選取合適的仿射變換 L1和 L2，就可以構(gòu)造出一個雙極多變量公鑰密碼方案。

雙極系統(tǒng)的公鑰包括兩部分：一是有限域F及其域結(jié)構(gòu)，二是映射Φ的m個多項式。私鑰為隨機選取的仿射變換 L1和L2，以及中心映射Φ′。

加密過程：需要加密的消息為 X=（x1，x2，…，xn），將消息值代入公鑰多項式，計算得到密文Y=Φ（X）=（y1，y2，…，ym）。

解密 過 程：密 文消 息 為 Y=（y1，y2，… ，ym），對 其解密即為求解方程：Y=Φ（X）。

首先求解 L1-1（Y）=Y′，然后計算 X′=Φ′-1（Y′），再計算明文 X=L2-1（X′）。

簽名過程：設(shè)需要簽名的消息為Y，則需求解方 程 Y=Φ（x1，x2，…，xn）， 以 得 到 方 程 的 解 X=（x1，x2，…，xn），X為簽名信息，即將解密的過程運行一次。

簽名驗證：將消息的簽名信息代入公鑰多項式，即可得到驗證。

雙極系統(tǒng)的主要思想是以仿射變換L1和L2來以隱藏中心映射Φ′，若沒有這兩個仿射變換，則核心映射的安全性將會受到威脅。當(dāng)前，多數(shù)多變量密碼體制都是基于雙極系統(tǒng)設(shè)計構(gòu)造的。

2.2.2 混合系統(tǒng)

同樣，混合型多變量公鑰密碼系統(tǒng)的公鑰也是在有限域下的映射，使用 Fn+m→Fl的映射，記為 H：

其 中 hi∈F[x1，x2，… ，xn，y1，y2， … ，ym]。 與 雙 極 系 統(tǒng)一樣，要構(gòu)造一個這樣的加密方案就需要找到相應(yīng)的中心映射 H′：Fn+m→Fl。

中心映射要滿足：對于任意給定的 x′1，x′2，…，x′n,方 程 組 H′（x′1，x′2， … ，x′n，y′1，y′2， … ，y′m）=（0，…，0）都很容易求解，并且在多數(shù)情況下，是一個關(guān)于變量 y′1，y′2，…，y′m的線性方程組。

找到符合要求的中心映射后，Φ可以表示為如下的形式：

其中L1和L2的定義與上一小節(jié)中的定義相同，L3則是一個從 Fl到Fl的線性映射。

混合系統(tǒng)的公鑰由兩部分組成：（1）有限域F及其域結(jié)構(gòu)；（2）構(gòu)成核心映射H的多項式方程。

混合多變量公鑰密碼系統(tǒng)的加密解密以及簽名等過程與雙極系統(tǒng)類似。其主要思想是利用三個仿射變換 L1、L2和 L3來隱藏方程 H（X，Y）=（0，…，0）。目前，基于混合系統(tǒng)的多變量公鑰密碼方案比較少，較為著名的有Patarin提出的Dragon加密體制。

3 多變量密碼的幾種陷門構(gòu)造技術(shù)

本小節(jié)針對幾種常見的陷門構(gòu)造進行介紹：UOV體制、STS體制、MI體制、HFE體制、MFE體制和l-IC體制，以及 PQC′2013上新提出的 Simple Matrix方案。

3.1 MI體制

MI體制是由Matsumoto和Imai提出的最早的多變量密碼方案，其主要理念是：以基域及其擴域構(gòu)造了一個多變量陷門。

設(shè)有限域 F=GF（q），E是 F的 n次擴域，π：E→Fn是擴域E到向量空間的同構(gòu)映射，正整數(shù)λ∈N滿足 gcd（qn-1，qλ+1）=1，則稱中心映射為如下形式的為 MI體制：

在此，條件 gcd（qn-1，qλ+1）=1可保證 Q 是一個可逆函數(shù)。

最原始的MI加密方案雖然已被攻破，但是其變型版本如Flash簽名體制[34]和 PMI+[13]較為可靠。加密體制仍然是值得研究和探索的，并且在實用領(lǐng)域，F(xiàn)lash簽名被NEESSIE計劃所采用，被應(yīng)用于低端智能卡；而后Ding等人結(jié)合內(nèi)部擾動方法，對MI體制做了改進，提出了 PMI+體制，到目前為止，并未出現(xiàn)一種針對此方案的有效攻擊算法。

3.2 HFE體制

隱域方程體制（Hidden Field Equations，HFE）是對MI體制（C*加密方案）的推廣，由 Patarin提出[6]，其核心映射建立在擴域上，由單變量多項式構(gòu)成，區(qū)別于MI體制核心映射的單變量單項式。

仍設(shè)有限域F=GF（q），E是F的n次擴域，π：E→Fn是擴域E到向量空間Fn的同構(gòu)映射，HFE體制的中心映射具有如下的形式：

其中 i，j∈N， 次數(shù) d∈N，Ci，j∈E 表示上式中二次項的系數(shù)，Bk∈E則代表其中一次項的系數(shù)，A∈E是常數(shù)項。

對于核心映射Q的求逆，需要利用Berlekamp算法（所有的運算都在有限域上進行），其計算復(fù)雜度為O（nd2logd+d3），因此，參數(shù) d的取值不能太大。

HFE密碼體制的主要變型有兩種：一是Quartz簽名體制[15]，一是 IPHFE[14]加密體制。HFE相關(guān)系統(tǒng)多年來受到了很多關(guān)注和各種密碼分析，2013年，Ding等人對HFEv-簽名方案的代數(shù)密碼分析的復(fù)雜性提出了第一個穩(wěn)定的理論估計。針對Kipnis-Shamir（KS）攻擊的minors建模方法對于 HFE非常有效，但是當(dāng)移除的方程數(shù)大于1時，導(dǎo)致失敗。2017年，Vates等人依然基于minors建模方法推出一個新的適用于HFE-的所有參數(shù)的密鑰恢復(fù)攻擊方法。2014年P(guān)orras等人提出了ZHFE方案，公鑰的核心映射是兩個高階HFE多項式構(gòu)造的。2016年，Baena等人對ZHFE進行改進，提出新的算法使得ZHFE生成密鑰的速度得到很大提升。但在2017年，Cabarcas等人發(fā)現(xiàn)利用ZHFE的低秩性質(zhì)可對其進行密鑰恢復(fù)攻擊。同年，Petzoldt、Ding等人提出了一個有效的多變量簽名HMFEv-，可以看作是Gui和Quartz的擴展版本，可抵御直接攻擊與Rank攻擊。

3.3 UOV體制

不平衡油醋密碼體制（Unbalanced Oil and Vinegar，UOV）是對平衡油醋體制（Oil and Vivegar，OV）的改進。1998年，Kipins和Shamir利用二次多項式定義的二次型相關(guān)的矩陣方法成功地攻擊了OV體制，偽造出了油醋體制的合法密鑰；在此基礎(chǔ)上，他們于1999年提出了不平衡油醋（UOV）體制。著名彩虹體制就是一種變形的油醋體制（即多層油醋體制[21]），多層油醋體制中的每一層都是油醋多項式，上一層中的所有變量都是下一層的醋變量。2013年，Petzoldt，Bulygin等人提出了一種運用Large Factor來縮短UOV和Rainbow簽名方案的公鑰方法，并實現(xiàn)了快速驗證。2017年，Ding等人在FPGA上完成對 Rainbow Signature的高速硬件實現(xiàn)。

油醋體制的中心映射是建立在基域之上，其結(jié)構(gòu)為：設(shè)有限域 F=GF（q），UOV的中心映射

在這里，x1，…，xo被稱為油變量“Oil”，x~1，…，x~n-o則稱為醋變量“Vinegar”。在此中心映射中，二次項是由醋變量與醋變量運算產(chǎn)生的，而與油變量相關(guān)的二次項只與醋變量結(jié)合產(chǎn)生，因此，當(dāng)醋變量的值給定后，上面的多項式方程組就成了關(guān)于油變量的線性方程組，可以根據(jù)高斯消元法很容易地得到方程組的解。

3.4 STS體制

三角階梯體制（Step-Wise Triangular Systems，STS）首先由Moh提出，其安全性可歸約到復(fù)合的非線性的可逆多項式映射分解的困難性上。將STS體制的中心映射定義為Q，其基本架構(gòu)介紹如下：

在上面的結(jié)構(gòu)當(dāng)中，1≤l≤L，l表示步數(shù)；nl表示在每步中增加的新變量的數(shù)量（步寬）；ml表示在每步中方程的數(shù)量（步高）。若以m和n分別表示方程的數(shù)目和自變量的數(shù)目，則一定存在關(guān)系n1+…+nL=n，m1+…+mL=m。

當(dāng)每一步的步寬和步長相同時n1=…=nL=m1=…=mL，稱此結(jié)構(gòu)為正則 STS，公式（10）描述的就是正則STS的結(jié)構(gòu)。

3.5 MFE體制

中間域（Medium-Field Extension Scheme，MFE）體制于2006年提出，由于核心映射中（有限域）域的擴張并沒有包含所有的變量，因此被稱之為“中間域”。MFE的核心映射采用了一種特殊的矩陣構(gòu)造，將明文與密文之間的對應(yīng)關(guān)系由這個矩陣來定義，由此構(gòu)造了一個與MI體制和HFE體制等不同的核心映射（即不采用單個的多項式的形式）。

與前述的多變量密碼體制相比，MFE具有如下明顯特點：（1）因為采用了中間域的思想，使得域的擴張次數(shù)減少，大大縮短了公鑰的長度，降低了計算復(fù)雜度；（2）MFE體制的核心映射采用了與Tame映射類似的形式，提高了密鑰生成的效率，從另一方面提高了方案的效率；（3）因MFE體制的核心映射與具有特殊構(gòu)造的矩陣存在對應(yīng)關(guān)系，使得破解方案的困難性加大，難以用常規(guī)的攻擊方法來破解此算法（從另一個角度促進了密碼分析方法的研究）。由Ding等人所提出的SOLE攻擊就是一種針對MFE體制有效的攻擊方式。

3.6 Simple Matrix方案

Simple Matrix（ABC）方案是在 2013年[20]由 Ding等人提出來的新的多變量加密方案。這是一種基于矩陣乘法的簡單高效的多變量公鑰加密方案，該方案沒有低秩的性質(zhì)。具體一點是指與中心映射相關(guān)的二次方程的形式不具有低秩的性質(zhì)，而其秩是與某個特定的參數(shù)n有關(guān)，進而可以加強對MinRank攻擊的防御。ABC方案的另一個亮點是解密計算速度非?？?，因為主要計算是解決某些線性方程。2014年，Ding等人對 Simple Matrix（ABC）方案進行了改進，提出了Cubic Simple Matrix加密方案[25]，使得安全性更高。通過利用具有隨機二次多項式的方陣，使得用代數(shù)攻擊破壞系統(tǒng)至少和求解一組隨機二次方程一樣難。此外，由于在矩陣中使用隨機多項式，與中心映射關(guān)聯(lián)的矩陣具有高秩，這防止了Rank攻擊，得到的公鑰是一個三次映射。

2014年，Smith-Tone等人根據(jù)ABC方案核心映射所固有的差分不變量提出了結(jié)構(gòu)性的密鑰恢復(fù)攻擊，在對原始方案及其推廣方案的攻擊方法中漸近最優(yōu)。2017年，Smith-Tone等人又對特征參數(shù)為2的Cubic ABC Simple Matrix加密方案的攻擊方法進行了改進。

4 針對多變量密碼的攻擊方法

除強力搜索攻擊外，針對多變量密碼體制的分析方法主要有：線性化方程、XL算法、Gr?bner基算法、秩攻擊及差分攻擊等。

4.1 解非線性化方程方法

XL算法和 Gr?bner基算法是主要的解非線性化方程的方法。

在多變量公鑰密碼系統(tǒng)當(dāng)中，將密文變量代入公鑰多項式，可以得到一組關(guān)于明文變量的多項式方程組Y=F（X），直接的想法就是解此非線性方程組，從而得到明文。XL算法的本質(zhì)是計算 Gr?bner基，可以看作是算法的一種冗余變體，目前最有效的求 Gr?bner基的方法是由 Faugere所提出的 F4和F5算法，利用F5算法，可以破解針對HFE體制的挑戰(zhàn) 1。文獻[35]中指出，F(xiàn)5算法通過計算Gr?bner基的方法破解多變量密碼算法的計算復(fù)雜度約為20.873n，其中 n為變量的數(shù)目。

4.2 線性化方程方法

線性化方程的攻擊方法最初是用來攻擊MI體制的，由Patarin[6]提出。線性化方程方法的原理是，在多變量密碼方案中，若密文變量yi和相應(yīng)的明文變量xi之間（首先要保證明文與密文的合法性）存在如下關(guān)系：

則稱此方案滿足線性化方程。

線性化方程攻擊方法的優(yōu)勢在于得到的線性化方程與密文無關(guān)，只要公鑰信息是已知的，則該過程就可以執(zhí)行，此方法的特點在于：若要攻擊已知其公鑰信息的密碼方案，則其所有的線性化方程都可以預(yù)先進行計算。

4.3 秩攻擊

秩攻擊是結(jié)合多變量公鑰密碼方案核心映射構(gòu)造的特點，通過將公鑰多項式的系數(shù)表示成矩陣的形式，從矩陣的秩的角度或矩陣奇異性的角度對多變量密碼方案進行私鑰恢復(fù)攻擊?，F(xiàn)有秩攻擊有三種：

（1）油醋分離攻擊：這一種攻擊方法主要用來分析油醋（OV）體制和不平衡油醋（UOV）體制以及油醋方案的變體方案，如彩虹體制、多層油醋簽名等，其計算復(fù)雜度為：q2v-n-1（n-v）4，其中 v為醋變量的個數(shù)，而n則為變量數(shù)。

（2）低秩攻擊（小秩攻擊）：這一類攻擊最初提出是用來攻擊隱域方程體制（HFE）的。

（3）高秩攻擊[27]：此類攻擊最初提出是用來攻擊基于雙有理轉(zhuǎn)換的簽名體制（此簽名體制由Shamir提出）的。文獻[27]指出，高秩攻擊在攻擊多變量密碼體制時的計算復(fù)雜度約為qu（un2+n3/6），其中u代表在核心映射多項式中出現(xiàn)最少的變量所出現(xiàn)的次數(shù)，n表示核心映射中變量的數(shù)目。

4.4 差分攻擊

差分攻擊最初由Fouque[29]等人提出，用以分析加密體制，其原理是：通過將計算核心映射的雙線性差分和線性化方程攻擊的方法相結(jié)合來恢復(fù)明文。

中心映射F（函數(shù)）所對應(yīng)的差分（算子）定義為：

此形式為域上的一個雙線性函數(shù)。

2008年，F(xiàn)ouque[36]等人成功地利用差分攻擊的方法攻破了l-IC方案。Billet等人于2009年將針對多變量公鑰密碼體制的差分攻擊方法作了改進，并利用改進后的差分攻擊方法攻擊了Square-Vinegar簽名方案和 Square加密方案[37]，分別得到了合法的偽造密文和正確的明文。2011年，Smith-Tone提出線性映射空間的大小可以作為決定差分安全的一個度量，空間越大越不安全。2013年，Perlner和Smith-Tone指出可以通過對差分不變量進行分類來抵抗差分攻擊。通過指出域映射中所有可能的線性差分不變量，就可以指出線性系統(tǒng)中可能會被攻擊者利用到的差分，從而確保系統(tǒng)可以抵抗對應(yīng)的攻擊模型。2014年，Daniels同樣和 Smith-Tone，對HFE和HFE-的核心映射進行研究，推導(dǎo)出差分對稱性與結(jié)構(gòu)不變量，并提供了一組參數(shù)的集合使得HFE體制對差分攻擊的安全性得到提高。2016年，Cartor和Smith-Tone等人對HFEv Signature Primitive的差分安全性進行了分析，并提出了新的可以抵抗差分攻擊的方案。

差分攻擊的優(yōu)點就在于其可以降低其所要攻擊函數(shù)的次數(shù)，這樣就大大減少了攻擊的計算復(fù)雜度，在尋找私鑰當(dāng)中特殊的線性關(guān)系方面有著巨大的優(yōu)勢。隨著對差分攻擊研究的深入，其在多變量公鑰密碼體制分析方面正在發(fā)揮越來越重要的作用，在密碼方案的構(gòu)造及改進的過程中要將此攻擊方法作為一種重要的攻擊類型來對待。

5 結(jié)論

多變量公鑰密碼系統(tǒng)的研究仍然存在許多不足，有很多相關(guān)的工作要完善，具體來說有以下三個方面：

（1）多變量公鑰密碼方案設(shè)計的基礎(chǔ)是數(shù)學(xué)理論，圖論、矩陣論等代數(shù)或幾何概念為方案的陷門構(gòu)造提供了新思路，推動了各種新方案的提出。另外，通過對攻擊方法的深入研究，分析舊方案，也能夠設(shè)計出新的多變量公鑰密碼方案。因此，數(shù)學(xué)理論、結(jié)構(gòu)的研究以及舊方案的分析改進將來一定能在構(gòu)造新多變量公鑰密碼系統(tǒng)上發(fā)揮作用。

（2）在多變量公鑰密碼系統(tǒng)的實際應(yīng)用上，存在公鑰長度過大的不足。如何針對資源和計算能力受限的小型設(shè)備，設(shè)計密鑰量較小的多變量公鑰密碼方案也是另一個吸引人的方向。

（3）對于多變量公鑰密碼系統(tǒng)的密碼分析和形式化證明的研究。方案設(shè)計伴隨著方案攻擊，新型攻擊方法的研究仍然是研究重點。另外，對多變量公鑰密碼安全性的形式化證明也應(yīng)該是安全性研究中的一個重要方面。