劉筱茜,趙一鳴

(復旦大學軟件學院,上海201203)

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

劉筱茜,趙一鳴

(復旦大學軟件學院,上海201203)

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

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

1 概述

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

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

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

2 預備知識

2.1 MQ問題

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

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

2.2 MPKC方案

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

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

2.3 IP問題

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

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

2.4 環(huán)簽名方案

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

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

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

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

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

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

(2)密鑰生成(KGen)

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

(3)簽名生成(PSign)

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

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

然后,對簽名者us隨機選取一個n維向量φs∈kn,并計算:

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

(4)簽名驗證(Verify)

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

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

3.2 存在問題

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

針對文獻[6]存在的問題,下面分別進行相應分析及給出解決方案。

(1)私鑰泄露

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

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

(2)基于MQ難解問題

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

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

4 變體方案

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

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

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

(2)密鑰生成(KGen)

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

5 可證明安全

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

5.1 完整性

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

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

5.2 匿名性

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

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

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

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

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)是攻擊者成功偽造的對消息m的一個能夠通過驗證的MQ環(huán)簽名。

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

情形1 若b≠b′,由式(7)、式(8)可知,H(U,m,θ)≠H(U,m,θ′),那么對于b′攻擊者找到了在哈希函數(shù)H(U,m,θ′)的一個原象,其中,θ′是偽造簽名的一部分,其余為公開的環(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為隨機選取的n維向量,根據(jù)定理2可知,Pi(ai),Pi(a′i),Pi(bi),Pi(b′i)均為偽隨機分布,則Pi(ai)+Pi(bi)和Pi(a′i)+Pi(b′i)也均為偽隨機分布,且不可區(qū)分,從而得出攻擊者成功破解了MQ問題,這與MQ問題是難解問題相矛盾。

6 結(jié)束語

本文針對基于多變量公鑰密碼體制的環(huán)簽名方案進行分析,指出其存在私鑰泄露。針對上述問題,對該方案進行了改進,提出一種可證明安全的環(huán)簽名變體方案,并給出完整的安全性證明,以MQ難解問題為基礎(chǔ),進行可證明安全分析,保證簽名方案的正確性、匿名性和不可偽造性。本文方案在提高了原方案安全性的同時,還存在每次更換環(huán)簽名者時,需重新生成環(huá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].河南科學,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].計算機工程,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

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

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

2014-04-02

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