一種混合多變量公鑰簽名方案

李曉莉,喬帥庭,劉 佳

(1.河南工業(yè)大學(xué)信息科學(xué)與工程學(xué)院,鄭州450001; 2.信息工程大學(xué)數(shù)字工程與先進(jìn)計(jì)算國(guó)家重點(diǎn)實(shí)驗(yàn)室,鄭州450001;3.防空兵指揮學(xué)院,鄭州450052)

一種混合多變量公鑰簽名方案

李曉莉1,喬帥庭2,劉 佳3

(1.河南工業(yè)大學(xué)信息科學(xué)與工程學(xué)院,鄭州450001; 2.信息工程大學(xué)數(shù)字工程與先進(jìn)計(jì)算國(guó)家重點(diǎn)實(shí)驗(yàn)室,鄭州450001;3.防空兵指揮學(xué)院,鄭州450052)

多變量公鑰密碼體制能抵抗量子計(jì)算機(jī)的攻擊,是后量子時(shí)代一種安全的密碼體制備選方案?？紤]到Square體制可有效抵抗線性化攻擊,不能抵抗差分攻擊,三角型密碼系統(tǒng)能抵抗差分攻擊,但受到線性化方程攻擊和最小秩攻擊的情況,結(jié)合Square體制和三角型密碼系統(tǒng),采用新的混合簽名結(jié)構(gòu)框架重構(gòu)中心映射,提出一種混合多變量公鑰簽名方案。分析結(jié)果表明,混合簽名方案克服了Square體制和三角型密碼系統(tǒng)的缺陷,能夠抵抗線性攻擊(包含一般線性化方程攻擊和高階線性化方程攻擊)、差分攻擊、最小秩攻擊和代數(shù)攻擊,具備較高的安全性。

多變量公鑰密碼;混合多變量簽名方案;線性攻擊;差分攻擊;最小秩攻擊;代數(shù)攻擊

1 概述

量子計(jì)算機(jī)的快速發(fā)展對(duì)信息安全體系造成極大的影響。Shor算法的提出使得目前廣泛使用的基于大數(shù)分解和離散對(duì)數(shù)的公鑰簽名算法受到嚴(yán)重威脅[1-2]。為此,具有抗量子計(jì)算性質(zhì)的公鑰密碼受到了廣泛關(guān)注[3]。多變量公鑰密碼體制就是在這種背景下發(fā)展而來。其安全性基于有限域上多元二次非線性方程組和多項(xiàng)式同構(gòu)問題的難解性[4-6]。

1999年,Moh提出了TTM(Tame Transformation Method)密碼系統(tǒng),該密碼系統(tǒng)的中心映射為“三角型”映射[7],具有很高的效率,但受到線性攻擊和最小秩攻擊[8-9]。2009年,Crystal Clough提出了一種新的高效的加密方案Square,該方案能有效地抵抗線性攻擊等[10],同年,Olivier Billet等通過差分攻擊手段尋找Square方案的不變子空間,從而恢復(fù)出Square方案的密鑰[11]。當(dāng)前的多變量公鑰密碼算法大部分受到不同程度的攻擊,如何構(gòu)造出一種安全的多變量公鑰加密和簽名體制是一個(gè)值得研究的熱點(diǎn)和難點(diǎn)。

本文利用分支思想,在Square體制和三角型密碼系統(tǒng)基礎(chǔ)上,重構(gòu)了中心映射,設(shè)計(jì)了混合簽名方案,從線性攻擊、差分攻擊、最小秩攻擊等對(duì)混合簽名方案進(jìn)行安全性分析。

2 背景知識(shí)

2.1 多變量公鑰密碼體制的一般結(jié)構(gòu)

多變量公鑰密碼的陷門構(gòu)造如下所示:

從而得到公鑰:

其中,S:X?X′=MiC+Ci和T:Y′?Y=MTY′+CT分別為和上隨機(jī)選取的可逆仿射變換,它們共同“隱藏”了中心映射Q的結(jié)構(gòu),是私鑰的重要組成部分。

