一类具有指定验证者性质的无证书聚合签名方案

马陵勇 杨秋宏 赖佳境

摘 要：本文提出了一种无证书具有指定验证者性质的聚合签名方案，并对方案的安全性进行了分析。结果表明，新方案不仅满足聚合签名的安全性，而且还满足不可传递性和指定的可验证性。

关键词：双线性对;计算Diffie-Hellman问题;聚合签名;广义指定验证者

中图分类号：TP309文献标识码：A文章编号：1003-5168（2020）19-0010-03

Abstract： In this paper， we proposed an aggregate signature scheme with no certificate and designated verifier， and analyzed the security of the scheme. The results show that the new scheme not only satisfies the security of aggregate signature， but also satisfies the non transitivity and the specified verifiability.

Keywords： bilinear paring;computational Diffie-Hellman problem;aggregate signature;universal designated verifier

无证书的公钥密码体系[1]于2003年由Riyami AI和Paterson K首次提出。在该体系中，密钥生成中心只生成和掌握用户的部分私钥，用户的完整私钥由用户自己的秘密信息和部分私钥结合生成。相对于基于身份的密码系统，无证书的公钥密码体系避免了密鑰生成中心完全掌控用户密钥所进行的不诚实欺骗[2]。同时，与基于证书的密码系统相比，无证书密码系统是利用用户的唯一身份信息（比如，身份证号码、Email地址等）直接作为用户公钥，因此，不需要对公钥进行认证，节省了因公钥认证而所付的昂贵代价。无证书密码系统的这些优点吸引了很多密码学者的关注。

Boneh在无证书密码系统中提出聚合签名的概念。在一些多重签名交易中，假如交易过程涉及[n]个用户的多重签名，则签名接收者需要对[n]个签名逐一验证有效性，其计算量和由此花费的代价可能是难以估量的;而聚合签名可以把多重签名合并成一个签名，接收者只需要验证这个合并后的签名，不需要分别验证个体签名，就可以确信每一个个体签名的合法性和有效性。这种思想备受区块链开发者们的关注，因为只需要验证合并后的聚合签名，既提高了验证效率，也节省了节点空间的占用。Gong等人[2]提出了一种无证书的聚合签名并定义了一种安全模型。关于无证书聚合签名的最新研究成果可以参考一些其他文献[3]。

对于任意第三方，传统的聚合签名方案都可以使用系统公开的参数对聚合签名进行验证，但是，这种公开验证性暴露了签名生成者的信息，某些实际应用中（如电子选举、电子商务等）需要保护签名者的信息，只有被赋予权限的用户才可以验证聚合签名，其他用户不能验证聚合签名，也就不能确信签名者的信息。而指定验证者签名方案的提出很好地解决了这个问题。

Chen等[3]在2015年提出了一类高效的无证书聚合签名方案，研究者在该方案中引入指定验证者签名方法，设计了一种新的无证书的指定验证者聚合签名方案。新方案满足正确性、强指定验证性、不可伪造性、不可传递性和高效性。

1 预备知识

1.1 定义1：双线性对

设[G1]是一个加法循环群，其阶为素数[q]，[P]是它的一个生成元;[G2]是一个乘法循环群，其阶也为[q]。若映射[e：G1×G1→G2]满足以下三个条件，则称这个映射为双线性映射，也叫双线性对。

第一，双线性：对于任意[U，V∈G1，a，b∈Z*q]，[e（aU，bV）][=e（U，V）ab]。

第二，非退化性：存在[U，V∈G1]，使得[e（U，V）≠1G2]。

第三，可计算性：对于任意的[U，V∈G1]，存在已知高效的算法来计算[e（U，V）]的值。

1.2 定义2：计算性Difiie-Hellman问题（CDHP）

给定一个阶为[q]的循环群[G]，它的一个生成元[P]以及[aP，bP∈G]（[a，b∈Z*q]且值未知），计算[abP∈G]。

1.3 定义3：计算双线性Difiie-Hellman问题（CBDHP）

对任意[a，b，c∈Z*q]，且值未知，给定[P，aP，bP，cP]计算[e（P，P）abc]的值。

2 具有广义验证者性质的无证书聚合签名方案

2.1 方案描述

Ming等把无证书广义验证者聚合签名定义为三类算法：第一类是无证书聚合签名算法;第二类是指定验证者签名算法;第三类是指定验证者验证算法。本文把聚合签名算法与指定验证者签名算法统一为指定验证者聚合签名生成算法，同时，把聚合签名算法与指定验证者验证算法也统一为指定验证者聚合签名验证算法，研究者提出的方案由此简化为6个算法，具体描述如下。

第一，建立初始系统。输入安全参数[k]，该算法输出系统全局参数空间[param=（G1，G2，e，q，P，P0，H1，][H2，H3，H4，H5，HDV）]，其中[（G1，+）]和[（G2，·?）]是上述定义1中的循环群，阶均为素数[q≥2k]，[P]是[G1]的一个生成元，[e]为定义1中的双线性对，[H1，H2，H3：{0，1}*→G1?]，[H4，H5：0，1?→Z?q]，[HDV：0，1?→Zq?]是安全的哈希函数，密钥生成中心（Key Generation Centre，KGC）输出系统主密钥[s∈Z?q]并保密，[P0=sP]为系统公钥。

