可验证加密签名方案的研究及进展*

关宏波，辛向军，邱学邵

（郑州轻工业学院信息与计算科学系 郑州450002）

1 引言

在公钥密码学中，数字签名是一个重要的研究内容。由于数字签名可提供消息认证性、完整性和不可否认性业务，因此其在电子商务、电子政务、军事等领域有着重要的应用。可验证的加密签名方案 （verifiably encrypted signature scheme，VESS）是普通签名的一种扩展，其有三个参与方：签名者、验证者和仲裁者。在VESS方案中，用户Alice利用自己的私钥对消息m产生签名signature，并同时利用仲裁者的公钥对签名进行加密，从而产生一个关于消息m的VESS签名vess。验证者Bob可以验证vess确实是signature的密文，但Bob不能由vess推出或获得signature的任何信息。若Alice不想或者不能（比如，Alice和Bob的通信中断）将signature交付于Bob，Bob可将vess发送给仲裁者，并由仲裁者解密vess而获得signature，从而仲裁者可将signature发送给Bob。VESS的这种特点使得多个签名者或用户之间可以安全地、公平地交换自己的签名。这与电子商务中的要求：公平、安全、高效相一致，故其主要用于构建优化的公平交换协议[1，2]。

因此，为建立电子商务中公平、安全、高效、优化的交换协议（如，电子合同的签署与交换，在线购物），很有必要研究VESS的基本理论，建立安全、高效的VESS，为电子商务中交换协议的公平、安全、高效应用提供理论依据和技术保障。因此，对VESS的研究具有重要的理论意义和实用价值。

2 国内外研究现状及分析

1976年，Diffie和Hellman提出了公钥密码体制。目前，公钥的分配主要有两种方法。第一种方法为基于公钥证书的分配方法。在这种方法中，证书管理机构（certificate authority，CA）给每个用户签发一个类似于数字签名的公钥证书，其中的数据项有与该用户的私钥相匹配的公钥及用户的身份和时戳等。用户之间通过交换公钥证书来相互交换自己的公钥而无须与CA联系。另一种方法为基于身份的分配方法。1984年，Shamir提出一种基于身份的加密思想，这也给出了基于身份的公钥分配方法。这种方法将用户的身份用作公钥，而用户的私钥由可信的密钥生成器（private key generator，PKG）根据用户的身份产生，并由用户秘密保存。因此，为便于分析，将VESS分成两类：基于公钥证书的VESS和基于身份的VESS，以此来讨论VESS的研究现状。

2.1 基于公钥证书的VESS

早期的VESS的方案[1]效率并不高，因为其需要零知识证明协议来验证一个VESS的有效性。Ateniese的方案[3]并未有较好的改观，因为其仍然是基于零知识证明的。参考文献[4]给出了基于对的随机化的VESS方案，然而，其需要3个对运算。需要注意的是，在基于对的VESS方案中，对运算是最为耗时的，故应在此类方案中尽量减少对运算的次数。Zhang等人[5]给出一个只有一个对运算的且签名长度最短的VESS签名方案，然而，这种VESS签名方案是确定性的签名方案（即对同一消息进行重复签名，每次总是产生相同的签名），其缺乏签名的灵活性和新鲜性。为防止仲裁者与用户的合谋，辛向军等给出了一种多个仲裁者分割仲裁权的VESS体制[6]，该技术可为公平交换协议提供更好的安全性，其同样只有一个对运算并具有较短的签名。然而，该方案也局限于确定性签名。为此，辛向军等人又给出一个高效的随机化的可验证加密签名方案[7]，其在保持签名随机性和一个对运算的前提下保证了较短的签名。

以上所有的VESS的安全性都是在随机预言机（random oracle model，ROM）下可证明安全的。需要注意的是，Canetti和Boneh等人的研究[8，9]说明ROM下的安全性仅是密码体制安全性的一种基本度量，这意味着ROM下可证明安全的VESS体制的安全性需要在实际应用环境中进一步检验。因此，为进一步提高VESS的安全性，Gorantla等先后提出标准模型下可证明安全的VESS签名体制[10～14]，但其中多数方案至少需要两个对运算，而参考文献[11，12]中的方案比较高效，因为它们仅需一个对运算。

