基于多變量公鑰密碼體制的環(huán)簽名變體方案

劉筱茜,趙一鳴

(復(fù)旦大學(xué)軟件學(xué)院,上海201203)

基于多變量公鑰密碼體制的環(huán)簽名變體方案

劉筱茜,趙一鳴

(復(fù)旦大學(xué)軟件學(xué)院,上海201203)

基于多元二次方(MQ)問(wèn)題的多變量公鑰密碼體制是一種可以抵抗量子攻擊的系統(tǒng)。分析基于多變量公鑰密碼體制的環(huán)簽名方案,指出其存在密鑰泄露和安全證明錯(cuò)誤的問(wèn)題。為解決上述問(wèn)題,對(duì)環(huán)簽名者和其他環(huán)成員采用不同的密鑰構(gòu)造方式,提出一種可證明安全的環(huán)簽名變體方案。該方案最大程度地去除原方案對(duì)IP問(wèn)題的依賴,使得方案的安全性直接規(guī)約于MQ問(wèn)題,以提升安全性。在環(huán)簽名的標(biāo)準(zhǔn)安全模型下,分別從正確性、匿名性和不可偽造性等方面對(duì)方案進(jìn)行分析和安全性證明,結(jié)果表明,與原方案相比,該方案有較高的安全性。

多變量公鑰密碼體制;多元二次方問(wèn)題;IP問(wèn)題;密鑰泄露;環(huán)簽名;可證明安全

1 概述

量子計(jì)算機(jī)的發(fā)展對(duì)目前現(xiàn)有的公鑰密碼體制構(gòu)成了潛在的威脅,1994年Shor量子算法[1]的提出使得量子計(jì)算機(jī)能以多項(xiàng)式時(shí)間攻擊現(xiàn)有的基于大素?cái)?shù)分解和離散對(duì)數(shù)難題,因此,在量子計(jì)算機(jī)環(huán)境下,需要為基于這些問(wèn)題的簽名方案提供備選方案。目前,被認(rèn)為能夠抵抗量子計(jì)算攻擊的方案主要基于編碼、格和MQ問(wèn)題,其中基于MQ問(wèn)題構(gòu)造的方案由于占用資源較少的特點(diǎn),適用于低消耗的設(shè)備,如RFID芯片、智能卡等移動(dòng)設(shè)備上。

另一方面,在傳統(tǒng)密碼學(xué)中有許多不同的簽名方案設(shè)計(jì),如代理簽名、盲簽名等,適用于不同情形,其中包括環(huán)簽名。環(huán)簽名由Rivest等人于2001年提出[2],非常適用于消息的匿名發(fā)布等應(yīng)用場(chǎng)景,之后文獻(xiàn)[3]提出基于雙線性對(duì)的環(huán)簽名。環(huán)簽名不僅在傳統(tǒng)密碼學(xué)中,而且在量子計(jì)算環(huán)境下的應(yīng)用也具有很大研究意義。

本文主要分析文獻(xiàn)[4]中基于MPKC的簽名方案,指出其存在私鑰泄露問(wèn)題和安全性分析問(wèn)題,然后給出分析過(guò)程、改進(jìn)方案,以及新方案的可證明安全。

2 預(yù)備知識(shí)

2.1 MQ問(wèn)題

定義1 給定一個(gè)有限域GF(q)上m個(gè)多項(xiàng)式n個(gè)變量的隨機(jī)多變量二次多項(xiàng)式組p(1),p(2),…,p(m),求解一個(gè)向量x=(x1,x2,…,xn)∈GF(q)n,滿足p(1)(x)=…=p(m)(x)=0。

MQ問(wèn)題在文獻(xiàn)[5]中被證明是NP難解問(wèn)題,即使是在僅有2個(gè)元素的有限域GF(2)上仍是難解問(wèn)題。

2.2 MPKC方案

基于MQ問(wèn)題的多變量公鑰加密體系(MPKC)是在有限域GF(q)上構(gòu)建的多變量二次方程式系統(tǒng),其中有m個(gè)多項(xiàng)式n個(gè)變量,每個(gè)多項(xiàng)式的形式為:

