新擴展多變量公鑰密碼方案

喬帥庭，李益發，韓文報

（1.信息工程大學 四院，河南 鄭州 450002；2. 數學工程與先進計算國家重點實驗室，江蘇 無錫 214125）

1 引言

二十一世紀是信息的時代，繼電子信息科學技術之后，量子和生物等新型信息科學正在建立和發展。量子計算機的產生將會對目前廣泛使用的基于離散對數（包括橢圓曲線上的離散對數）和大數分解的公鑰密碼體制構成潛在的威脅[1～3]。為此，基于抗量子的公鑰密碼體制成為密碼學中一個研究的熱點和重點[4]。多變量公鑰密碼系統作為一種能有效抵抗未來的基于量子計算機攻擊方法的密碼體制，在近二十幾年受到越來越多的關注。

多變量公鑰密碼體制的安全性是基于有限域上多元非線性方程組的難解性[5]和多項式同構問題[6]。1988年，日本學者Matsumoto和Imai提出了第一個多變量公鑰密碼方案，即著名的Matsumoto-Imai(MI)方案[7]。該方案將“小域—大域”思想引入了多變量公鑰密碼方案，有較高的計算效率，在當時被認為是安全的。然而，1995年，Patarin等提出了針對MI方案的線性攻擊[8]，攻破了原始的MI體制。為了抵抗線性攻擊，Patarin等在2001年提出了FLASH方案[9]，Ding等人于2004年提出了PMI方案[10]，但都受到差分攻擊的影響[11,12]。到目前為止，多變量公鑰密碼體制主要有5類方案[5]：MI方案、hidden field equation (HFE)方案、unbalanced oil andvinegar (UOV)方案、stepwise triangular systems (STS)方案和medium field equation (MFE)方案，但大部分不能同時用于加密和簽名。近幾年來，多變量公鑰密碼體制的研究一直是熱點，相繼出現了CyclicRainbow方案[13]、Double-Layer square方案[14]、Enhenced STS方案[15]等，它們在安全性上得到了不同程度的提高[16,17]。2011年，Wang等通過引入Hash認證技術、并結合傳統Multivariate Quadratic（MQ）公鑰密碼算法，提出了一種擴展MQ公鑰密碼體制[18]，同時具備加密和簽名功能。但該方案的加密和簽名算法的構造較為復雜，引入了較大的私鑰空間。本文利用函數合成思想，構造了一種獨特的基于溫順變換思想[19]的非線性可逆變換，并將此變換與MI方案結合起來，提出了一種新的擴展多變量公鑰密碼方案，且給出了新的擴展方案的加密和簽名方案。分析結果顯示：該方案繼承了MI方案計算高效的特點，具有較小的私鑰量；克服了MI方案不能抵抗線性攻擊、差分攻擊的缺陷，還能抵抗代數攻擊。

2 多變量公鑰密碼體制及MI方案簡介

本文方案是在多變量公鑰密碼體制基礎上，與MI方案結合而成的，下面從多變量公鑰密碼體制的一般結構、加解密及簽名和MI方案三方面對相關研究工作展開論述。

2.1 多變量公鑰密碼的一般結構

多變量公鑰密碼的門限函數形式為有限域上一類多元二次方程組

每個pi為一個關于x=(x1,…,xn)的非線性二次方程

所有的系數和變量都在域K=Fq中，q為域K的階。多變量公鑰體制的構造主要基于multivariate quadratic (MQ)問題及isomorphism of polynomials(IP)問題的難解性。

定義1 給定有限域Fq上的n個變元m個方程組成的非線性方程組

其中，pi的系數和變量均取自有限域K=Fq，通常q＞2，每個多項式的形式為

求解該方程組的問題稱為MQ問題。已經證明MQ問題為NP難問題，即使是在最小的域F2上。

定義2 設(P)和(Q)為有限域Fq上隨機的n元m個方程的多變量方程組，且(P)和(Q)同構，則有P=T?Q?S ，T和S分別為2個可逆的仿射變換。稱尋找從(Q)到(P)同構的(T, S)的問題為IP問題，即多項式同構問題。