利用Boneh的方法[15]在标准模型下构建VESS签名为建立更为安全的VESS体制提供了一种有益的思路。然而，VESS体制是普通签名体制的一种扩展，其有自身的特点，并主要用于电子商务中建立公平交换协议。首先，公平交换协议允许用户在不同时间和不同地点交换相同类型的物品（签名），这就需要标准模型下的VESS签名体制应具有强不可伪造性[9，15～22]，即不允许敌手或伪造者能够对同一消息伪造不同的签名。然而，目前所有的标准模型下的VESS签名体制的强不可伪造性都没有得到证明，这就意味着这些方案中敌手可能会对相同类型的物品伪造不同的VESS签名。例如，在参考文献[12]中，假定敌手知道关于消息m的两个VESS签名(r1，K1)和(r2，K2)，敌手可通过如下的步骤对消息m伪造一个新的签名(r*，K*)：

第二步：敌手随机选取r*∈Zp*并计算K*=u-r*v。

易验证(r*，K*)满足参考文献[12]的VESS验证方程。这样，敌手伪造消息m的一个新的签名(r*，K*)成功。因此，为使得VESS能够满足电子商务中公平交换协议的需要，需要标准模型下的VESS签名体制应具有强不可伪造性。

另外，以上所有的方案仅仅考虑了公平和安全的需要，而没有考虑到用户的隐私保护问题。特别是在一些涉及隐私及商业机密的签名中，用户不希望作为仲裁者的第三方也获得用户所交换的物品或签名，甚至不希望第三方知道用户之间交换的内容。为实现用户的隐私保护，辛向军等利用短签名给出一种具有离线半可信第三方的公平交换协议[17]，方案中离线第三方不必完全可信，因其在解决纠纷的同时并不能获得交换双方的签名。这种协议使得作为仲裁者的第三方无法获得用户所交换的物品或签名，从而能够在一定程度上保护用户的隐私。然而，这种协议中并未使用VESS体制，因此其效率并不优于基于VESS的公平交换协议。因此，建立安全、高效并具有隐私保护可选项的优化公平交换协议仍然是一个公开问题。

2.2 基于身份的VESS

基于身份的密码系统使得用户的身份标识 （如名字、IP地址、E-mail等）可用作用户的公钥，从而避免了公钥证书的生成、签发、存储、维护、使用、更新、撤销这些复杂的过程，从而大大节约了系统的成本和代价，并极大地方便了用户。为使VESS具有基于身份的密码系统的优点，Gu和Cheng等分别提出三种基于身份的可验证加密签名方案(ID-VESS)[18～20]。然而，参考文献[18]的方案并不安全，张在参考文献[21]中给出对参考文献[18]中的方案的两种攻击：伪造VESS攻击和合谋攻击。这说明参考文献[18]的方案不满足不可伪造性。另外，Cheng等人给出的ID-VESS[19]并不是可证明安全的，因此，这直接影响到参考文献[18，19]中方案在实践中的应用。需要注意的是，在参考文献[18～20]的所有方案中，每个基于身份的可验证加密签名的产生至少需要使用三个对运算。然而，在基于身份和对的签名体制中，对运算是最为耗时的。因此，在一个ID-VESS中，应尽量少地使用对运算。辛向军等人通过构造和利用双签名密钥，提出了一种新的ID-VESS[22]。该方案具有最短的签名和最少的对运算的次数，因此，与同类方案相比，具有较高的计算效率。

然而，以上的所有ID-VESS（参考文献[19]除外，参考文献[19]并不是可证明安全的）都是在ROM下可证明安全的，并且只有参考文献[22]中给出了强不可伪造性的证明，但其也仅仅局限于ROM之下。另外，类似于基于公钥证书的VESS，目前的所有ID-VESS也都忽略了交换协议中用户隐私保护的问题，而仅仅考虑的是交换的公平和安全。

为了指导以后的研究，笔者总结了以上目前可验证加密签名体制的研究状况，见表1。表1中SM指标准模式（standard model），且在效率分析中忽略了预运算。