現(xiàn)有的大多數(shù)MPKC方案中公鑰系數(shù)并非隨機(jī)選取,而是由可逆二次中心映射F和為了隱藏F的可逆仿射變換L和R來(lái)構(gòu)建公鑰P=L°F°R,因此,這些方案的安全性不僅基于MQ問(wèn)題,還基于IP問(wèn)題。

2.3 IP問(wèn)題

定義2 假設(shè)P和F是2個(gè)給定的有限域GF(q)上m個(gè)多項(xiàng)式n個(gè)變量的隨機(jī)多變量二次多項(xiàng)式組,求解有限域GF(q)上的2個(gè)仿射變換L∈GF(q)n×GF(q)n和R∈GF(q)m×GF(q)m,且P=L°F°R。

引入仿射變換L和R來(lái)隱藏中心映射F構(gòu)建公鑰P=L°F°R是為了讓合法用戶能夠容易解密密文,從而構(gòu)建單向陷門函數(shù),在此情況下P和F是同構(gòu)的。已知P和F求解仿射變換L和R的問(wèn)題稱為多項(xiàng)式同構(gòu)問(wèn)題,即IP(Isomorphism of Polynomials)問(wèn)題,該問(wèn)題已被證明為一個(gè)NP困難性問(wèn)題[6]。

2.4 環(huán)簽名方案

在環(huán)簽名方案中,簽名者選擇一個(gè)包括自己在內(nèi)的一個(gè)群組,用自己的私鑰和其他環(huán)成員的公鑰對(duì)消息進(jìn)行簽名。驗(yàn)證者可以驗(yàn)證消息的確來(lái)自該環(huán)中成員的簽名,但是不能指出具體簽名者。環(huán)簽名方案一般包括:系數(shù)生成,密鑰生成,簽名生成,簽名驗(yàn)證,最終滿足完整性、匿名性和不可偽造性。完整性:根據(jù)給出的環(huán)簽名和環(huán)成員公鑰信息能夠成功驗(yàn)證簽名;匿名性:任意2個(gè)環(huán)成員生成的環(huán)簽名對(duì)攻擊者來(lái)說(shuō)是不可區(qū)分的;不可偽造性:攻擊者成功偽造環(huán)簽名的概率是可忽略的。

3 MQ環(huán)簽名方案分析

3.1 基于MPKC的環(huán)簽名方案

MPKC的環(huán)簽名方案過(guò)程如下:

(1)系統(tǒng)建立(Setup)

生成系統(tǒng)參數(shù)(k,q,p,l,m,n,H),其中,k=GF(q)是特征為p的有限域;q=pl;l為正整數(shù);m是多變量方程組的個(gè)數(shù);H是變量的個(gè)數(shù)且m和n均為正整數(shù)。哈希函數(shù)H:{0,1}?→km,Pi(i=1, 2,…,r)是第i個(gè)環(huán)成員的公鑰,Pi=Li°Fi°Ri,其中,Li,Fi,Ri是該用戶的私鑰。

(2)密鑰生成(KGen)

環(huán)中每個(gè)成員的公私鑰對(duì)生成為(PKi,SKi),i=1,2,…,r。PKi:Pi=Li°Fi°Ri,SKi:Li,Fi,Ri,其中,Li,Ri分別是從km到km和kn到kn隨機(jī)選取的可逆仿射變換,Fi是有限域k=GF(q)上可逆的二次多變量方程的中心映射。

(3)簽名生成(PSign)

環(huán)成員U(u1,u2,…,ur)所對(duì)應(yīng)的公鑰集合為(P1,P2,…,Pr),現(xiàn)有一名環(huán)成員us代表整個(gè)環(huán)成員對(duì)消息進(jìn)行簽名,簽名者us的私鑰為SKi:Ls,Fs,Rs,對(duì)消息m進(jìn)行如下簽名操作:

首先,對(duì)除簽名者us外的所有環(huán)成員,隨機(jī)選取2個(gè)n維向量ai∈kn和kn(i=1,2,…,r,i≠s),令:

然后,對(duì)簽名者us隨機(jī)選取一個(gè)n維向量φs∈kn,并計(jì)算:

最后,給出消息m的MQ環(huán)簽名為δ=(U,a1,b1,…,ar,br)。

(4)簽名驗(yàn)證(Verify)