公鑰方程組每個(gè)pk(x1,x2,…,xn)為一個(gè)關(guān)于x=(x1,x2,…,xn)的非線性二次方程:

所有的系數(shù)和變量都在域k=Fq中,q為域k的階。

解決此類問題相當(dāng)于解決了有限域上的多元二次方程組求解問題,即MQ(Multivariate Quadratic)問題[12-13]。

2.2 Square方案及其攻擊

2.2.1 Square方案

2009年,Crystal Clough提出了一種新的高效的加密方案 Square,該方案能有效地抵抗線性攻擊等[10]。

記k為一有限域,k=Fq,q≡3mod4。K為k的n+l次擴(kuò)域,K?k[y]/[g(y)]=Fqn+l,l滿足n+l為奇數(shù)。定義k同構(gòu)φ:K→kn+l,φ(a0+a1x+…+an+l-1xn+l-1)=(a0,a1,…,an+l-1),L1:kn→kn+l為一個(gè)單射仿射變換,中心映射F:K→K,F(X)=X2,L2:kn+l→kn+l為一個(gè)可逆仿射變換。Square加密體制如圖1所示。

圖1 Square加密體制

Square體制的公鑰為:

記Square體制的密文為(c1,c2,…,cn+l)=P(m1,m2,…,mn)∈kn+l,解密如下所示:

(2)解方程X2=Y,因q=3mod4,且n+l為奇數(shù),則|K|≡3mod4,于是可得

(3)計(jì)算(由于L1是仿射的,只有一個(gè)X是L1° φ-1的象)。

2.2.2 Square方案的攻擊

2009年,文獻(xiàn)[11]通過差分攻擊手段尋找Square方案的不變子空間,從而恢復(fù)出Square方案的密鑰[11]。

將Square方案的公鑰分解為:

記:

DP(X,Y)=L2(2·L1(X)·L1(Y)),考慮差分DPy:X→DP(X,y)。由于L1:kn→kn+l滿秩,則它的象的維數(shù)為n。任意選取線性獨(dú)立的向量y1,y2,…,yn,使得DPy1,DPy2,…,DPyn能夠表示{DPz}z∈E的整個(gè)空間。記Δ={P1}∪{DPyi}i=1,2,…,n,每個(gè)元素都可表示為L(zhǎng)2°να°L1,να表示E中的元素乘以α,因而Δ={L2°νλi°L1}i=1,2,…,n,n個(gè)值λ1,λ2,…,λn未知,但線性獨(dú)立。

通常的方法是找到公鑰方程D1=L2°νλ1°L1∈Δ和D1=L2°νλ2°L1∈Δ之間的線性映射L,使得:

即若存在λ使得:

2.3 三角型方案及其攻擊

2.3.1 三角型方案

文獻(xiàn)[7]提出TTM(Tame Transformation Method)密碼系統(tǒng)[7],該密碼系統(tǒng)的中心映射為三角型映射G:

其中,gi∈Fq[x1,x2,…,xn]是任意的二次多項(xiàng)式。

易知G是一個(gè)一一映射,而且容易求逆:給定G(x1,x2,…,xn)=(y1′,y2′,…,yn′),可以依次求出(x1′,x2′,…,xn′):

2.3.2 對(duì)三角型方案的攻擊

針對(duì)TTM三角型密碼系統(tǒng)的攻擊主要有2種:線性化方程攻擊和最小秩攻擊。

線性化方程攻擊是指TTM密碼系統(tǒng)存在如下的線性化方程:

其中,aij,bi,ci,d為方程式的(n+1)2個(gè)系數(shù)。

在給出O((n+1)2)個(gè)明密文對(duì)(x1,x2,…,xn,y1,y2,…,yn)時(shí),可以求解上述方程組的系數(shù)。一旦所有的系數(shù)均被求解得到,在給定密文y=(y1,…,yn)的情況下,就可得到關(guān)于明文x=(x1,x2,…,xn)的n個(gè)線性方程組。