第二，部分私钥提取。由用户和KGC交互完成，用户提交自己的身份[IDi∈{0，1}?]给KGC，KGC计算[Di=sQi=sH1（IDi）]，然后把[Di]经安全方式返回给用户。

第三，公/私钥对生成。用户[IDi]随机选取[xi∈Z*p]，计算[Pi=xiP]，公钥为[Pi]，私钥为[（xi，Di）]。

第四，个体签名生成。聚合签名生成者[IDA]选取一个状态信息[Δ]，并广播给每一个参与个体，身份[IDi]的用户，执行如下计算，从而对消息[mi]（i = 1，2，…，n）进行签名。①随机选取[r∈Z*p]，计算[Ri=riPhi=H4（miΔRiIDi）]和[gi=H5（miΔRiPi）];②计算[Wi=giDi+xihiU+riV]，其中[U=H2（ΔP），V=H3（ΔP0）];③输出[σi=（Ri，Wi）]为个体签名。

第五，指定验证者聚合签名生成算法。假如聚合者为[IDA]，[IDA]收齐[n]个个体签名后，在公开状态信息[Δ]下对被指定的验证者身份[IDDV]，公钥为[PDV]的指定验证者聚合签名按如下方式进行：①计算[W=W1+W2+…+Wn]和[hDV=HDV（xAPDV）];②计算[S=e（W，hDVPDV）]。

输出给指定验证者[IDDV]的聚合签名为[σ=（R1，R2，…，Rn，S）]。

第六，指定验证者聚合签名验证算法。指定验证者[IDDV]的用户对来自于聚合者[IDA]签名[σ=（R1，R2，…，Rn，S）]的有效性进行验证。输入身份信息集[{ID1，ID2，…，IDn}]、公钥信息集[{P1，P2，…，Pn}]、消息集合[{m1，m2，…，mn}]以及聚合签名[σ=（R1，R2，…，Rn，S）]，[IDDV]的操作为：①计算[U=H2（ΔP），V=H3（ΔP0）][，hi=H4（miΔRiIDi）]，[gi=H5（miΔRiPi）]和[Qi=H1（IDi）];②计算[hDV=HDV（xDVPA）];③验证[S=[e（i=1ngiQi，P0）e（i=1nhiPi，U）e（i=1nRi，V）]xDVhDV]是否为真，若真，则接受[σ]，否则，拒绝[σ]。

2.2 安全性分析

2.2.1 方案的正确性。定理1：本文提出的新方案是正确的。

证明：指定验证者聚合签名[σ=（R1，R2，…，Rn，S）]能而且只能由被指定的身份为[IDDV]，公钥为[PDV]的用户正确验证：

[S=eW，hDVPDV=ei=1nWi，hDVPDV=ei=1ngiDi+xihiU+riV，hDVPDV=ei=1ngiDi，hDVPDVei=1nxihiU，hDVPDVei=1nriV，hDVPDV=ei=1ngiQi，P0ei=1nhiPi，Uei=1nRi，VxDVhDV]           （1）

所以，本文方案是正确的。

2.2.2 强指定验证性。根据定理1的证明过程，指定验证者的聚合签名的验证阶段需要恢复[hDV=HDV（xAPDV）]，而[hDV=HDV（xAPDV）=HDV（xAxDVP）=HDV（xDVPA）]，只有[IDDV]拥有私钥[xDV]，其他用户不能正确地恢复出[hDV=HDV（xAPDV）]，也就无法验证聚合签名的正确性;而指定验证者[IDDV]可以利用自己的私钥恢复[hDV=HDV（xAPDV）]，同时，根据验证算法，[IDDV]信任这个聚合签名[σ=（R1，R2，…，Rn，S）]是来自聚合者[IDA]，身份为[IDi（i=1，2，…，n）]的用户对消息[mi（i=1，2，…，n）]分别进行了签名，所以，本文方案满足强指定验证性。

2.2.3 不可伪造性。一般的无证书聚合签名方案的不可伪造性需要考虑一类攻击，这类伪造攻击中存在两个具有不同能力的敌手[AⅠ]和[AⅡ]，相应的有一个可以解决某种困难问题的挑战者[C]，挑战者[C]与敌手进行两类交互游戏，关于敌手[AⅠ]和[AⅡ]的定义以及挑战者[C]与之进行的交互游戏见Chen H的研究[3]。同时，基于CDH困难问题，Chen H的研究[3]也证明了其无证书聚合签名方案满足适应性选择消息和身份攻击下的存在性不可伪造。而本文方案是基于Chen H的研究[3]进行改进的，所以，本文方案满足自适应性选择消息和身份攻击下的存在性不可伪造。

无证书的指定验证者聚合签名方案除了满足上述的一类攻击安全之外，还要考虑另一种攻击类型，即对指定验证者身份的攻击。