已知環(huán)成員集合U(u1,u2,…,ur),對(duì)應(yīng)的公鑰集合(P1,P2,…,Pr),對(duì)消息m產(chǎn)生的簽名δ=(U,a1,b1,…,ar,br),驗(yàn)證者檢驗(yàn)以下等式是否成立:

若式(5)成立,那么驗(yàn)證者接受該簽名,否則拒絕該簽名。

3.2 存在問(wèn)題

分析文獻(xiàn)[6]的方案,存在以下2個(gè)問(wèn)題: (1)整個(gè)方案進(jìn)行安全性分析前沒(méi)有考慮私鑰泄露問(wèn)題;(2)該方案是基于MPKC方案生成,非直接規(guī)約于MQ難解問(wèn)題,安全性說(shuō)明沒(méi)有說(shuō)服力。

針對(duì)文獻(xiàn)[6]存在的問(wèn)題,下面分別進(jìn)行相應(yīng)分析及給出解決方案。

(1)私鑰泄露

為了保證方案不泄露私鑰,則要使得環(huán)成員us的簽名方案是基于MQ問(wèn)題的安全簽名方案,所以有以下定理:

根據(jù)文獻(xiàn)[7]可知,目前基于MQ問(wèn)題的簽名方案被指出只有UOV,Rainbow,Enhanced TTS等幾種尚未被攻破的安全簽名方案,選取其中一種作為環(huán)簽名者us用自己私鑰進(jìn)行簽名得到as的安全簽名方案,并選取其對(duì)應(yīng)的安全參數(shù)系數(shù)。

(2)基于MQ難解問(wèn)題

文獻(xiàn)[6]的方案中,r個(gè)環(huán)成員均以P=L°F°R來(lái)構(gòu)造公私鑰對(duì),隨后說(shuō)明其基于MPKC方案的安全性。然而,如此構(gòu)造的方案并非是直接基于MQ問(wèn)題的簽名方案,而是結(jié)合了IP問(wèn)題從而加入了陷門函數(shù),使得方案易于轉(zhuǎn)置,具有較大的不安全性,如文獻(xiàn)[7-10]均為已被攻破方案,并且文獻(xiàn)[11]中指出大部分MPKC方案采用此構(gòu)造方式均已破解,所以需要構(gòu)建直接基于MQ問(wèn)題的環(huán)簽名方案以保證方案的安全性。

根據(jù)上一節(jié)中選定環(huán)簽名者us的安全簽名方案后,確定環(huán)U中其他環(huán)成員(u1,u2,…,us-1,us+1,…,ur)的公私鑰構(gòu)建方案應(yīng)為僅基于MQ問(wèn)題的MPKC方案。

4 變體方案

為避免私鑰泄露和提升方案安全性,下面對(duì)原方案的系統(tǒng)建立和密鑰生產(chǎn)進(jìn)行改進(jìn):

(1)系統(tǒng)建立(Setup)

生成系統(tǒng)參數(shù)(k,q,p,l,m,n,H),其中,k=GF(q)是特征為p的有限域;q=pl且為奇素?cái)?shù);l為正整數(shù);m是多變量方程組的個(gè)數(shù);n是變量的個(gè)數(shù)且m和n均為正整數(shù)。哈希函數(shù)H:{0,1}?→km。

(2)密鑰生成(KGen)

簽名生成和簽名驗(yàn)證和原方案一致。如此構(gòu)造的新方案不僅降低了原方案不安全的風(fēng)險(xiǎn),而且滿足文獻(xiàn)[12]中對(duì)(x)分布是偽隨機(jī)分布的分析定理。

5 可證明安全

根據(jù)環(huán)簽名方案模型設(shè)計(jì),MQ環(huán)簽名方案應(yīng)當(dāng)同時(shí)滿足完整性、匿名性和不可偽造性,下面對(duì)新方案進(jìn)行分別證明。

5.1 完整性

嚴(yán)格按照方案進(jìn)行簽名,并且在傳輸過(guò)程中沒(méi)有改變,那么驗(yàn)證者可知對(duì)消息m的簽名δ=(U,a1,b1,…,ar,br),環(huán)成員U(u1,u2,…,ur)以及他們的公鑰PKi,i=1,2,…,r。驗(yàn)證等式(6):

其中,φi=Pi(ai)+Pi(bi),那么代入ai,bi容易驗(yàn)證等式(6)成立,即新方案滿足完整性。