最小秩攻擊是指把TTM密碼系統(tǒng)的分析問題轉(zhuǎn)化成求解最小秩的問題。首先把TTM系統(tǒng)的公鑰多項(xiàng)式轉(zhuǎn)化成二次型,然后得到該二次型下的一組n×n矩陣(M1,M2,…,Mm)。希望找到一組向量使得其中,Rank(·)表示矩陣的秩。在TTM系統(tǒng)中d比較小,最小秩問題在多項(xiàng)式時(shí)間內(nèi)可以求解,也就是說最小秩攻擊可以打敗TTM密碼系統(tǒng)。

3 簽名方案

當(dāng)前的多變量公鑰密碼體制中,大部分處于不同程度地攻擊,構(gòu)造一種安全性好的多變量公鑰加密和簽名方案仍是一個(gè)值得研究的開放課題。Square加密體制能夠抵抗線性攻擊和最小秩攻擊,但是受到差分攻擊的影響;三角型密碼系統(tǒng)能夠抵抗差分攻擊,但不能夠抵抗線性攻擊和最小秩攻擊。

3.1 方案描述

本文將2種方案結(jié)合起來,構(gòu)造一種混合的多變量公鑰簽名方案?；旌虾灻桨傅慕Y(jié)構(gòu)如圖2所示。

圖2 混合簽名方案

其中,S:和T:分別為可逆仿射變換,中心映射的構(gòu)造思想類似于Square加密體制,為單射仿射變換,φ為k同構(gòu):K→km+l,φ(a0+a1x+…+,F:K→K,F(X)=X2;中心映射G:為三角型映射。

公鑰包含以下內(nèi)容:

(1)有限域k以及域上的加法和乘法運(yùn)算;

(2)映射P=T°(+G)°S。

私鑰包含以下內(nèi)容:

(1)可逆仿射變換S:和

簽名:設(shè)M為待簽名文件,用公開的哈希函數(shù)Hash計(jì)算(x1,x2,…,x2m+l)=Hash(M)(l?m)。簽名步驟如下:

(1)計(jì)算X′=(x1′,x2′,…,x2m+l′)=S(x1,x2,…,x2m+l);

(2)選取X′=(x1′,x2′,…,x2m+l′)中的前m個(gè)分量,即(x1′,x2′,…,xm′),則其余的分量記為(xm+1′,…,x2m+l′),經(jīng)過中心映射,計(jì)算Y1′=(y11′,y12′,…,y1(m+l)′)=(x1′,x2′,…,xm′)和Y2′=(y21,′y22′,…,y2(m+l)′)=G(xm+1′,…,x2m+l′),得到Y(jié)′=(y1′,y2′,…,ym+l′)=Y1′⊕Y2′=(y11′+y21′,…,y1(m+l)′+y2(m+l)′);

(3)經(jīng)過仿射變換T,得到Y(jié)=(y1,y2,…,ym+l)=T(y1′,y2′,…,ym+l′)即為簽名值。

驗(yàn)證:驗(yàn)證者收到消息M和簽名(y1,y2,…,ym+l)后,驗(yàn)證如下:

(1)計(jì)算Hash(M)=(x1,x2,…,x2m+l);

(2)驗(yàn)證方程組P(x1,x2,…,x2m+l)=(y1,y2,…,ym+l)是否成立。若成立,則簽名有效,否則,簽名無效。

3.2 方案效率分析

本文方案在中心映射的設(shè)計(jì)上采用分支思想,在硬件實(shí)現(xiàn)上,便于進(jìn)行并行化操作。不妨設(shè)消息摘要的長(zhǎng)度為2m+l,則在一般情況下(沒有采用分支時(shí))完成簽名需要在多項(xiàng)式時(shí)間O((2m+l)2)內(nèi)完成;在本文的方案中,完成簽名至多在多項(xiàng)式時(shí)間O(m2+(m+l)2),約為O(2m2),即簽名的時(shí)間復(fù)雜度為O(2m2)。因此,方案具有很好的效率。由混合簽名方案的結(jié)構(gòu)可知,簽名長(zhǎng)度為(m+l)q。

4 安全性分析

目前,針對(duì)多變量數(shù)字簽名方案的典型攻擊方法主要有線性化方程攻擊(線性攻擊)、差分攻擊、秩攻擊、代數(shù)攻擊等,當(dāng)針對(duì)多變量數(shù)字簽名方案的攻擊算法計(jì)算復(fù)雜度均大于O(280)時(shí),稱該方案的安全強(qiáng)度達(dá)到O(280)。下面以選取參數(shù)q=216,m=16,l=4為例對(duì)混合簽名方案進(jìn)行安全分析。

4.1 線性攻擊

混合簽名方案的公鑰P也可表示為:

其中,T°φ°F°φ-1°L°S為Square密碼體制;T°G°S為三角型密碼系統(tǒng)。

對(duì)T°φ°F°φ-1°L°S而言,中心映射F=X2(即MI的中心映射Y=Xqθ+1中θ=0的情形)。而線性化方程攻擊是利用MI類的中心映射的關(guān)系XYqθ-Xq2θY=0得到的X與Y的線性關(guān)系進(jìn)行攻擊的。在混合簽名方案中,取θ=0,不能得到系統(tǒng)T°φ°F° φ-1°L°S關(guān)于X與Y的線性關(guān)系,從而得不到公鑰P=T°(+G)°S中X與Y的線性關(guān)系,所以,混合簽名方案可抵抗一般線性化方程攻擊。

Ding等人在PKC 2007提出了針對(duì)中間域多變量公鑰加密體制(MFE)的高階線性化方程攻擊[14]?？紤]混合簽名方案中含有三角型密碼系統(tǒng),需要對(duì)混合簽名方案進(jìn)行抗HOLE攻擊分析。