关于第二类攻击，我们定义一类攻击者[AⅢ]，[AⅢ]所具有的攻击能力类似于前述的攻击者[AⅠ]和[AⅡ]，在不同的攻击下可以分别充当外部敌手和内部不诚实的KGC身份，指定验证者聚合签名方案如果存在敌手[AΙΙΙ]以不可忽略的概率在如下游戏1中获胜，则无证书具有指定验证者的聚合签名方案在适应性选择消息和指定身份攻击下指定验证者签名不可伪造。

游戏1：假设[C]为游戏的挑战者。[C]在游戏开始之前进行的运算和第一类攻击者下挑战者所做的运算一样产生系统参数和系统主密钥[s]，并与攻击者[AⅢ]模拟交互，而攻击者[AⅢ]在游戏过程中可以询问以下预言机。

①Hash函数询问、部分私钥提取询问、秘密值询问、用户公钥询问、公钥替换询问，这些询问与第一类攻击类型中敌手[AⅠ]与挑战者之间的游戏相同，如果[AⅢ]是不诚实的KGC，则不能做部分私钥询问和公钥替换询问。

②指定验证者聚合签名询问：[AⅢ]可以获得[M?={m1?，m2?，…，mn?}]指定验证者[IDDV?]的签名。

攻击者[AⅢ]按照上述询问得到的信息，可以输出对[M?={m1?，m2?，…，mn?}]指定验证者[IDDV?]的指定验证者聚合签名[σDV?]，[AΙΙΙ]在該游戏中获胜当且仅当以下条件满足：第一，[σDV?]是一个有效的无证书指定验证者聚合签名，可以通过合法验证;第二，[AⅢ]之前没有对[M?={m1?，m2?，…，mn?}]进行过指定验证者聚合签名询问;第三，[AⅢ]没有对指定验证者[IDDV]的私钥询问。

定理2：本文的無证书指定验证者聚合签名方案对第二类攻击者[AⅢ]满足存在性不可伪造。

证明：不妨假设敌手[AⅢ]对伪造的身份[IDDV?]，伪造的消息集合[M?={m1?，m2?，…，mn?}]所计算的指定验证者的聚合签名为[σDV?=（M?，R1?，R2?，…，Rn?，S?）]。如果该伪造能够顺利通过验证算法，两种方式敌手[AⅢ]都可以实现伪造，取得[IDDV]的私钥，或者取得对[M?={m1?，m2?，…，mn?}]伪造的聚合签名。

第一种方式伪造是不可能的，哈希函数[HDV]的输入只有两个值，即[xAPDV]和[xDVPA]，由这两个输入值获取[xDV]相当于计算CDH困难问题。同时，由于哈希函数本身的单向性，由哈希值获得哈希输入也是不可能的。

第二种方式的伪造同样不可行，敌手[AⅢ]要获得对[M?={m1?，m2?，…，mn?}]的伪造聚合签名，等价于[AⅢ]扮演了敌手类型[AⅠ]和[AⅡ]，这在Chen H的研究中[8]中已经被证明是不可能的。

所以，本文的方案满足对第二类攻击者[AⅢ]的存在性不可伪造。

2.2.4 不可传递性。所谓不可传递性是指指定验证者可以模仿聚合生成者生成一个合法的指定聚合签名，其他第三方不能冒充，以防止指定验证者的抵赖行为。

定理3：方案满足指定验证者签名的不可传递性。

证明：在签名[σ=（R1，R2，…，Rn，S）]中，[S=e（W，hDVPDV）]，而[hDV=HDV（xAPDV）=HDV（xDVPA）]，由于指定验证者可以恢复[hDV]，所以其可以模仿聚合生成者[IDA]生成一个签名的副本[σ′]，而且可以顺利通过验证者算法。

3 方案的效率分析

Chen H的研究[3]比较了几类经典无证书聚合签名方案的效率，证实了其提出的无证书聚合签名方案具有高效性，本方案是对Chen H提出的方案[3]的改进，在指定验证者签名和指定验证者验证时均没有增加计算复杂性，所以新方案依然具有高效性。

4 结语

基于Chen H的研究[3]提出了一种无证书的具有指定验证者性质的聚合签名方案。新方案满足正确性、强指定验证性、不可为造性、不可传递性和高效性。设计安全高效的无证书指定验证者聚合签名方案仍然是需要进一步研究的课题。

参考文献：

[1] Al-Riyami S S，Paterson K G . Certificateless Public Key Cryptography[C]// International Conference on the Theory and Application of Cryptology and Information Security. Springer， Berlin， Heidelberg，2003.

[2] Gong Z ， Long Y ， Hong X ， et al. Two Certificateless Aggregate Signatures From Bilinear Maps[C]// Eighth ACIS International Conference on Software Engineering，Artificial Intelligence， Networking， and Parallel/Distributed Computing （SNPD 2007）. IEEE， 2007.

[3]Chen H， Wei SM， Zhu CJ， Yang Y. S ecure certificateless aggregate signature scheme[J].Ruan Jian Xue Bao/Journal of Software，2015（5）：1173-1180.