一般地，設(Q)∈(Fq[a1,…,an])m為Fq上m個多項式集合，集合中每個多項式都是n元二次多項式，其形式如下

2.2 加解密及簽名

多變量公鑰密碼的加解密方法如下所示

這里，S和T分別為Fqn和Fqm上的可逆仿射變換，中心映射為Q:Fqn→Fqm，公鑰為P=T?Q?S，S和T共同“隱藏”中心映射Q的結構，是私鑰的重要組成部分。

1) 加密

給定明文(u1,…,un)，利用公鑰P=T?Q?S對其進行運算，得到密文(v1,…,vn)=P(u1,…,un)。

2) 解密

給定密文(v1,…,vn)，利用私鑰{T-1, Q-1, S-1}對密文依次進行T-1、Q-1和S-1運算，得到明文

3) 簽名

給定消息M，得到消息摘要(v1,…,vm)=Hash(M)，利用私鑰{T-1, Q-1, S-1}對其依次進行T-1、Q-1和S-1運算，得到簽名

4) 驗證

給定簽名(u1,…,un)，利用公鑰P=T?Q?S對其進行運算，得到消息摘要(v1′,…,vm′)，然后判斷(v1′,…,vm′)=Hash(M)是否成立，若成立，則簽名有效，否則，簽名無效。

2.3 MI方案

1988年，Matsumoto和Imai提出了第一個多變量公鑰方案——MI方案[7]。

令k為一有限域，k=Fq，特征為2，可設q=2w。K為k的n次擴域，K=Fqn。 定義K同構φ：K→kn，正整數 θ滿足gcd(1+qθ, qn-1)=1，此時定義F：K→K，F(X)=X1+qθ，則F為可逆的，F-1(X)=Xt，這里t滿足t(1+qθ)≡1 mod (qn-1)。

最后，隨機選擇2個kn上的可逆的仿射變換L1和L2，定義

3 新的擴展多變量公鑰密碼方案

多變量公鑰密碼體制根據不同的中心映射的構造方法主要可分為：MI體制、隱藏域方程體制、不平衡油醋體制、三角形體制以及中間域方程體制。這些算法大多不能同時用于加密和簽名，而且，大部分受到不同程度地攻擊[19]，例如線性攻擊、差分攻擊、代數攻擊等。如何構造一種安全高效且同時具備加密和簽名功能的多變量方案仍是一個值得研究的難題和熱點。

本文利用溫順變換(tame transformation)思想，構造出非線性可逆變換L3:Fqn→Fqn，即L3(x1,…,xn)=(t1,…,tn)。然后，將MI方案與基于溫順變換思想的非線性可逆變換結合起來，提出了一種新的擴展多變量公鑰密碼方案

3.1 L3的構造

L3的構造用到一類特殊的映射G:GF(q)n→其形式為

其中，gi為任意二次多項式。此變換結構特殊，容易求逆，也稱溫順變換[19]。

取正整數n，d，且滿足n＞2d，構造基于溫順變換的可逆變換L3(x1,…,xn)=(t1,…,tn)，其形式如下

3.2 新擴展方案

利用函數合成思想將MI方案與基于溫順變換思想構造的L3結合，得到新擴展多變量公鑰密碼方案的公鑰多項式為

其中，L1、L2、φ、φ-1的定義同MI方案中的定義一致，L3的定義如3.1節所述。正整數θ滿足條件gcd(1+qθ,qn-1)=1，此時定義F：K→K，F(X)=X1+qθ，則F為可逆的，且當t(1+qθ)≡ 1 mod (qn-1)時F-1(X)=Xt。

3.3 基于新擴展體制的加密方案

加密過程：加密者用公鑰F?對明文(x1,…,xn)進行加密，得到密文：

解密過程：解密者收到密文(y1,…,yn)后，做如下計算。

1) 用私鑰L1-1計算可得

3) 用私鑰L2-1計算得到

4) 用私鑰L3-1計算便可得到相應的明文

由解密的過程，可得明文(x1,…,xn)與密文(y1,…,yn)滿足如下關系式：

3.4 基于新擴展體制的簽名方案