由混合簽名方案的公鑰為:P=T°(φ°F°φ-1°L+G)°S=T°(+G)°S。在簽名過程中經(jīng)過變換S后,變量分為兩部分(x1,′x2,′…,xm′)和(xm+1,′xm+21,′…,x2m+l′),中心映射為+G:X′→Y′,即:

類似于MFE加密方案[15],變量(xm+1′,xm+2′,…,x2m+l′)與(y21′,y22′,…,y2(m+l)′)存在高階線性化方程,但系統(tǒng)加入了(y11′,y12′,…,y1(m+l)′),相當(dāng)于在三角型系統(tǒng)中加入了外部干擾,而加入外部干擾后就打破了高階線性化方程攻擊的可能[16]。事實(shí)上,在一般情況下,在三角型系統(tǒng)中,中心映射的輸入變量與輸出變量一般不會(huì)存在特殊的關(guān)系,即不會(huì)存在高階線性化方程關(guān)系,所以混合簽名方案能抵抗高階線性化方程攻擊。

綜上所述,混合簽名方案可抵抗線性化攻擊。

4.2 差分攻擊

多變量公鑰密碼系統(tǒng)中,差分攻擊主要針對(duì)中心映射形如F:X→Xql+1的體制提出[17]。

由于在系統(tǒng)中P1=T°φ°F°φ-1°L°S中F的特殊形式使得DP1(X,Y)=T(2·S(X)·S(Y)),從而可以尋找不變子空間來恢復(fù)密鑰信息。

但混合簽名方案中P=T°(+G)°S引入了中心映射G,G不是形如G:X→Xql+1的映射,整體中心映射的結(jié)構(gòu)發(fā)生變化,且引入G后條件DP(X,Y)=T(2·S(X)·S(Y))也不能滿足,針對(duì)Square的攻擊也不適應(yīng)于新的混合簽名方案,所以,利用差分手段對(duì)混合簽名方案進(jìn)行攻擊不可行。

4.3 秩攻擊

考慮到針對(duì)三角型密碼系統(tǒng)的攻擊主要是最小秩攻擊,這里的秩攻擊特指最小秩攻擊。最小秩攻擊的復(fù)雜度為qtr(w2(nt/2-w/6)+wn2t)～O(qtrw3),其中,;r各方程的線性組合所能達(dá)到的最小秩;n為方程組中變量的個(gè)數(shù);w為方程的個(gè)數(shù)[18]。由給出的參數(shù)可知,混合簽名方案中q=216,m=20,n=36,從而t=1。將中心映射轉(zhuǎn)為可以利用的矩陣形式,將公鑰轉(zhuǎn)為20個(gè)36×36的矩陣,r為公鑰矩陣的一組線性組合達(dá)到的最小秩。只要保證r≥5,最小秩攻擊的復(fù)雜度就大于O(280)。

