單項式多變量公鑰密碼算法的等價密鑰問題

魏占禎，袁峰，許盛偉，江繼軍

(1.北京電子科技學院通信工程系，北京100070;2.北京電子科技學院信息安全研究所，北京100070)

1994 年，Peter Shor［1］提出了多項式時間內的量子大整數分解算法。這意味著一旦造出實用的量子計算機后，基于大整數分解和離散對數問題的傳統公鑰密碼算法將會是不安全的。基于有限域上多元多項式方程組的多變量公鑰密碼算法被認為是能抵抗量子計算機攻擊的幾種公鑰密碼算法之一，其安全性基礎是解有限域上的多元多項式方程組，而這一問題是NP-困難問題［1］。較之于傳統公鑰密碼算法［2］，多變量公鑰密碼算法具有速度快、易于實現等優點［3-5］。多變量公鑰密碼算法中存在著多個私鑰對應于同一個公鑰的等價密鑰問題。Wolf等在文獻［6］中分別研究了C*，C*-和 HFE 等［1，7］著名算法的等價密鑰問題，計算出了這些算法的等價密鑰數量。并且，Wolf等指出，任一公鑰都有指數級個私鑰與之對應，從而使私鑰空間大量減少。通過應用保形變換，將私鑰的線性部分化為具有稀疏特性的矩陣，選該形式作為等價類的代表元，可以有效地減少運算量，從而有助于存儲的高效實現。同時，等價密鑰的存在導致實際安全參數空間的規模也大為減少，要想達到預想的安全強度就必須提高算法參數的大小［6］。多變量公鑰密碼算法C*，C*-和Square等［1，8］是中心映射為一般單項式的多變量公鑰密碼算法［9］的特例，即中心映射為一般單項式的多變量公鑰密碼算法是以上這些著名算法更為一般的推廣形式，若能計算出其等價密鑰的數量，就可直接推出這些“特例”算法等價密鑰的數量。本文對中心映射為一般單項式的多變量公鑰密碼算法的等價密鑰問題進行了研究，利用保形變換和有限域方面的知識計算出了其等價密鑰的具體數量。

1 等價密鑰和保形變換

本節介紹多變量公鑰密碼中等價密鑰和保形變換的定義，以及有限域上的一些結論。

設k是q階元素的有限域，即k=GF(q)。若g(x)是域k上的n次不可約多項式，則K=k［x］/(g(x))是域k的n次擴域，即K=GF(qn)。設φ:K→kn是域K到域k上n維線性空間的同構映射，即 φ(a0+a1α+…+an-1αn-1)=(a0，a1，…，an-1)。

多變量公鑰密碼算法的關鍵思想［1］是用2個可逆線性仿射(或可逆線性映射)U:kn→kn和T:kn→kn來隱藏中心映射F'。若F'是從kn到kn的映射，令F=F'，則合成映射P:kn→kn是:

若F'是從域K到域K的映射，令F=φ?F'?φ-1，即F是從kn到kn的映射，則合成映射P:kn→kn是:

定義 1［6］若 2 組密鑰 (T，F，U)和能夠使得

則稱這2組密鑰是等價的。

事實上，多變量公鑰密碼的等價密鑰問題就是指對應公鑰相同，對私鑰空間劃分等價類。

定義 2［6］映射ρ:kn→kn和 ω:kn→kn是2個可逆線性仿射，可知:

若ρ和ω能夠使得映射F的形狀保持不變，即映射F與ω?F?ρ在表達形式上是相同的，則稱ρ和ω為保形變換。

事實上，所定義的保形變換ρ和ω必須要使映射F的形狀保持不變，在這種情況下，所得到的映射ρ-1?U和T?ω-1的數量，就是等價密鑰的數量。

通過應用保形變換ρ和ω，將可逆線性仿射U和T所對應的矩陣化為具有“稀疏”特性的標準形式。在計算資源和存儲空間都受限的場合，如智能卡、傳感器平臺、無線射頻識別上，選具有“稀疏”特性的標準形作為等價類的代表元，可以有效地減少計算量，提高存儲效率。