5.2 匿名性

為了證明新方案的匿名性,下面分析U(u1,u2,…,ur)中任意2個(gè)環(huán)成員uj,uk生成的簽名δj,δk是不可區(qū)分的。

定理3 環(huán)H(U,m,φ1,φ2,…,φr)中任意環(huán)成員ue(e=1,2,…,r)對(duì)消息m生成的MQ環(huán)簽名δe=(U,a1,b1,…,ae,be,…,ar,br)滿足偽隨機(jī)分布。

由新MQ環(huán)簽名設(shè)計(jì)方案可知,a1,a2,…,ae-1,ae+1,…,ar和b1,…,be-1,be+1,…,br是從有限域GF(q)n中隨機(jī)選取的。分析be=b-(b1+b2+…+be-1+be+1+…+br)。其中,b=H(U,m,φ1,φ2,…,φr)滿足偽隨機(jī)分布,所以be亦滿足偽隨機(jī)分布。再分析ae=L-1e°F-1e°R-1e(φe-Pe(be)),由于φe是在有限域GF(q)n上隨機(jī)選取的n維向量,因此φe-Pe(be)滿足偽隨機(jī)分布,同時(shí)在新方案中ae是采用基于MQ問(wèn)題的安全簽名方案如Rainbow,簽名滿足偽隨機(jī)性。綜上所述,環(huán)中任意成員ue生成的MQ環(huán)簽名δe=(U,a1,b1,…,ae,be,…,ar,br)滿足偽隨機(jī)性。

根據(jù)定理3可知,任意2個(gè)環(huán)成員uj,uk的簽名δj,δk均為偽隨機(jī)分布,那么滿足不可區(qū)分性,從而驗(yàn)證了新方案的匿名性成立。

5.3 不可偽造性

將等式(6)變形為b=H(U,m,θ),其中,θ:P1(a1)+P1(b1),…,Pr(ar)+Pr(br)。

假設(shè):簽名δ′(U,a′1,b′1,…,a′r,b′r)是攻擊者成功偽造的對(duì)消息m的一個(gè)能夠通過(guò)驗(yàn)證的MQ環(huán)簽名。

同時(shí),實(shí)際簽名者us通過(guò)新的簽名方案得到真實(shí)簽名δ(U,a1,b1,…,ar,br)。由于δ和δ’都能通過(guò)認(rèn)證,有以下等式成立:

情形1 若b≠b′,由式(7)、式(8)可知,H(U,m,θ)≠H(U,m,θ′),那么對(duì)于b′攻擊者找到了在哈希函數(shù)H(U,m,θ′)的一個(gè)原象,其中,θ′是偽造簽名的一部分,其余為公開(kāi)的環(huán)成員集合U和消息m。

情形2 若b=b′,則H(U,m,θ)=H(U,m,θ′)那么θ=θ′,即P1(a1)+P1(b1)=P1(a′1)+P1(b′1),…,Pr(ar)+Pr(br)=Pr(a′r)+Pr(b′r)其中,Pi是環(huán)成員i的公鑰,ai,a′i,bi,b′i∈kn為隨機(jī)選取的n維向量,根據(jù)定理2可知,Pi(ai),Pi(a′i),Pi(bi),Pi(b′i)均為偽隨機(jī)分布,則Pi(ai)+Pi(bi)和Pi(a′i)+Pi(b′i)也均為偽隨機(jī)分布,且不可區(qū)分,從而得出攻擊者成功破解了MQ問(wèn)題,這與MQ問(wèn)題是難解問(wèn)題相矛盾。

6 結(jié)束語(yǔ)

本文針對(duì)基于多變量公鑰密碼體制的環(huán)簽名方案進(jìn)行分析,指出其存在私鑰泄露。針對(duì)上述問(wèn)題,對(duì)該方案進(jìn)行了改進(jìn),提出一種可證明安全的環(huán)簽名變體方案,并給出完整的安全性證明,以MQ難解問(wèn)題為基礎(chǔ),進(jìn)行可證明安全分析,保證簽名方案的正確性、匿名性和不可偽造性。本文方案在提高了原方案安全性的同時(shí),還存在每次更換環(huán)簽名者時(shí),需重新生成環(huán)簽名者的公私鑰對(duì),這是下一步需要研究的問(wèn)題。