在三角型密碼系統(tǒng)中,通常r的取值很小,比如TTM體制,r=2,所以三角形系統(tǒng)容易受到最小秩攻擊[7]。在混合簽名方案中,引入了Square方案,從而使得r增大,所以20個(gè)36×36的矩陣的線性組合的秩很容易滿足r≥5。

綜上,在參數(shù)選取合適的情況下,混合簽名方案可抵御最小秩攻擊。

4.4 代數(shù)攻擊

代數(shù)攻擊是直接針對(duì)公鑰方程組的,常用的工具包括Gr?bner基攻擊和XL算法[19-20]。

根據(jù)方程的個(gè)數(shù)m和變量的個(gè)數(shù)n之間的關(guān)系,代數(shù)攻擊分為m=n,m＞n和m＜n3種情況進(jìn)行。但在混合簽名方案中,方程的個(gè)數(shù)為m+l,變量的個(gè)數(shù)為2m+l＞m+l,所以僅就m＜n的情形進(jìn)行討論。當(dāng)m＜n時(shí),多元二次方程組為不定方程組[11],求解的復(fù)雜度約等于窮盡搜索的復(fù)雜度O(qm)。在本文方案中,參數(shù)q=216,m=20,復(fù)雜度為O(2320),所以,混合簽名方案能夠抵抗代數(shù)攻擊。

5 結(jié)束語

本文結(jié)合Square體制和三角型密碼系統(tǒng),構(gòu)造了新的中心映射,提出一種混合的多變量公鑰簽名方案。由安全性分析可知,該方案克服了Square體制和三角型密碼系統(tǒng)的缺陷,能夠抵抗線性攻擊、差分攻擊、最小秩攻擊和代數(shù)攻擊。本文簽名方案參數(shù)的選取以及是否存在對(duì)其新的攻擊是下一步要研究的問題。

[1] Shor P.Polynomial-time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer[J].Aiam Journal on Scientific Computing,1999,41(2):303-332.

[2] Fu Xingqun,Bao Wandu,Zhou Chun.Speeding up Implementation for Shor’s Factorization Quantum[J]. Chinese Science Bull,2010,(4):322-327.

[3] Bernstein D J,Buchmann J,Dahmen E.Post-quantum Cryptography[M].Berlin,Germany:Springer,2009.

[4] Ding Jintai,Yang B Y.Multivariate Public Key Cryptography[M].Berlin,Germany:Springer,2009.

[5] 孫昌毅,李益發(fā),斯雪明.基于多變量公鑰密碼體制的代理重簽名方案[J].計(jì)算機(jī)工程,2012,38(17): 116-118.

[6] 喬帥庭,韓文報(bào),李益發(fā),等.基于外部干擾的中間域公鑰簽名方案的優(yōu)化[J].信息工程大學(xué)學(xué)報(bào),2013, 14(2):135-140.

[7] Moh T.A Public Key System with Signature and Master Key Functions[J].Communications in Algebra,1999, 27(5):2207-2222.

[8] Goubin L,Courtois N T.Cryptanalysis of the TTM Cryptosystem[C]//Proceedings of Asiacrypt’ 00. Berlin,Germany:Springer,2000:44-57.

[9] Tsujii S,Gotaishi M,Tadaki K,et al.Proposal of a Signature Scheme Based on STS Trapdoor[EB/OL]. (2004-05-20).http://www.eprint.iacr.org/2004/366.

[10] Clough C,Baena J,Ding J T,et al.Square,A New Multivariate Encryption Scheme[C]//Proceedings of CT-RSA’09.Berlin,Germany:Springer,2009:252-264.

[11] Billet O,Macario-Rat G.Cryptanalysis of the Square Cryptosystems[C]//Proceedings of ASIACRYPT’09. Berlin,Germany:Springer,2009:451-468.