引理 1［10］

其中，GLn(Fq)為域Fq上的可逆矩陣群。

引理1給出了域Fq上n×n階可逆矩陣的數量。

引理2［1］若多項式映射L:K→K是:

其中，Ai，B∈K。令，則是一個多項式映射:

引理2揭示了域K上的線性化多項式:

與kn上線性仿射y=Cx+D之間存在著一一對應關系，其中C∈kn×n，D∈kn，x=(x0，x1，…，xn-1)∈kn，y=(y0，y1，…，yn-1)∈kn。

下面的引理3是引理2的推廣，引理3揭示了kn上的二次多項式與擴域K上的多項式映射之間的一一對應關系。

引理3［1］若多項式映射F:K→K是:

2 單項式多變量公鑰密碼算法的等價密鑰數量

本節討論中心映射為一般單項式F'(X)=(t＜q)的多變量公鑰密碼算法的等價密鑰問題。下面的定理1討論了l1，l2，…，lt∈{0，1，2，…，n-1}且l1，l2，…，lt全不相同時的情形;定理2 討論了l1，l2，…，lt∈{0，1，2，…，n-1}且l1=l2=…=lt-1=lt時的情形。這2個結果非常一般，由這2個結果可直接推出一些基于單項式的多變量公鑰算法等價密鑰的數量，如C*算法和Square算法。

定理1 對于域K=GF(qn)上的中心映射F'(X)=Xql1+ql2+…+qlt，t＜q，l1，l2，…，lt∈ {0，1，2，…，n-1}且l1，l2，…，lt全不相同，使得F=ω?F?ρ成立的可逆線性仿射ρ和ω的數量為n(qn-1)，其中ρ和 ω的線性化多項式形式為 ρ(X)=AXqc和ω(X)=A-qn-c(qi1+qi2+…+qit)Xqn-c，c=0，1，…，n-1，0 ≠A∈K。

證明:由F=ω?F?ρ可得ω-1?F=F?ρ。根據引理2，可設

由于t＜q，則可推出ql1+ql2+…+qlt≤qn-1+qn-1+ … +qn-1=tqn-1＜qn;由于l1，l2，…，lt∈{0，1，2，…，n-1}且l1，l2，…，lt全不相同，則l1+i，l2+i，…，lt+i也全不相同。因此，對比等式F?ρ(X)=ω-1?F(X)兩邊各項系數可以發現，等式左邊形如Xqa+qa+…+qa的單項式的系數為0，這里qa+qa+…+qa共有t項，a=0，1，…，n-1，即有如下n個方程:

這里i1，i2，…，it∈{0，1，2，…，n-1}，且i1，i2，…，it全不相同。要想使以上n個方程成立，就要求在A10，A11，…，A1n-1中至少有 2 個值為 0，不妨設A1n-2=0，A1n-1=0。進一步可以發現，存在形如Xqa+qa+…+qa+qb的單項式的系數為0，這里qa+qa+…+qa+qb共有t項，a∈{0，1，…，n-1}，b=0，1，…，n-1，即有如下形式的方程:

這里j1，j2，…，jt∈ {0，1，2，…，n-1}。要想使以上方程成立，就要求在A10，A11，…，A1n-3中至少有一個值為0，不妨設A1n-3=0。進一步還可以發現，存在形如Xqa+qa+…+qa+qb+qb的單項式的系數為0，其中qa+qa+…+qa+qb+qb總共有t項，a∈{0，1，…，n-1}，b=0，1，…，n-1，即有如下形式的方程:

這里k1，k2，…，kt∈ {0，1，2，…，n-1}。要想使以上方程成立，就要求在A10，A11，…，A1n-4中至少有一個值為0，不妨設A1n-4=0。以此類推，能夠發現，有且僅有一個A1m≠ 0，0≤m≤n-1，其余A1i=0，i≠m。因而就有

