可驗證加密簽名方案的研究及進展*

關(guān)宏波，辛向軍，邱學(xué)邵

（鄭州輕工業(yè)學(xué)院信息與計算科學(xué)系 鄭州450002）

1 引言

在公鑰密碼學(xué)中，數(shù)字簽名是一個重要的研究內(nèi)容。由于數(shù)字簽名可提供消息認(rèn)證性、完整性和不可否認(rèn)性業(yè)務(wù)，因此其在電子商務(wù)、電子政務(wù)、軍事等領(lǐng)域有著重要的應(yīng)用。可驗證的加密簽名方案 （verifiably encrypted signature scheme，VESS）是普通簽名的一種擴展，其有三個參與方：簽名者、驗證者和仲裁者。在VESS方案中，用戶Alice利用自己的私鑰對消息m產(chǎn)生簽名signature，并同時利用仲裁者的公鑰對簽名進行加密，從而產(chǎn)生一個關(guān)于消息m的VESS簽名vess。驗證者Bob可以驗證vess確實是signature的密文，但Bob不能由vess推出或獲得signature的任何信息。若Alice不想或者不能（比如，Alice和Bob的通信中斷）將signature交付于Bob，Bob可將vess發(fā)送給仲裁者，并由仲裁者解密vess而獲得signature，從而仲裁者可將signature發(fā)送給Bob。VESS的這種特點使得多個簽名者或用戶之間可以安全地、公平地交換自己的簽名。這與電子商務(wù)中的要求：公平、安全、高效相一致，故其主要用于構(gòu)建優(yōu)化的公平交換協(xié)議[1，2]。

因此，為建立電子商務(wù)中公平、安全、高效、優(yōu)化的交換協(xié)議（如，電子合同的簽署與交換，在線購物），很有必要研究VESS的基本理論，建立安全、高效的VESS，為電子商務(wù)中交換協(xié)議的公平、安全、高效應(yīng)用提供理論依據(jù)和技術(shù)保障。因此，對VESS的研究具有重要的理論意義和實用價值。

2 國內(nèi)外研究現(xiàn)狀及分析

1976年，Diffie和Hellman提出了公鑰密碼體制。目前，公鑰的分配主要有兩種方法。第一種方法為基于公鑰證書的分配方法。在這種方法中，證書管理機構(gòu)（certificate authority，CA）給每個用戶簽發(fā)一個類似于數(shù)字簽名的公鑰證書，其中的數(shù)據(jù)項有與該用戶的私鑰相匹配的公鑰及用戶的身份和時戳等。用戶之間通過交換公鑰證書來相互交換自己的公鑰而無須與CA聯(lián)系。另一種方法為基于身份的分配方法。1984年，Shamir提出一種基于身份的加密思想，這也給出了基于身份的公鑰分配方法。這種方法將用戶的身份用作公鑰，而用戶的私鑰由可信的密鑰生成器（private key generator，PKG）根據(jù)用戶的身份產(chǎn)生，并由用戶秘密保存。因此，為便于分析，將VESS分成兩類：基于公鑰證書的VESS和基于身份的VESS，以此來討論VESS的研究現(xiàn)狀。

2.1 基于公鑰證書的VESS

早期的VESS的方案[1]效率并不高，因為其需要零知識證明協(xié)議來驗證一個VESS的有效性。Ateniese的方案[3]并未有較好的改觀，因為其仍然是基于零知識證明的。參考文獻[4]給出了基于對的隨機化的VESS方案，然而，其需要3個對運算。需要注意的是，在基于對的VESS方案中，對運算是最為耗時的，故應(yīng)在此類方案中盡量減少對運算的次數(shù)。Zhang等人[5]給出一個只有一個對運算的且簽名長度最短的VESS簽名方案，然而，這種VESS簽名方案是確定性的簽名方案（即對同一消息進行重復(fù)簽名，每次總是產(chǎn)生相同的簽名），其缺乏簽名的靈活性和新鮮性。為防止仲裁者與用戶的合謀，辛向軍等給出了一種多個仲裁者分割仲裁權(quán)的VESS體制[6]，該技術(shù)可為公平交換協(xié)議提供更好的安全性，其同樣只有一個對運算并具有較短的簽名。然而，該方案也局限于確定性簽名。為此，辛向軍等人又給出一個高效的隨機化的可驗證加密簽名方案[7]，其在保持簽名隨機性和一個對運算的前提下保證了較短的簽名。