表1 可验证加密签名体制的研究现状

由表1中可以看出，参考文献[1，3]的方案需要零知识证明，因此其缺乏实用性，故在表中对其不予以考虑。同样，参考文献[18]不能抵抗伪造攻击，参考文献[19]不是可证明安全的，因此也忽略了它们的比较。在基于证书的VESS体制中，参考文献[5，7]的计算效率较好，但参考文献[5]的签名为确定性签名，同时它们都是在ROM下是可证明安全的；在SM模型下可证明安全的方案如参考文献[10]也有较好的计算效率。在基于身份的VESS中，参考文献[22]的方案有较好的计算效率，但其是基于ROM模型的。目前，并无标准模型下可证明安全的基于身份的VESS体制。因此，研究标准模型下可证明安全的且具有基于身份密码系统的优点的VESS体制也是目前急需解决的一个问题。

另外，一个重要的问题是，以上所有方案的强不可伪造性并未得到证明，并且所有的方案都不具有隐私保护性能，这使得它们在电子商务中的应用受到限制。因此，建立标准模型下具有强不可伪造性、可证明安全的、具有隐私保护可选项、高效的VESS体制是一个亟待解决的、具有挑战性的问题。

3 VESS的研究中需要解决的一些问题和未来的研究趋势

（1）寻求安全、高效的VESS体制

首先，可将已有的VESS分为两类：基于身份的VESS和基于公钥证书的VESS。多数VESS都是建立在双线性对（bilinear pairings，BP）的基础之上。需要注意的是，在基于BP的密码体制中，同其他运算相比，对运算是最为耗时的，对运算的次数直接决定着VESS方案的效率。然而，在基于身份的VESS中，已有的方案都至少需要两个对运算。

2001年，Boneh和Franklin利用双线性对构造出具有实用性的基于身份的密码体制。目前，几乎所有的基于身份的VESS都是在双线性对的基础上构建的。然而，在基于对的密码体制中，同其他运算相比，对运算是最为耗时的。已有的基于身份的VESS体制至少需要两个对运算。另外，目前已有的基于身份的VESS体制都仅仅是在ROM下可证明安全的。然而ROM下可证明安全的签名体制在实践中却未必安全。根据我们的研究结果可知，已有的基于身份的VESS体制的安全性在标准模型下很难得到证明，原因是基于身份的VESS体制中VESS的生成算法中需要生成一个会话密钥或随机数，而这个会话密钥或随机数一般都放在可验证加密签名所含的一个有理多项式的分母上，这就使得利用传统的方法在标准模型下很难证明这些方案的安全性。在基于身份的VESS签名体制的签名生成算法中放弃使用随机数又会导致签名体制成为确定性签名体制，从而丧失了签名的新鲜性与灵活性。因此，如何构造标准模型下的可证明安全的、基于身份的VESS是一个亟待解决的一个问题。这个问题的解决将为实现电子商务中安全、高效、基于身份的公平交换协议提供理论依据和技术保障。

对于基于公钥证书的VESS体制，已有一些效率较高的在ROM下可证明的安全性VESS方案 （如辛向军等人在参考文献[7]中提出的方案）。然而，ROM仅是对签名方案安全性的一种基本考验，ROM下可证明安全的VESS签名方案仍然需要在实践中得到进一步的验证。同时，也存在一些在标准模型下基于公钥证书的可证明安全的VESS方案。然而，不管是什么类型的VESS体制，所有方案的强不可伪造性（即不允许敌手或伪造者能够对同一消息伪造出不同的签名）并未得到证明，这就影响了它们在电子商务中的应用（比如，参考文献[10]给出标准模型下的VESS方案，然而，在该方案中，攻击者仍然可对同一消息伪造出不同的签名，这使得这种方案在实践中并不实用，因为在公平交换协议中同一用户可能在不同的时间和地点交换相同类型的物品或电子合同）。