形如Xqi1+qi2+…+qit-1的單項式的系數為0，其中qi1+qi2+…+qit-1共有t-1 項，i1，i2，…，it-1∈ {0，1，2，…，n-1}，且i1，i2，…，it-1全不相同，即有如下形式的方程:

要想使以上方程成立，就要求D=0。由于G=Dqi1+qi2+…+qit，因此G=0。再對比等式F?ρ(X)=ω-1?F(X)兩邊各項系數能夠得到，C2m≠0，0≤m≤n-1，C2i=0，i≠m。

根據以上分析可設，

其中，0≤c，d≤n-1，A，C∈K。由于映射ω與ω-1互逆，因此ω(X)=C-qn-dXqn-d。再根據等式ω?F?ρ(X)=F(X)可得

即C-qn-dAqn-d(qi1+qi2+…+qit)=1，c=d，則可逆線性仿射 ρ和ω的線性化多項式形式就是 ρ(X)=AXqc和ω(X)=A-qn-c(qi1+qi2+…+qit)Xqn-c，c=0，1，…，n-1，A∈K，因而具有這樣形式的可逆線性仿射ρ和ω的數量即為n(qn-1)。

定理2 對于域K=GF(qn)上的中心映射F'(X)=Xql1+ql2+…+qlt，t＜q，l1，l2，…，lt∈ {0，1，2，…，n-1}且l1=l2=…=lt-1=lt，使得F=ω?F?ρ成立的可逆線性仿射ρ和ω的數量為n(qn-1)，其中ρ和 ω的線性化多項式形式為 ρ(X)=AXqc和ω(X)=A-qn-c(qi1+qi2+…+qit)Xqn-c，c=0，1，…，n-1，0 ≠A∈K。

證明:由F=ω?F?ρ可得ω-1?F=F?ρ。根據引理2，可設

其中，A1i，B2i，C2i，D，S，G∈K=GF(qn)。

由等式ω-1?F(X)=F?ρ(X)可知，對比常數項可得

對比n個單項式Xq0，Xq1，…，Xqn-1的系數，可得以下n個等式:

對比以下n(n-1)個單項式:

設域k=GF(q)的特征為素數p，q=pm，m≥1，則有以下2種情形:

情形1 若 (p，t)=1，由式(2)可知，D=0或A1i=0，0≤i≤n-1。根據映射ρ是可逆線性仿射，A1i(0≤i≤n-1)都為0是不可能的，因此，由式(2)可推出D=0。再由式(1)可得，G=0。

由式(3)可推出，在A10，A11，…，A1n-1中至少有n-1個值為0，再根據映射ρ是可逆線性仿射可得，有且僅有一個A1c=A≠0，0≤c≤n-1，其余A1i=0，i≠c。以下證明過程與定理1的證明過程相同。

情形2 若p|t，可設t=pew，(p，w)=1，e，w≥1 ，則tql1=wpml1+e，就有

由于(p，w)=1，以下證明過程與情形1的證明過程相似。

3 C*算法和Square算法的等價密鑰數量

在C*算法［1］中，域k是q階元素且特征為2的有限域，域K是域k的n次擴域。中心映射F'是:F'(X)=Xqθ+1，X∈K，其中 θ要使qθ+1與qn-1互素，即gcd(qθ+1，qn-1)=1且0＜θ＜n。

由于C*算法的中心映射F'為F'(X)=Xqθ+q0，0＜θ＜n，q=2m(一般情況下m＞1，著名的SFLASH算法［1，9］的推薦參數為q=27)，因此，2=t＜q=2m，l1=0，l2=θ，l1，l2∈ {0，1，2，…，n-1}且l1≠l2，根據定理1，可得以下推論1。

推論1 若C*算法的私鑰是(T，F，U)，則等價密鑰的數量是n(qn-1)。

