高雪辰，郭顯久、2

(1.大連海洋大學(xué)信息工程學(xué)院，遼寧大連116023;2.遼寧省海洋信息技術(shù)重點(diǎn)實(shí)驗(yàn)室，遼寧大連 116023）

一種同態(tài)驗(yàn)證環(huán)簽名方案的安全性分析與改進(jìn)

高雪辰1，郭顯久1、2

(1.大連海洋大學(xué)信息工程學(xué)院，遼寧大連116023;2.遼寧省海洋信息技術(shù)重點(diǎn)實(shí)驗(yàn)室，遼寧大連 116023）

對(duì)2012年Wang等提出的一種新的應(yīng)用于云計(jì)算的共享數(shù)據(jù)可公開審計(jì)方法中的同態(tài)驗(yàn)證環(huán)簽名方案進(jìn)行了分析。結(jié)果表明，該方案容易受到群成員改變攻擊，并且給出了攻擊方法。為了防止攻擊，對(duì)該方案進(jìn)行了改進(jìn)，并對(duì)新方案做了安全性分析，證明其具有安全性。

環(huán)簽名;雙線性對(duì);公開審計(jì)

環(huán)簽名的概念最早由Rivest等［1］在2001年提出，最初的環(huán)簽名方案思想是基于RSA公鑰密碼體制。此后，很多研究者相繼提出了各種環(huán)簽名方案［2－4］，繼而使環(huán)簽名得到了較為廣泛的應(yīng)用。與一般的數(shù)字簽名不同，環(huán)簽名最吸引人的地方在于它的不可偽造性和無條件匿名性。

2007年，Ateniese等［5］第一次提出了在云計(jì)算環(huán)境下的可證數(shù)據(jù)持有性 (provable data possession，PDP）模型。該P(yáng)DP模型主要運(yùn)用了同態(tài)理論以及RSA公鑰密碼體制，實(shí)現(xiàn)了遠(yuǎn)程數(shù)據(jù)持有性證明，并且大大減少了證明過程中的通信量。隨后PDP模型理論得到了快速發(fā)展，很多新型的遠(yuǎn)程數(shù)據(jù) PDP 方案被提出［6－8］。

2012年，Wang等［9］將PDP模型與環(huán)簽名理論相結(jié)合，提出了Oruta公開審計(jì)方法，該方法可以在云服務(wù)器上對(duì)共享數(shù)據(jù)進(jìn)行公開審計(jì)，并對(duì)其用戶的隱私給予保留。Oruta公開審計(jì)方法主要基于同態(tài)驗(yàn)證環(huán)簽名方案 (HARS），可以允許一個(gè)用戶群組通過TPA(第三驗(yàn)證方）在云服務(wù)器上公開驗(yàn)證共享的存儲(chǔ)數(shù)據(jù)的完整性，而無需取回所有的共享數(shù)據(jù)。與此同時(shí)，在驗(yàn)證的過程中，每個(gè)具有共享數(shù)據(jù)身份的用戶都可以通過TPA持有自己的私鑰，以便通過TPA來公開驗(yàn)證共享數(shù)據(jù)的完整性。經(jīng)分析發(fā)現(xiàn)，HARS方案其模型存在安全缺陷，本研究中對(duì)此提出了分析和改進(jìn)，彌補(bǔ)了此方案的不足。

1 雙線性對(duì)

HARS方案以及本研究改進(jìn)的方案都將用到雙線性對(duì)的性質(zhì)。雙線性對(duì)是定義于橢圓曲線上的一種映射，滿足雙線性性質(zhì)。設(shè)G1和G2為兩個(gè)乘法循環(huán)群，其階都為質(zhì)數(shù)p。令g1和g2分別為群G1和G2的生成元。令φ為從G2到G1的同構(gòu)映射，即φ(g2）=g1。

雙線性對(duì)e:G1×G2→GT，e滿足下列條件:

(1）雙線性。對(duì)于u∈G1、v∈G2和 a、b∈Z，有

(2）非退化性。e(g1，g2）≠1。

(3）可計(jì)算性。存在有效算法計(jì)算e(u，v）。

目前，雙線性對(duì)大多是基于 Weil配對(duì)［10］或Tate配對(duì)［11－12］實(shí)現(xiàn)的。假設(shè) G1和 G2為兩個(gè)乘法循環(huán)群，階為p，p為G1的生成元，則解決下列問題是困難的:

(1）離散對(duì)數(shù)問題 (DLP）。任取Q∈G1，找出一個(gè)n∈，使得滿足Q=Pn。

(2）計(jì)算 Diffie－Hellman問題 (CDHP）。? (P，Pa，Pb）∈，其中 a、b∈，求出Pab。

(3）決策 Diffie－Hellman問題 (DDHP）。? (P，Pa，Pb，Pc）∈，其中 a、b、c∈，判斷ab≡c mod p是否成立。

(4）Gap Diffie－Hellman問題 (GDHP）。一類CDHP解決困難而DDHP解決容易的問題。

(5）雙線性逆 Diffie－Hellman問題(BIDHP）。? (P，Pa，Pb）∈，其中 a、b∈，計(jì)算e(P，P）ab－1。

(6）逆Diffie－Hellman計(jì)算問題 (Inv－CDHP）。? (P，Pa）∈，其中 a∈，計(jì)算Pa－1。

2 文獻(xiàn) ［9］中的HARS方案及其攻擊方法

2.1 安全模型

HARS方案包括3種算法:KeyGen、RingSign和RingVerify。在KeyGen算法中，用戶群中的每個(gè)用戶都可生成其公鑰和私鑰;在RingSign算法中，用戶群中的每個(gè)用戶都可以用其私鑰和其他用戶的公鑰對(duì)數(shù)據(jù)分組生成環(huán)簽名;在RingVerify算法中，驗(yàn)證者可以檢查一個(gè)給出的數(shù)據(jù)分組環(huán)簽名對(duì)是否由該群中某一成員生成。HARS方案具有以下性質(zhì):

(1）正確性。對(duì)于給出的任意數(shù)據(jù)分組及其環(huán)簽名，一個(gè)驗(yàn)證者都可以正確地通過該方案來檢查此數(shù)據(jù)分組的完整性。

(2）不可偽造性。對(duì)于任何一個(gè)偽造者A來說，想對(duì)此方案?jìng)卧斐鲆粋€(gè)環(huán)簽名在計(jì)算上是不可行的。

(3）同態(tài)性。該方案是一個(gè)具有同態(tài)性質(zhì)的方案，包括無阻塞驗(yàn)證性以及不可延展性。

(4）完全匿名性。對(duì)于任意的擁有d個(gè)用戶的用戶群組U，以及任意一種算法ξ來說，在U中的任意一個(gè)可以成為真實(shí)簽名者的Us，用算法ξ可以計(jì)算出其真實(shí)身份的概率不超過1/d。

2.2 HARS方案

假設(shè)G1、G2和GT分別為具有相同階p的循環(huán)乘法群，g1和g2分別由G1和G2生成。設(shè)e:G1×G2→GT為雙線性對(duì)，φ (g2）=g1，H1∶{0，1}*→G1為一個(gè)哈希函數(shù)，系統(tǒng)參數(shù)為param=(e，φ，p，G1，G2，GT，g1，g2，H1）。用戶群中的用戶總數(shù)為d。

(1）密鑰產(chǎn)生KeyGen。用戶ui隨機(jī)選取xi∈Zp，計(jì)算wi=∈G2。用戶得到公鑰pki=wi，以及相應(yīng)的私鑰ski=xi。

(2）環(huán)簽名產(chǎn)生RingSign。給出用戶的公鑰集合 (pk1，…，pkd）=(w1，…，wd），數(shù)據(jù)分組m∈Zp，該分組的標(biāo)識(shí)為 id，以及相對(duì)于用戶s的私鑰 sks，隨機(jī)選取 ai∈Zp，i≠s，i∈ ［1，d］，令σi=。用戶 (簽名者）s計(jì)算β=H1(id）∈G2，使

輸出環(huán)簽名 σ=(σ1，…，σd）∈，L=(w1，…，wd），以及消息m。

(3）環(huán)簽名確認(rèn)RingVerify。當(dāng)接收到環(huán)簽名(L，m，σ）后，確認(rèn) e(β，g2）與e(σi，wi）是否相等。如果相等，則m是被d個(gè)用戶中的一個(gè)用戶簽名，反之則不成立。

2.3 對(duì)HARS方案的攻擊方法

通過對(duì)上述方案進(jìn)行分析，發(fā)現(xiàn)在其安全模型中存在群成員改變的攻擊方法。設(shè)σ=(σ1，…，σd）為m的環(huán)簽名，偽造者A在不知道任何用戶群成員私鑰的情況下，可以增加Ud+1進(jìn)入成員集，但仍然可以通過簽名確認(rèn)。

偽造者A任取t∈Zp，使得=σd+twd+1，= － twd，令= σi，i=1，2，…，n－1。消息m 的新簽名為 σ =(，…，，），則新簽名能夠通過確認(rèn)，利用雙線性對(duì)的性質(zhì)，證明如下:

上式說明，偽造者A所偽造的環(huán)簽名可以通過環(huán)簽名確認(rèn)RingVerify，從而成功地偽造了環(huán)簽名，使得同態(tài)驗(yàn)證環(huán)簽名方案存在群成員改變攻擊。

3 對(duì)文獻(xiàn) ［9］中HARS方案的改進(jìn)和安全性分析

3.1 改進(jìn)的方案

由于HARS方案在其安全模型中存在群成員改變攻擊，針對(duì)這種攻擊方式，對(duì)原方案進(jìn)行如下改進(jìn):在環(huán)簽名產(chǎn)生RingSign階段，給出所有用戶的公鑰集合，不妨設(shè)為 L=(pk1，…，pkd）=(w1，…，wd），數(shù)據(jù)分組m∈Zp，該分組標(biāo)識(shí)為id，以及相對(duì)于用戶 s的私鑰sks，隨機(jī)選取 ai∈Zp，i≠s，i∈ ［1，d］，計(jì)算 σi=。用戶 (簽名者）s計(jì)算

其中，L為用戶群成員的公鑰集合。輸出環(huán)簽名σ =(σ1，…，σd）∈，L=(W1，…，Wd），以及消息分組m。

3.2 安全性分析

定理1(正確性） 任意一個(gè)有效的數(shù)據(jù)分組及其環(huán)簽名能夠通過驗(yàn)證者的檢測(cè)。

證明:設(shè)公鑰集合 L=(pk1，…，pkd）=(w1，…，wd），能夠得到:

定理2(不可偽造性） 假設(shè)攻擊者A能夠以(t'，ε'）偽造改進(jìn)的環(huán)簽名，則存在一種算法，該算法能夠以 (t，ε）解決BIDHP困難問題。其中，

A發(fā)出至多個(gè)qH哈希請(qǐng)求和qs個(gè)環(huán)簽名請(qǐng)求，e=limqs→∞(1+1/qs）qs，cG1為在 G1上運(yùn)算的消耗，cG2為在G2上冪運(yùn)算的消耗。

首先，B從Zp中隨機(jī)選取 (x2，…，xn），并且設(shè)x1=1。然后令pki=wi= (）xi，其中pki代表用戶i的公鑰。A得到公鑰集合L=(pk1，…，pkd）=(w1，…，wd）。不失一般性，假設(shè) A可以為每個(gè)數(shù)據(jù)分組m、標(biāo)識(shí)id和L發(fā)出環(huán)簽名產(chǎn)生的請(qǐng)求和哈希請(qǐng)求。

在每個(gè)哈希請(qǐng)求中，B需要做出投擲硬幣的選擇，假如以概率Pc為投擲了背面，那么顯示為0，否則為1。這時(shí)，B隨機(jī)從ZP中選取r，如果投擲為背面0的時(shí)候，B會(huì)返回φ(）r，否則返回φ）r。

假設(shè)A對(duì)數(shù)據(jù)分組m、標(biāo)識(shí)id和L發(fā)出環(huán)簽名產(chǎn)生的請(qǐng)求。那么通過上述假設(shè)，一個(gè)哈希請(qǐng)求將在這個(gè) (m，id，L）上發(fā)出。如果B在哈希請(qǐng)求中投擲了0，則B失敗退出。否則，B返回H1(id，L）=φ(）r。如此，B選擇隨機(jī)的 a2，…，ad∈ZP，計(jì)算a1=r－ (a2x2+…+adxd），然后返回簽名σ=(，…，）。

最后，A在數(shù)據(jù)分組m和標(biāo)識(shí)id上輸出一個(gè)偽造的簽名σ=(σ1，…，σd）。再次通過之前的假設(shè)，一個(gè)哈希請(qǐng)求將在這個(gè) (m，id，L）上發(fā)出。如果B在哈希質(zhì)疑中沒投擲0，則B退出。否則H1(id，L）=，r由B產(chǎn)生，B通過計(jì)算(）1/r輸出。

A不能區(qū)分B的模擬和真實(shí)身份。如果A成功地偽造了簽名，那么B將輸出。B不失敗的概率為(1－P），當(dāng)Pc=qs/(qs+1）時(shí)最大，值域?yàn)?1/(e(1+qs）），e=limqs→∞(1+1/qs）qs。B算法需要做以下次運(yùn)算:在設(shè)置G2上做d次取冪運(yùn)算，每個(gè)A的哈希請(qǐng)求在G1上都做1次取冪運(yùn)算，每個(gè)A的環(huán)簽名生成請(qǐng)求在G1上都做d+1次取冪運(yùn)算，以及在G1上輸出做d次取冪運(yùn)算。所以，B的運(yùn)算時(shí)間是在A運(yùn)算時(shí)間上再加cG1(qH+dqs+qs+d）+cG2d。

由于BIDHP問題可通過用B算法解決兩個(gè)隨機(jī)問題而得到解決，因此，如果A利用算法 (t'，ε'）生成一個(gè)擁有d個(gè)用戶的群組的偽造環(huán)簽名，就需要存在一種算法 (t，ε）去解決co－CDH問題，這個(gè)算法的復(fù)雜度為

但目前來說，解決co－CDH問題仍然是比較困難的，也就是說，對(duì)于攻擊者A來說，偽造環(huán)簽名在計(jì)算上是不可行的，所以新方案具有不可偽造性。

定理3(完全匿名性） 對(duì)于任意的擁有d個(gè)用戶的用戶群組L的環(huán)簽名，攻擊者A可以計(jì)算出其真實(shí)身份的概率不超過1/d。

證明:對(duì)于任意的h(h∈G1）和s(1≤s≤d），有 {，…，∶，i≠s，as被選擇于=h}與 {，…∶=h}同分布，所以給出簽名σ=(σ1，…，σd），攻擊者A可計(jì)算出簽名者真實(shí)身份的概率最多為1/d。

4 結(jié)語

本研究中通過對(duì)Wang等［9］提出的HARS方案進(jìn)行分析，發(fā)現(xiàn)該方案存在群成員改變攻擊，并給出了攻擊方法，繼而對(duì)其方案加以改進(jìn)，又對(duì)新方案進(jìn)行了安全性分析，證明了改進(jìn)后的方案更具有安全性。

［1］ Rivest R L，Shamir A，Tauman Y.How to leak a secret［C］//LNCS.In Advances in ASIACRYPT 2001，Berlin:Springer－ Verlag，2001，2248:552 －565.

［2］ Masayuki A，Miyako O，Koutarou S.1 － out－ of－ n signatures from a variety of keys［J］.IEICE Trans Fundamentals，2004，E87－A:131－140.

［3］ Zhang F G，Kwangjo K.ID －based blind signature and ring signature from pairings［C］//LNCS.In Advances in ASIACRYPT 2002.Berlin:Springer－ Verlag，2002，2501:548 －566.

［4］ Herranz J，Saez G.New identity － based ring signature schemes［C］//LNCS.ICICS 2004，Berlin:Springer－ Verlag，2004，3269:27－39.

［5］ Ateniese G，Burns R，Curtmola R，et al.Provable data possession at untrusted stores［J］.Proc.14th ACM Conference on Computer and Communications Security(CCS'07），2007，202(3）:598 －609.

［6］ Curtmola R，Khan O，Burns R，et al.MR － PPDP:multiple－ replica provable data possession［J］.Proc.28thIEEE International Conference on Distributed Computing Systems(ICDCS'08），2008，201(2）:411－420.

［7］ Erway C C，Kupcu A，Papamanthou C，et al.Dynamic provable data possession［J］.Proc.16th ACM Conference on Computer and Communications Security，2009，11(9）:213 －222.

［8］ Zhu Y，Wang H，Hu Z，et al.Efficient provable data possession for hybrid clouds［J］.Proc.17th ACM Conference on Computer and Communications Security，2010，10(4）:756 －758.

［9］ Wang B Y，Li B C，Hui L.Oruta:Privacy－ preserving public auditing for shared data inthe cloud［J］.IEEE Fifth International Conference on Cloud Computing，2012，46(1）:295 －302.

［10］ Boneh D，F(xiàn)ranklin M.Identity－ based encryption from the weft pairing［C］//LNCS.Advances in Cryptology － Crypto 2001.Berlin:Springer－Verlag，2001，2139:213 －229.

［11］ Barceto P S L M，Kim H Y.Efficient algorithms for pairing －based cryptosystems［C］//LNCS.Advances in Crptology －Crypto'02.Berlin:Springer－ Verlag，2002，2442:354 －368.

［12］ Galbraith S，Harrison K，Soldera D.Implementing the Tate Pairing［C］//LNCS.ANTS 2002，Berlin:Springer－ Verlag，2002:324－337.

Cryptanalysis and improvement of a homomorphic authenticable ring signature scheme

GAO Xue － chen1，GUO Xian － jiu1，2
(1.College of Information Engineering，Dalian Ocean University，Dalian 116023，China;2.Key Laboratory of Ocean Information Technology of Liaoning Province，Dalian 116023，China）

The new homomorphic authenticable ring signature scheme is analyzed，and it is used in the public auditing for shared data in cloud computing and proposed by Wang et al in 2012.It is found that their scheme is susceptible to group－changing attack whose method is also given in this paper.In order to avoid the attack，the paper deals with improvement of their scheme and scheme's security.

ring signature;bilinear pairings;public auditing

P315.69

A

10.3969/J.ISSN.2095 －1388.2014.02.021

2095 －1388(2014）02 －0201 －04

2013－05－18

上海市重點(diǎn)實(shí)驗(yàn)室開放課題項(xiàng)目 (AGK2013005）

高雪辰 (1988－），男，碩士研究生。E－mail:214751193@qq.com

郭顯久 (1963－），男，博士，教授。E－mail:gxj@dlou.edu.cn