以上所有的VESS的安全性都是在隨機預(yù)言機（random oracle model，ROM）下可證明安全的。需要注意的是，Canetti和Boneh等人的研究[8，9]說明ROM下的安全性僅是密碼體制安全性的一種基本度量，這意味著ROM下可證明安全的VESS體制的安全性需要在實際應(yīng)用環(huán)境中進一步檢驗。因此，為進一步提高VESS的安全性，Gorantla等先后提出標(biāo)準(zhǔn)模型下可證明安全的VESS簽名體制[10～14]，但其中多數(shù)方案至少需要兩個對運算，而參考文獻[11，12]中的方案比較高效，因為它們僅需一個對運算。

利用Boneh的方法[15]在標(biāo)準(zhǔn)模型下構(gòu)建VESS簽名為建立更為安全的VESS體制提供了一種有益的思路。然而，VESS體制是普通簽名體制的一種擴展，其有自身的特點，并主要用于電子商務(wù)中建立公平交換協(xié)議。首先，公平交換協(xié)議允許用戶在不同時間和不同地點交換相同類型的物品（簽名），這就需要標(biāo)準(zhǔn)模型下的VESS簽名體制應(yīng)具有強不可偽造性[9，15～22]，即不允許敵手或偽造者能夠?qū)ν幌卧觳煌暮灻?。然而，目前所有的?biāo)準(zhǔn)模型下的VESS簽名體制的強不可偽造性都沒有得到證明，這就意味著這些方案中敵手可能會對相同類型的物品偽造不同的VESS簽名。例如，在參考文獻[12]中，假定敵手知道關(guān)于消息m的兩個VESS簽名(r1，K1)和(r2，K2)，敵手可通過如下的步驟對消息m偽造一個新的簽名(r*，K*)：

第二步：敵手隨機選取r*∈Zp*并計算K*=u-r*v。

易驗證(r*，K*)滿足參考文獻[12]的VESS驗證方程。這樣，敵手偽造消息m的一個新的簽名(r*，K*)成功。因此，為使得VESS能夠滿足電子商務(wù)中公平交換協(xié)議的需要，需要標(biāo)準(zhǔn)模型下的VESS簽名體制應(yīng)具有強不可偽造性。

另外，以上所有的方案僅僅考慮了公平和安全的需要，而沒有考慮到用戶的隱私保護問題。特別是在一些涉及隱私及商業(yè)機密的簽名中，用戶不希望作為仲裁者的第三方也獲得用戶所交換的物品或簽名，甚至不希望第三方知道用戶之間交換的內(nèi)容。為實現(xiàn)用戶的隱私保護，辛向軍等利用短簽名給出一種具有離線半可信第三方的公平交換協(xié)議[17]，方案中離線第三方不必完全可信，因其在解決糾紛的同時并不能獲得交換雙方的簽名。這種協(xié)議使得作為仲裁者的第三方無法獲得用戶所交換的物品或簽名，從而能夠在一定程度上保護用戶的隱私。然而，這種協(xié)議中并未使用VESS體制，因此其效率并不優(yōu)于基于VESS的公平交換協(xié)議。因此，建立安全、高效并具有隱私保護可選項的優(yōu)化公平交換協(xié)議仍然是一個公開問題。

2.2 基于身份的VESS

基于身份的密碼系統(tǒng)使得用戶的身份標(biāo)識 （如名字、IP地址、E-mail等）可用作用戶的公鑰，從而避免了公鑰證書的生成、簽發(fā)、存儲、維護、使用、更新、撤銷這些復(fù)雜的過程，從而大大節(jié)約了系統(tǒng)的成本和代價，并極大地方便了用戶。為使VESS具有基于身份的密碼系統(tǒng)的優(yōu)點，Gu和Cheng等分別提出三種基于身份的可驗證加密簽名方案(ID-VESS)[18～20]。然而，參考文獻[18]的方案并不安全，張在參考文獻[21]中給出對參考文獻[18]中的方案的兩種攻擊：偽造VESS攻擊和合謀攻擊。這說明參考文獻[18]的方案不滿足不可偽造性。另外，Cheng等人給出的ID-VESS[19]并不是可證明安全的，因此，這直接影響到參考文獻[18，19]中方案在實踐中的應(yīng)用。需要注意的是，在參考文獻[18～20]的所有方案中，每個基于身份的可驗證加密簽名的產(chǎn)生至少需要使用三個對運算。然而，在基于身份和對的簽名體制中，對運算是最為耗時的。因此，在一個ID-VESS中，應(yīng)盡量少地使用對運算。辛向軍等人通過構(gòu)造和利用雙簽名密鑰，提出了一種新的ID-VESS[22]。該方案具有最短的簽名和最少的對運算的次數(shù)，因此，與同類方案相比，具有較高的計算效率。