[12] 孫昌毅,李益發(fā),張文政,等.基于多變量密碼體制的新型代理簽名方案[J].四川大學(xué)學(xué)報(bào):自然科學(xué)版, 2013,49(3):565-569.

[13] 陶 羽.多變量數(shù)字簽名的研究與設(shè)計(jì)[D].西安:西安電子科技大學(xué),2012.

[14] Ding J,Hu L,Nie X,et al.High Order Linearization Equation(HOLE)Attack on Multivariate Public Key Cryptosystems[C]//Proceedings of PKC’07.Berlin, Germany:Springer,2007:233-248.

[15] Wang L C,Yang B Y,Hu Y H,et al.A“Medium-field”Multivariate Public-key Encryption Scheme[C]// Proceedings of CT-RSA’06.Berlin,Germany:Springer, 2006:132-149.

[16] Tian L,Bao W S.A Medium Field Multivariate Public key Signature Scheme with ExternalPerturbation[C]// ProceedingsofCorference on IntelligentInformation Technology and Security Informatics.[S.1.]:IEEE Perss, 2010:753-757.

[17] Fouque P A,Granboulan L,Stern J.Differential Cryptanalysis for Multivariate Schemes[C]//Proceedings of EUROCRYPT’05.Berlin,Germany:Springer,2005: 341-353.

[18] 魯曉彬.幾類多變量數(shù)字簽名方案研究[D].鄭州:解放軍信息工程大學(xué),2012.

[19] Albrecht M R,Cid C,Faugère J C,et al.On the Relation Between the MXL Family of Algorithms and Gr?bner Basis Algorithms[J].Journal of Symbolic Computation, 2012,47(8):926-941.

[20] Thomae E,Wolf C.Solving Underdetermined Systems of Multivariate Quadratic Equations Revisited[C]//Proceedings of PKC’12.[S.1.]:IEEE Press,2012:156-171.

編輯 索書志

A Hybrid Multivariate Public Key Signature Scheme

LI Xiaoli1,QIAO Shuaiting2,LIU Jia3
(1.College of Information Science and Engineering,Henan University of Technology,Zhengzhou 450001,China; 2.State Key Laboratory of Mathematical Engineering and Advanced Computing,Information Engineering University, Zhengzhou 450001,China;3.Air Defense Forces Command Academy,Zhengzhou 450052,China)

Multivariate public key cryptosystem mechanism can resist attacks from the quantum computer,so it is believed to be an alternative secure cryptosystem in the post-quantum age.Considering that the Square scheme can resist linearization attack,but it can not be resistant against differential attack,and tame transformation method can resist differential attack,but it cannot be resistant against linearization attack and the minrank attack,by combining the Square scheme and tame transformation method,and using a new framework,a new central mapping is redesigned,and a hybrid multivariate public key signature scheme is proposed.Analysis results show that the hybrid signature cryptosystem has good efficiency and overcomes the drawbacks of the Square scheme and tame transformation method.Meanwhile,it can also resist linearization attack(including ordinary linearization attack and High Order Linearization Equation(HOLE) Attack),differential attack,the minrank attack and algebraic attack.

multivariate public key cryptography;hybrid multivariate signature scheme;linearization attack;differential attack;minrank attack;algebraic attack

1000-3428(2015)01-0121-05

A

TP309

10.3969/j.issn.1000-3428.2015.01.022

國(guó)家自然科學(xué)基金資助項(xiàng)目(61300123)。

李曉莉(1976-),女,講師、博士,主研方向:信息安全;喬帥庭,碩士研究生;劉 佳,講師、博士。

2014-01-14

2014-03-26 E-mail:lixiaoli201311@163.com

中文引用格式:李曉莉,喬帥庭,劉 佳.一種混合多變量公鑰簽名方案[J].計(jì)算機(jī)工程,2015,41(1):121-125.

英文引用格式:Li Xiaoli,Qiao Shuaiting,Liu Jia.A Hybrid Multivariate Public Key Signature Scheme[J].Computer Engineering,2015,41(1):121-125.