[1] Shor P W.AlgorithmsforQuantumComputation: Discrete Logarithms and Factoring[C]//Proceedings of the35thAnnualSymposiumonFoundationsof Computer Science.[S.1.]:IEEE Press,1994:124-134.

[2] Rivest R L,Shamir A,Tauman Y.How to Leak a Secret[M].Berlin,Germany:Springer,2001.

[3] Xu J,Zhang Z,Feng D.A Ring Signature Scheme Using Bilinear Pairings[M].Berlin,Germany:Springer,2005.

[4] 王曉蘭.基于多變量公鑰密碼體制的環(huán)簽名方案[J].河南科學(xué),2013,(3):318-321.

[5] Johnson D S.TheNP-completenessColumn:An Ongoing Guide[J].Journal of Algorithms,1984,5(3): 433-447.

[6] Patarin J.HiddenFieldsEquations(HFE)and Isomorphisms of Polynomials(IP):Two New Families ofAsymmetricalgorithms[C]//Proceedingsof Eurocrypt’96.Berlin,Germany:Springer,1996:33-48.

[7] Bouillaguet C,Faugère J C,Fouque P A,et al.Practical Cryptanalysis of the Identification Scheme Based on the Isomorphism ofPolynomialwithOneSecretProblem[C]//Proceedings of PKC’11.Berlin,Germany: Springer,2011:473-493.

[8] Dubois V,Fouque P A,Shamir A,et al.Practical CryptanalysisofSFLASH[C]//Proceedingsof CRYPTO’07.Berlin,Germany:Springer,2007:1-12.

[9] Kipnis A,Shamir A.Cryptanalysis of the Oiland VinegarSignatureScheme[C]//Proceedingsof CRYPTO’98.Berlin,Germany:Springer,1998:257-266.

[10] Patarin J.Cryptanalysis of the Matsumoto and Imai Public Key Scheme[C]//Proceedings of CRYPTO’95. Berlin,Germany:Springer,1995:248-261.

[11] Thomae E.About the Security of Multivariate Quadratic Public Key Schemes[EB/OL].(2013-10-21).http:// www.cits.rub.de/personen/thomae.html.

[12] Huang Y J,LiuFH,YangBY.Public-key CryptographyfromNewMultivariateQuadratic assumptions[C]//Proceedings of PKC’12.Berlin, Germany:Springer,2012:190-205.

編輯 索書志

Variant Scheme of Ring Signature Based on Multivariate Public Key Cryptosystems

LIU Xiaoqian,ZHAO Yiming
(Software School,Fudan University,Shanghai 201203,China)

Based on Multivariate Quadratic(MQ)problem,Multivariate Public Key Cryptosystems(MPKC)are regarded as systems resisting quantum attacks.This paper analyzes a ring signature scheme based on MQ and points out that there exist some issues such as secret key leakage and incorrect security proof.To solve these problems,this paper proposes a variant of ring signature scheme with provable security by applying different key generation methods to ring signer and the remaining ring members.The scheme removes the dependence on IP problem as much as possible,gaining higher security by direct reduction to MQ problem.This paper gives detailed analysis and security proof of the new scheme from the aspects of correctness,anonymity and unforgeability in the standard security model of ring signature. Compared with the original scheme,the scheme is more complete both in analysis and security proof.

Multivariate Public Key Cryptosystems(MPKC);Multivariate Quadratic(MQ)problem;IP problem; secret key leakage;ring signature;provable security

劉筱茜,趙一鳴.基于多變量公鑰密碼體制的環(huán)簽名變體方案[J].計(jì)算機(jī)工程,2015,41(2):96-99.

英文引用格式:Liu Xiaoqian,Zhao Yiming.Variant scheme of Ring Signature Based on Multivariate Public Key Cryptosystems[J].Computer Engineering,2015,41(2):96-99.

1000-3428(2015)02-0096-04

:A

:TP309

10.3969/j.issn.1000-3428.2015.02.019

國(guó)家“十二五”密碼發(fā)展基金資助項(xiàng)目。

劉筱茜(1990-),女,碩士研究生,主研方向:密碼學(xué),信息安全;趙一鳴,副教授。

2014-04-02

:2014-05-06E-mail:11212010019@fudan.edu.cn