簽名：設M為待簽名文件，用公開的散列函數Hash計算(y1,…,yn)=Hash(M)。簽名體制的私鑰和上述加密方案的私鑰一致，計算簽名(x1,…,xn)的步驟和3.3中解密步驟相同，不再詳述。

驗證：驗證者收到消息M和簽名(x1,…,xn)后，驗證如下。

1) 計算Hash(M)=(y1,…,yn)；

2) 然后驗證下列方程組是否成立。若成立，則簽名有效；否則，簽名無效。

4 新方案的性能分析和安全性分析

下面將對新方案進行性能分析和安全性分析。性能分析主要包括公私鑰大小和擴展體制的運算效率。安全性分析則從針對多變量公鑰密碼體制的結構攻擊和直接攻擊著手。

4.1 性能分析

4.1.1 公私鑰大小

1) 基于“溫順變換”思想的擴展方案的公鑰的一般形式為

由3.1節中it的構造可得

對于私鑰而言，如3.1節定義，L3的私鑰為c1,…,cd，由于d=6，相對于L1、L2的私鑰量，L3的私鑰量極小，而MI方案的私鑰量大小約為2wn2bit，Wang等人的方案私鑰量約為3wn2bit，新擴展方案的私鑰量大小約為w(2n2+6) bit，在推薦參數w=8，n=32下，MI方案私鑰量大約為2 KB，Wang等人的私鑰量約為3 KB，新擴展方案的私鑰量約為2 KB，與MI方案相比，對應的擴展體制私鑰量基本不發生變化；與Wang等人的方案相比，本文新的擴展方案縮小了約1/3私鑰量。

4.1.2 運算效率

由L3，L3-1構造可知，它們的運算僅僅多出了d個乘法和加法，在推薦參數w=8，n=32，d=6下，相對于MI體制的加解密和簽名效率，運算L3和L3-1可忽略不計，不影響全局運算效率，因此，新的擴展體制保持了MI方案的高效性。

可見，本文提出的新的擴展方案具備較小的公鑰量和私鑰量，保持了MI方案的優勢，具有較高的加解密和簽名效率。

4.2 安全性分析

多變量體制的安全性分析分為結構攻擊和直接攻擊2類。結構攻擊是針對多變量體制特殊的結構特征，主要包括線性攻擊和差分攻擊。直接攻擊是從多變量體制的公鑰多項式入手，常用的攻擊方法為Gr˙obner基算法和XL算法。通常認為只要攻擊方案的復雜度超過O(280)，則稱該方案可抗此種攻擊。下面進行本文方案的安全性分析。

4.2.1 抗線性攻擊

1998年Patarin提出的一種線性攻擊[8]，在w=8，n=32的情況下，經過O(232)次運算就可以求解。

根據MI方案特殊的中心映射F:X?Xqθ+1，存在如下特殊的代數關系式

兩邊分別乘以XY，得到關系式

其中，aij、bi、ci、d為方程式的(n+1)2個系數。

在給出O((n+1)2)個明密文對(x1,…,xn,y1,…,yn)時，可以求解上述方程組的系數。一旦所有的系數均被求解得到，那么在給定密文y=(y1,…,yn)的情況下，就可得到關于明文x=(x1,…,xn)的n個線性方程組。

定理1 新擴展方案利用函數合成思想，將非線性可逆變換L3與MI方案結合起來，從而可抗線性攻擊。

證明 根據中心映射的構造可得

在給出O((n+1)2)個(t1,…,tn,y1,…,yn)時，可以求解上述方程組的系數。而密文(y1,…,yn)已知，中間量(t1,…,tn)未知，所以代入密文后仍然無法解出方程組的系數；但當d=1,…,5時，含有二次非線性項較少，此時若對t1,…,t5進行窮舉，可以在O(280)時間以內攻破。以d=1為例，此時t1=x1-c1xd+1xn,ti=xi(i=2,…,n)得到如下的關系式

若對t1進行窮舉，可得