然而，以上的所有ID-VESS（參考文獻[19]除外，參考文獻[19]并不是可證明安全的）都是在ROM下可證明安全的，并且只有參考文獻[22]中給出了強不可偽造性的證明，但其也僅僅局限于ROM之下。另外，類似于基于公鑰證書的VESS，目前的所有ID-VESS也都忽略了交換協(xié)議中用戶隱私保護的問題，而僅僅考慮的是交換的公平和安全。

為了指導(dǎo)以后的研究，筆者總結(jié)了以上目前可驗證加密簽名體制的研究狀況，見表1。表1中SM指標(biāo)準(zhǔn)模式（standard model），且在效率分析中忽略了預(yù)運算。

表1 可驗證加密簽名體制的研究現(xiàn)狀

由表1中可以看出，參考文獻[1，3]的方案需要零知識證明，因此其缺乏實用性，故在表中對其不予以考慮。同樣，參考文獻[18]不能抵抗偽造攻擊，參考文獻[19]不是可證明安全的，因此也忽略了它們的比較。在基于證書的VESS體制中，參考文獻[5，7]的計算效率較好，但參考文獻[5]的簽名為確定性簽名，同時它們都是在ROM下是可證明安全的；在SM模型下可證明安全的方案如參考文獻[10]也有較好的計算效率。在基于身份的VESS中，參考文獻[22]的方案有較好的計算效率，但其是基于ROM模型的。目前，并無標(biāo)準(zhǔn)模型下可證明安全的基于身份的VESS體制。因此，研究標(biāo)準(zhǔn)模型下可證明安全的且具有基于身份密碼系統(tǒng)的優(yōu)點的VESS體制也是目前急需解決的一個問題。

另外，一個重要的問題是，以上所有方案的強不可偽造性并未得到證明，并且所有的方案都不具有隱私保護性能，這使得它們在電子商務(wù)中的應(yīng)用受到限制。因此，建立標(biāo)準(zhǔn)模型下具有強不可偽造性、可證明安全的、具有隱私保護可選項、高效的VESS體制是一個亟待解決的、具有挑戰(zhàn)性的問題。

3 VESS的研究中需要解決的一些問題和未來的研究趨勢

（1）尋求安全、高效的VESS體制

首先，可將已有的VESS分為兩類：基于身份的VESS和基于公鑰證書的VESS。多數(shù)VESS都是建立在雙線性對（bilinear pairings，BP）的基礎(chǔ)之上。需要注意的是，在基于BP的密碼體制中，同其他運算相比，對運算是最為耗時的，對運算的次數(shù)直接決定著VESS方案的效率。然而，在基于身份的VESS中，已有的方案都至少需要兩個對運算。

2001年，Boneh和Franklin利用雙線性對構(gòu)造出具有實用性的基于身份的密碼體制。目前，幾乎所有的基于身份的VESS都是在雙線性對的基礎(chǔ)上構(gòu)建的。然而，在基于對的密碼體制中，同其他運算相比，對運算是最為耗時的。已有的基于身份的VESS體制至少需要兩個對運算。另外，目前已有的基于身份的VESS體制都僅僅是在ROM下可證明安全的。然而ROM下可證明安全的簽名體制在實踐中卻未必安全。根據(jù)我們的研究結(jié)果可知，已有的基于身份的VESS體制的安全性在標(biāo)準(zhǔn)模型下很難得到證明，原因是基于身份的VESS體制中VESS的生成算法中需要生成一個會話密鑰或隨機數(shù)，而這個會話密鑰或隨機數(shù)一般都放在可驗證加密簽名所含的一個有理多項式的分母上，這就使得利用傳統(tǒng)的方法在標(biāo)準(zhǔn)模型下很難證明這些方案的安全性。在基于身份的VESS簽名體制的簽名生成算法中放棄使用隨機數(shù)又會導(dǎo)致簽名體制成為確定性簽名體制，從而喪失了簽名的新鮮性與靈活性。因此，如何構(gòu)造標(biāo)準(zhǔn)模型下的可證明安全的、基于身份的VESS是一個亟待解決的一個問題。這個問題的解決將為實現(xiàn)電子商務(wù)中安全、高效、基于身份的公平交換協(xié)議提供理論依據(jù)和技術(shù)保障。