事实上，VESS体制不同于普通的签名体制，其有自身的特殊性质，并主要用于电子商务的公平交换协议中。公平交换协议允许同一用户在不同时间和不同地点交换同种类型的物品。因此，这就要求VESS体制必须能够抵抗对同一消息伪造出不同签名的攻击，即要求VESS体制必须具有强不可伪造性。然而，目前还未有标准模型下VESS强不可伪造性的相关理论 （如游戏Game的定义和构造），更不存在标准模型下可证明强不可伪造性的VESS体制。因此，目前的密码学研究将标准模型下具有强不可伪造性的VESS的相关理论及其可证明安全性作为VESS的未来重点研究内容。

（2）在VESS体制的构造和应用中，应注意用户的隐私保护问题

电子商务中的隐私保护是普遍受到关注的一个问题，人们日益认识到在电子商务中保护自己隐私权的重要性。VESS体制主要用于公平交换协议。为保护一些商业、敏感或私人信息，许多情况下公平协议中物品交换方不希望交换的物品落入任何第三方，甚至不希望任何第三方知道交换的内容（如电子合同的内容、涉及到一些个人物品或商业合同）。然而，目前存在的VESS中，仲裁者都能由VESS获得用户的signature，这无疑会侵犯用户的隐私。另外，在目前的VESS中，待签名的消息m（如电子合同）的内容对任何人都可以验证，这可能会对用户造成巨大的损失。也就是说，在一些环境下，用户只有希望交换者之间知道交换物品的内容。但是，目前的VESS仅仅考虑的是交换的公平性和安全性，而忽略了这些隐私保护。因此，对隐私保护的日益重视也使得探索具有隐私保护功能的VESS体制成为一个重要的研究课题。

据我们研究，为使得VESS体制(包括基于身份的VESS体制和基于公钥证书的VESS体制)具有隐私保护功能，就需要利用仲裁者和用户的公钥生成一个新的共享公钥，并利用这个新的公钥对用户的数字签名进行加密而产生用户的VESS签名，其结果必然是：只有仲裁者用自己的私钥解密VESS后得到S并将S发给用户，用户用自己的私钥再次S解密后才能得到交换的签名。单独的第三方仲裁者无法获得VESS中所包含的签名，而只能协助用户使用户得到VESS中包含的签名。更进一步，若使得第三方或其他人不知用户交换的签名所含消息（如签名的电子合同、敏感商业信息）的内容，还必须在用户之间传递一个共享的秘密钥，用其对签名的信息进行加密。因此，如何利用仲裁者和用户的公钥生成一个新的共享公钥?如何利用这个共享公钥对用户的签名进行加密而产生VESS签名?如何在用户之间传递一个共享的秘密钥用以加密签名的消息?如何证明这种VESS体制的安全性?这都是具有隐私保护功能的VESS体制的构造及安全性证明中需要解决的关键问题。

（3）建立安全、高效并具有隐私保护可选项的优化公平交换协议

在目前存在的公平交换协议中的类似于对VESS的研究，研究者普遍关注的是安全和高效，而忽略了隐私保护。随着人们对隐私保护的日益重视，利用VESS建立安全、高效并具有隐私保护可选项的优化公平交换协议也将成为一个重要的研究内容。

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

2 周永斌，张振峰，卿斯汉等.基于RSA签名的优化公平交换协议.软件学报，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 辛向军，李清波.多个提取者的可验证的加密的签名方案.郑州轻工业学院学报，2008，23（6）：84～86

7 辛向军，李刚，董庆宽等.一个高效的随机化的可验证加密签名方案.电子学报，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 杨浩淼，孙世新，徐继友.一种无随机预言机的高效可验证加密签名方案.软件学报，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 辛向军，李发根，肖国镇.一种基于短签名和离线半可信第三方的公平交换协议.西安电子科技大学学报，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 顾纯祥，张亚娟，祝跃飞.混合可验证加密签名体制及应用.电子学报，2006，34（5）：878～882

21 张振峰.基于身份的可验证加密签名协议的安全性分析.计算机学报，2006，29（9）：1688～1693

22 辛向军，张宏伟.一个安全的基于身份的可验证加密签名方案.十四届全国青年通信学术会议论文集，Scientific Research Publishing，USA，2009:471～475