而在參數w=8，n=32，d=1時，假設出現最好的情況：攻擊者知道ti=xi(i=2,…,n)。在已知足夠多的明密文對(t1,x2,…,xn,y1,…,yn)時，可求解出系數，在給定密文y=(y1,…,yn)時，可依次給出t1,x2,…,xn，此過程的復雜度為O(232)。再對c1窮舉，可得到明文x1,…,xn，所以在d=1時，線性攻擊成功的復雜度約為O(240)，當d=2時，線性攻擊成功的復雜度約為O(248)，依次類推，d=5時，線性攻擊成功的復雜度約為O(272)。所以當d≥6時，線性攻擊成功的復雜度為O(280)，即安全級別為O(280)。

綜上所述，新的擴展方案可抵抗線性攻擊。

4.2.2 抗差分攻擊

MI體制是公鑰密碼發展的一個里程碑，它為該領域帶來了一種全新的設計思想。在此基礎上，相繼提出了PMI方案、SFLASH方案等。但是PMI方案、SFLASH方案均受到差分攻擊。SFLASH方案其實就是MI-Minus方案即C*-體制，可通過差分分析恢復出r個被去掉的多項式的等價多項式，再加上已知的n-r個公鑰多項式，從而構成了一個完整的MI方案的公鑰多項式，這樣就可重新利用線性攻擊去偽造簽名。

首先，給出差分的定義：對于函數()Fx，定義其在a點處的差分為

其中，Nξ和Mξ均表示關于ξ的線性映射。

定理2 新擴展方案在MI方案的基礎上，引入了非線性可逆變換L3，打破了MI體制的乘法反對稱性，能很好地抵抗差分攻擊。

由于L3變換是一個非線性變換，對應地，式(17)中也是一個非線性變換，因此對于?x,ξ∈GF(qn)，顯然有

式(19)表明非線性變換L3的引入破壞了MI體制公鑰的乘法反對稱性。

所以新擴展方案能抵抗差分攻擊。

4.2.3 抗代數攻擊

代數攻擊常用的工具包括Gr˙obner基算法和XL算法[17]。目前，計算Gr˙obner基最有效的算法為F4和F5算法。

證明 根據方程的個數m和變量的個數n之間的大小關系，分3種情況討論。

1) 當m=n時，多元二次方程組為置換方程組，當k=GF(q)≠GF (2)時，求解方程組的復雜度為O(23m)[19]。

2) 當m＞n時，多元二次方程組為超定方程組，此時用XL算法。當m≥εn2，0＜ε≤1/2時，XL算法都可以在nO(1/ε)的多項式時間內運行成功[20]。

3) 當m＜n時，多元二次方程組為不定方程組[21]，求解的復雜度約等于窮盡搜索的復雜度O(qm)。

在新方案中，公鑰多項式為P(x1,…,xn)=(p1(x1,…,xn),…,pn(x1,…,xn))，對應的方程組為

此時，方程組的個數和變量的個數相等，都為n，但由4.1.1節知pi(x1,…,xn)為多元四次多項式，求解方程組(20)的復雜度遠大于求解多元二次方程組。在給定的參數n=32下，由情況1)可得，求解多元二次方程組的復雜度為O(296)，可見求解新體制公鑰多項式的復雜度在O(296)之上。

所以新擴展方案在特定參數下可以抵抗代數攻擊。

目前，針對多變量體制的攻擊主要包括線性攻擊、差分攻擊和代數攻擊。由定理1～定理3可知，新的擴展方案能同時抵抗線性化攻擊、差分攻擊和代數攻擊，所以新擴展方案是安全的。

5 結束語

針對MI方案不能抵抗線性攻擊和差分攻擊，本文基于溫順變換思想構造了一種的獨特的非線性可逆變換，并將此非線性變換與MI方案結合，提出一種新的擴展多變量公鑰密碼方案。對應地，構造了新的擴展方案的加密方案和簽名方案。新的擴展方案保持了MI方案計算高效的優點，具有較小的公私鑰空間；同時能抵抗線性化攻擊、差分攻擊和代數攻擊，在安全性上得到了提高。是否存在一個新的攻擊方法有待進一步研究。

[1] SHOR P. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer[J]. SIAM Rev, 1999, 41(2):303–332.

[2] 付向群, 鮑皖蘇, 周淳. Shor 整數分解量子算法的加速實現[J]. 科學通報, 2010, 4: 322-327.FU X Q, BAO W S, ZHOU C. Speeding up implementation for Shor’s factorization quantum[J]. Chinese Sci Bull, 2010, 4: 322-327.