對于基于公鑰證書的VESS體制，已有一些效率較高的在ROM下可證明的安全性VESS方案 （如辛向軍等人在參考文獻[7]中提出的方案）。然而，ROM僅是對簽名方案安全性的一種基本考驗，ROM下可證明安全的VESS簽名方案仍然需要在實踐中得到進一步的驗證。同時，也存在一些在標(biāo)準(zhǔn)模型下基于公鑰證書的可證明安全的VESS方案。然而，不管是什么類型的VESS體制，所有方案的強不可偽造性（即不允許敵手或偽造者能夠?qū)ν幌卧斐霾煌暮灻┎⑽吹玫阶C明，這就影響了它們在電子商務(wù)中的應(yīng)用（比如，參考文獻[10]給出標(biāo)準(zhǔn)模型下的VESS方案，然而，在該方案中，攻擊者仍然可對同一消息偽造出不同的簽名，這使得這種方案在實踐中并不實用，因為在公平交換協(xié)議中同一用戶可能在不同的時間和地點交換相同類型的物品或電子合同）。

事實上，VESS體制不同于普通的簽名體制，其有自身的特殊性質(zhì)，并主要用于電子商務(wù)的公平交換協(xié)議中。公平交換協(xié)議允許同一用戶在不同時間和不同地點交換同種類型的物品。因此，這就要求VESS體制必須能夠抵抗對同一消息偽造出不同簽名的攻擊，即要求VESS體制必須具有強不可偽造性。然而，目前還未有標(biāo)準(zhǔn)模型下VESS強不可偽造性的相關(guān)理論 （如游戲Game的定義和構(gòu)造），更不存在標(biāo)準(zhǔn)模型下可證明強不可偽造性的VESS體制。因此，目前的密碼學(xué)研究將標(biāo)準(zhǔn)模型下具有強不可偽造性的VESS的相關(guān)理論及其可證明安全性作為VESS的未來重點研究內(nèi)容。

（2）在VESS體制的構(gòu)造和應(yīng)用中，應(yīng)注意用戶的隱私保護問題

電子商務(wù)中的隱私保護是普遍受到關(guān)注的一個問題，人們?nèi)找嬲J(rèn)識到在電子商務(wù)中保護自己隱私權(quán)的重要性。VESS體制主要用于公平交換協(xié)議。為保護一些商業(yè)、敏感或私人信息，許多情況下公平協(xié)議中物品交換方不希望交換的物品落入任何第三方，甚至不希望任何第三方知道交換的內(nèi)容（如電子合同的內(nèi)容、涉及到一些個人物品或商業(yè)合同）。然而，目前存在的VESS中，仲裁者都能由VESS獲得用戶的signature，這無疑會侵犯用戶的隱私。另外，在目前的VESS中，待簽名的消息m（如電子合同）的內(nèi)容對任何人都可以驗證，這可能會對用戶造成巨大的損失。也就是說，在一些環(huán)境下，用戶只有希望交換者之間知道交換物品的內(nèi)容。但是，目前的VESS僅僅考慮的是交換的公平性和安全性，而忽略了這些隱私保護。因此，對隱私保護的日益重視也使得探索具有隱私保護功能的VESS體制成為一個重要的研究課題。

據(jù)我們研究，為使得VESS體制(包括基于身份的VESS體制和基于公鑰證書的VESS體制)具有隱私保護功能，就需要利用仲裁者和用戶的公鑰生成一個新的共享公鑰，并利用這個新的公鑰對用戶的數(shù)字簽名進行加密而產(chǎn)生用戶的VESS簽名，其結(jié)果必然是：只有仲裁者用自己的私鑰解密VESS后得到S并將S發(fā)給用戶，用戶用自己的私鑰再次S解密后才能得到交換的簽名。單獨的第三方仲裁者無法獲得VESS中所包含的簽名，而只能協(xié)助用戶使用戶得到VESS中包含的簽名。更進一步，若使得第三方或其他人不知用戶交換的簽名所含消息（如簽名的電子合同、敏感商業(yè)信息）的內(nèi)容，還必須在用戶之間傳遞一個共享的秘密鑰，用其對簽名的信息進行加密。因此，如何利用仲裁者和用戶的公鑰生成一個新的共享公鑰?如何利用這個共享公鑰對用戶的簽名進行加密而產(chǎn)生VESS簽名?如何在用戶之間傳遞一個共享的秘密鑰用以加密簽名的消息?如何證明這種VESS體制的安全性?這都是具有隱私保護功能的VESS體制的構(gòu)造及安全性證明中需要解決的關(guān)鍵問題。