在Square算法［8］中，域k是q階元素的有限域，其中q≡3 mod 4，域K是域k的n+l次擴域。中心映射F'是:F'(X)=X2，X∈K。映射T:kn+l→kn+l是可逆線性仿射，映射U-:kn→kn+l是將可逆線性仿射U:kn+l→kn+l(線性部分)的最后l列刪掉。

由于Square算法的中心映射F'為F'(X)=Xq0+q0，q≡3 mod 4(q＞3，Square算法［8］的推薦參數為q=31)，因此，2=t＜q，l1=l2=0且l1，l2∈{0，1，2，…，n-1}，根據定理 2，可直接得到以下推論 2。

推論2 對于特征不為2的域K上的中心映射F'(X)=X2，使得F=ω?F?ρ成立的可逆線性仿射ρ和ω的數量為n(qn-1)，其中ρ和ω的線性化多項式形式為 ρ(X)=BXqt和 ω(X)=B-2qn-tXqn-t，t=0，…，n-1，0≠B∈K。

推論3 若Square算法的私鑰為(T，F，U)，l是可逆線性仿射U刪掉的列數，則等價密鑰的數量是

證明:由于可逆線性仿射U和T的數量為(n+l)(qn+l-1)，U-是將線性仿射U的線性部分的最后l列刪掉，因此，在U-端就產生了倍的等價密鑰。注意到T和U-兩端的變換是獨立的，所以直接相乘就能得到結論。

4 結束語

等價密鑰問題是多變量公鑰密碼算法中一類重要的問題，中心映射為一般單項式的多變量公鑰密碼算法是C*，C*-和Square等著名算法更為一般的推廣形式。本文利用保形變換和一些數學技巧計算出了中心映射為一般單項式的多變量公鑰密碼算法等價密鑰的數量。所得到的結果可直接推出C*，C*-和Square等著名算法等價密鑰的數量。目前對于中心映射為高次多元多項式(如高次二項式)的等價密鑰問題仍然沒有結果，將來可嘗試計算中心映射為一般多元多項式的多變量公鑰密碼算法等價密鑰的數量。

［1］DING Jintai，GOWER J E，SCHMIDT D S.Multivariate public key cryptosystems［M］.New York:Springer，2006:2-3，246-247.

［2］劉振華，胡予濮，牟寧波.基于身份認證密鑰協商的分析與改進［J］.哈爾濱工程大學學報，2009，30(10):1194-1198.LIU Zhenhua，HU Yupu，MU Ningbo.Analysis and improvement of identity-based authenticated key agreement［J］.Journal of Harbin Engineering University，2009，30(10):1194-1198.

［3］BETTALE L，FAUGèRE J C，PERRET L.Cryptanalysis of HFE，multi-HFE and variants for odd and even characteristic［J］.Designs，Codes and Cryptography，2013，69(1):1-52.

［4］GAO Shuhong，HEINDL R.Multivariate public key cryptosystems from diophantine equations［J］.Designs，Codes and Cryptography，2013，67(1):1-18.

［5］YUAN Feng，SUN Ying，JIANG Jijun，et al.A multivariate public key cryptographic scheme［J］.China Communications，2014，11(12):120-124.

［6］WOLF C，PRENEEL B.Equivalent keys in HFE，C*，and variations［C］//Progress in Cryptology-MYCRPT 2005.Berlin，2005:33-49.

［7］BOUILLAGUET C，FOUQUE P A，VéBER A.Graph-theoretic algorithms for the“isomorphism of polynomials”problem［C］//Advances in Cryptology-EUROCRYPT 2013.Berlin，2013:211-227.

［8］DING Jintai，CLOUGH C，ARAUJO R.Inverting square systems algebraically is exponential［J］.Finite Fields and Their Applications，2014，26:32-48.

［9］CAO Weiwei，HU Lei.Projective interpolation of polynomial vectors and improved key recovery attack on SFLASH［J］.Designs，Codes and Cryptography，2014，73(3):719-730.

［10］萬哲先.有限域上典型群的幾何學［M］.第2版.北京:科學出版社，2002:4-5.