[3] MYASNIKOV A D, USHAKOV A. Quantum algorithm for the discrete logarithm problem for matrices over finite group rings[EB/OL].https://eprint.iacr.org/2012/574.pdf, 2012.

[4] BERNSTEIN D J, BUCHMANN J, DAHMEN E. Post-Quantum Cryptography[M]. Berlin: Springer-Verlag, 2009.

[5] DING J T, YANG B Y. Multivariate Public Key Cryptography[M].Berlin: Springer-Verlag, 2009.

[6] TANG S, XU L. Proxy signature scheme based on isomorphisms of polynomials[A]. NSS 2012[C]. Fujian, China, 2012. 113-125.

[7] MATSUMOTO T, IMAI H. Public quadratic polynomial-tuples for efficient signature-verification and message-encryption[A]. Advances in Cryptology—EUROCRYPT’88[C]. Switzerland, 1988. 419-453.

[8] PATARIN J. Cryptanalysis of the Matsumoto and Imai public key scheme of Eurocrypt’88[A]. Advances in Cryptology—CRYPT0’95[C].Santa Barbara, California, USA, 1995. 248-261.

[9] PATARIN J, COURTOIS N, GOUBIN L. Flash, a fast multivariate signature algorithm[A]. Topics in Cryptology—CT-RSA 2001[C]. San Francisco, CA, USA, 2001. 298-307.

[10] DING J. A new variant of the Matsumoto-Imai cryptosystem through perturbation[A]. Public Key Cryptography–PKC 2004[C]. Singapore,2004. 305-318.

[11] DUBOIS V, FOUQUE P A, STERN J. Cryptanalysis of SFLASH with slightly modified parameters[A]. Advances in Cryptology- EUROCRYPT 2007[C]. Barcelona, Spain, 2007. 264-275.

[12] DING J, GOWER J E. Inoculating multivariate schemes against differential attacks[A]. Public Key Cryptography-PKC 2006[C]. New York,USA, 2006. 290-301.

[13] PETZOLDT A, BULYGIN S, BUCHMANN J. CyclicRainbow–a multivariate signature scheme with a partially cyclic public key[A]. Progress in Cryptology-INDOCRYPT 2010[C]. Hyderabad, India, 2010. 33-48.

[14] CLOUGH C L, DING J. Secure variants of the square encryption scheme[A]. Post-Quantum Cryptography[C]. Darmstadt, Germany,2010. 153-164.

[15] TSUJII S, GOTAISHI M, TADAKI K,etal. Proposal of a signature scheme based on STS trapdoor[A]. Post-quantum cryptography[C].Darmstadt, Germany, 2010. 201-217.

[16] THOMAE E, WOLF C. Roots of square: cryptanalysis of double-layer square and square+[A]. Post-Quantum Cryptography[C]. Taipei, China,2011. 83-97.

[17] THOMAE E, WOLF C. Cryptanalysis of enhanced TTS, STS and all its variants, or: why cross-terms are important[A]. Progress in Cryptology-AFRICACRYPT 2012[C]. Ifrance, Morocco, 2012. 188-202.

[18] WANG H Z, ZHANG H G. Extended multivariate public key cryptosystems with secure encryption function[J]. Science China Information Sciences, 2011, 54(6): 1161- 1171.

[19] 王后珍, 張煥國, 管海明等. 多變量代數理論及其在密碼學中的應用[J]. 北京工業大學學報, 2010 , 5: 627-634.WANG H Z, ZHANG H G, GUAN H M, etal. Multivariate algebra theory and its application in cryptography[J]. Journal of Beijing University of Technology, 2010, 5: 627-634.

[20] ALBRECHT M R, CID C, FAUGèRE J C, etal. On the relation between the MXL family of algorithms and Gr?bner basis algorithms[J].Journal of Symbolic Computation, 2012, 47(8): 926-941.

[21] THOMAE E, WOLF C. Solving underdetermined systems of multivariate quadratic equations revisited[A]. PKC 2012[C]. Darmstadt, Germany, 2012. 156-171.