（3）建立安全、高效并具有隱私保護可選項的優(yōu)化公平交換協(xié)議

在目前存在的公平交換協(xié)議中的類似于對VESS的研究，研究者普遍關(guān)注的是安全和高效，而忽略了隱私保護。隨著人們對隱私保護的日益重視，利用VESS建立安全、高效并具有隱私保護可選項的優(yōu)化公平交換協(xié)議也將成為一個重要的研究內(nèi)容。

1 Asokan N,Shoup V,Waidner M.Optimistic fair exchange of signature.In:EUROCRYPT’98,Berlin:Springer-Verlag,1998

2 周永斌，張振峰，卿斯?jié)h等.基于RSA簽名的優(yōu)化公平交換協(xié)議.軟件學(xué)報，2004，15（4）：1049～1055

3 Ateniese G.Verifiableencryptionofdigitalsignaturesand applications.ACMTransactionsonInformationandSystem Security,2004,7(1):1～20

4 Boneh D,Gentry C,Lynn B,et al.Aggregate and verifiably encrypted signatures from bilinear maps.In:EURCRYFF’03,Berlin:Springer-Verlag,2003

5 Zhang F,Naini R S,Susilo W.Eficient verifiably encrypted signature and partially blind signature from bilinear pairings.In:INDOCRYPT 2003,Berlin:Springer-Verlag,2003

6 辛向軍，李清波.多個提取者的可驗證的加密的簽名方案.鄭州輕工業(yè)學(xué)院學(xué)報，2008，23（6）：84～86

7 辛向軍，李剛，董慶寬等.一個高效的隨機化的可驗證加密簽名方案.電子學(xué)報，2008（7）：1378～1382

8 CanettiR,GoldreichO,HaleviS.Therandomoracle methodology,revised.In:Prodeedings of the 30th Annual ACM Syposium on Theory of Computing,New York:ACM,1998

9 Dan Boneh,Ilya Mironov,Victor Shoup.A secure signature scheme from bilinear maps.M Joye(Ed):CT-RSA 2003,Berlin:Springer-Verlag,LNCS 2612,2003

10 楊浩淼，孫世新，徐繼友.一種無隨機預(yù)言機的高效可驗證加密簽名方案.軟件學(xué)報，2009，20（4）：1070～1076

11 Gorantla C M,Saxena A.Verifiably encrypted signature schelne without random oracles.In:ICDCIT 2005,Berlin:Springer-Verlag,2005

12 Li X,Chen K,Liu S,et al．Verifiably encrypted signatutre schelne without random oracles．Journal of Shanghai Jiaotong University(Science),2006,E-I1(2):230～235

13 LuS,OstrovskyR,SahaiA,etal.Sequentialaggregate signatures and multisignatures without random oracles.In:Proc of the EUROCRYPT 2006,Berlin:Springer-Verlag,2006

14 Ming Y,Wang Y M.An efficient verifiably encrypted signature scheme without random oracle.http://ijns.nchu.edu.tw/paper_upload?IJNS-2006-10-09-1-r.pdf,2006

15 Boneh D,Boyen X.Short signatures without random oracles.In:EUROCRYPT 2004,Berlin:Springer-Verlag,2004

16 An J H,Dodis Y,Rabin T.On the security of joint signature and encryption.In:EUROCRYPT 2002,Berlin:Springer-Verlag,2002

17 辛向軍，李發(fā)根，肖國鎮(zhèn).一種基于短簽名和離線半可信第三方的公平交換協(xié)議.西安電子科技大學(xué)學(xué)報，2007，34（1）：92～95

18 Gu C,Zhu Y.An ID-based verifiable encrypted signature schemebasedonHess’scheme.In:CISC2005,Berlin:Springer-Verlag,2005

19 Cheng X,Liu J,Wang X.Identity-based aggregate and verifiably encrypted signatures from bilinear pairing.In:ICCSA 2005,Berlin:Springer-Verlag,2005

20 顧純祥，張亞娟，祝躍飛.混合可驗證加密簽名體制及應(yīng)用.電子學(xué)報，2006，34（5）：878～882

21 張振峰.基于身份的可驗證加密簽名協(xié)議的安全性分析.計算機學(xué)報，2006，29（9）：1688～1693

22 辛向軍，張宏偉.一個安全的基于身份的可驗證加密簽名方案.十四屆全國青年通信學(xué)術(shù)會議論文集，Scientific Research Publishing，USA，2009:471～475