密钥隔离的无证书聚合签名

寻甜甜,于　佳,2,杨光洋,江秀秀,郝　蓉

(1.青岛大学信息工程学院，山东青岛 266071；2.山东省科学院山东省计算机网络重点实验室，山东济南 250014)



密钥隔离的无证书聚合签名

寻甜甜1,于佳1,2,杨光洋1,江秀秀1,郝蓉1

(1.青岛大学信息工程学院，山东青岛 266071；2.山东省科学院山东省计算机网络重点实验室，山东济南 250014)

无证书的聚合签名的提出是为了解决密钥托管问题以及复杂的证书管理问题.然而在无证书的聚合签名中，一旦某一签名者的密钥发生泄漏，所有由此签名者参与生成的聚合签名都将不再安全.为了减小无证书的聚合签名中密钥泄漏带来的危害，本文首次将密钥隔离安全机制嵌入到无证书的聚合签名中，提出了密钥隔离的无证书聚合签名的概念和安全模型，并给出了一个实用的方案，通过与协助器的交互，实现了对签名者密钥的定时更新.同时证明了方案在随机预言机模型下是安全的，即，满足密钥隔离安全、强密钥隔离安全和安全密钥更新的性质.

聚合签名；密钥隔离；无证书签名；密钥托管；双线性配对

1　引言

2003年，Boneh等人[1]提出了聚合签名的概念，并给出了第一个基于双线性配对的聚合签名方案.在此方案中，n个签名者对n个不同消息的签名可以被压缩成单个签名，而验证方只需对合成的单个签名进行一次验证就能够判断签名是否来自这些签名者.为了解决聚合签名中复杂的证书管理问题，Gentry等[2]提出了基于身份的聚合签名方案，在该方案中，签名者的身份可以替代它的公钥，验证者仅使用签名者的身份就可验证签名是否有效，从而简化了证书管理的过程.由于聚合后的签名和单个签名的长度是相同的，因此该方案验证时所需总的信息量较少，可应用于无线网络等领域.Ah Shim等[3]提出了另外一个基于身份的聚合签名方案，该方案具有更高的效率.

然而，在基于身份的聚合签名方案中，存在密钥托管问题，即私钥生成中心(PKG)知道每个用户的私钥.用户私钥是由PKG跟据用户的身份生成的，也就是说不诚实的PKG可以伪造任何用户的签名，因此密钥托管问题严重威胁到基于身份的密码系统的安全.为了解决这个问题，Al-Riyami和Paterson[4]最先提出了无证书的公钥密码体制，密钥生成中心(KGC)生成用户的部分私钥，用户使用部分私钥和自己选取的秘密值独立生成自己的公私钥，因此，KGC无法伪造用户的签名，从而解决了基于身份的密码系统中的密钥托管问题.由于既能解决密钥托管问题，又能简化公钥证书的管理，无证书密码体制近些年来受到密码学界的广泛关注.Zheng等[5]首次提出无证书聚合签名方案，安全性只在一个较弱的模型下得到了证明，随后文献[6]强化了无证书聚合签名的安全性模型，并给出了高效的无证书签名方案.Xiong等[7]提出了具有常数个配对的无证书聚合签名方案，并称方案在随机预言机模型下是可证安全的.文献[8～15]给出了一些其他的无证书签名方案.

然而，在无证书聚合签名中密钥泄露问题是亟待解决的问题，如果一个签名者密钥发生泄漏，由此签名者参与的所有聚合签名将不再安全.Dodis等[16]提出的密钥隔离机制，可以定时对私钥进行更新并保证用户公钥不变.某一时间段的私钥泄露不会影响其他时间段系统的安全性，有效地降低了密钥泄露带来的危害.万中美提出的标准模型下的无证书密钥隔离签名[17]方案和无证书的强密钥隔离签名[18]方案，减小了无证书签名中的密钥泄漏问题.

密钥隔离的无证书聚合签名方案目前尚未被提出，一个重要的原因是密钥隔离的无证书聚合签名的构造需要满足：聚合签名的长度应与单个签名的长度相同.这需要构造的无证书签名方案同时具有可聚合性和密钥隔离性.本文的主要贡献是解决了上述问题.首先，给出了密钥隔离的无证书聚合签名的概念；然后，给出了其具体的安全性模型；最后，设计了一个高效的密钥隔离的无证书聚合签名方案，并给出了具体的安全性证明和相关效率分析.在提出的方案中，公钥始终不变，签名者通过与协助器的交互，定时对其私钥进行更新.某一签名者密钥即使发生了泄漏，不会影响到其他未发生密钥泄漏时间段有此签名者参与的聚合签名的安全性，从而减少了密钥泄漏带来的危害.本方案生成的聚合签名的长度和单个签名的长度相同，与签名者人数无关.验证时只需要常数个双线性配对，效率较高.本文提出的方案在给出的安全模型下是可证安全的，满足密钥隔离安全，强密钥隔离安全和安全密钥更新的性质.

2　预备知识

2.1双线性映射

2.2CDH困难问题假设

定义2(CDH假设)若对于敌手A，在多项式时间t内，其攻破群G上的CDH问题的概率均小于ε，则称群G上的(t,ε)-CDH假设成立.

3　密钥隔离的无证书聚合签名的定义和安全模型

3.1密钥隔离的无证书聚合签名的定义

定义3一个密钥隔离的无证书聚合签名方案包括以下8个算法：

(1)Setup(k，N)：系统建立算法.输入给定安全参数k和总时间段数N，输出KGC的主密钥s和公开参数param.

(2)PartialKey(s，IDi，param)：部分私钥生成算法.输入KGC的主密钥s，签名者身份IDi(1≤i≤n)和公开参数param，输出签名者IDi的部分私钥PSKi,j.

(3)KeyGen(PSKi,j，IDi，param)：密钥生成算法.输入给定签名者身份IDi和公开参数param，输出签名者IDi的初始私钥USKi,j,0，公钥UPKi，生成协助器的私钥HSK，公钥HPK.

(4)UpdateM(t，IDi，HSK，param)：更新消息生成算法.输入签名者身份IDi，时间段t，协助器私钥HSK和公开参数param，输出t时间段的更新消息UKi,j,t.

(5)UpdateU(t，IDi，USKi,j,t-1，UKi,j,t，param)，签名者临时密钥更新算法.输入签名者身份IDi，时间段t时的更新消息UKi,j,t，t-1时间段签名者的临时私钥USKi,j,t-1和公开参数param，输出签名者IDi在t时间段的临时私钥USKi,j,t.

(6)Sign(t，IDi，mi，USKi,j,t，param)：签名算法.输入时间段t，签名者身份IDi，消息mi，签名者IDi在t时间段的临时私钥USKi,j,t和公开参数param，输出签名者IDi在t时间段对消息mi的签名(t，σi).

3.2密钥隔离的无证书聚合签名的安全模型

密钥隔离的无证书聚合签名应该抵御两种类型的攻击者.第Ⅰ类攻击者可以替换其选择用户的公钥(身份)，可以得到任意签名者的部分私钥，某些时间段的临时私钥，但是不能得到KGC的主密钥.第Ⅱ类攻击者可以得到KGC的主密钥，因此它可以计算用户的部分私钥，也可以得到用户的某些时间段的临时私钥，但是不能替换用户公钥.

定义4如果没有攻击者A在多项式时间内以不可忽略的概率赢得以下游戏，我们称方案是密钥隔离安全的.

系统建立阶段挑战者C运行setup生成公共参数，并给定用户ID1,ID2,…,IDk，将ID2,…,IDk的私钥和公共参数发送给攻击者A.如果是第I类攻击者，C自己保存主密钥，如果是第Ⅱ类攻击者，C将主密钥发送给A.

查询阶段敌手A自适应的向挑战者进行以下查询.

(1)部分私钥提取查询：当A查询用户IDi的部分私钥时，C运行Setup，PartialKey算法生成部分私钥PSKi,j返回给A.(只用于第一类攻击者)

(2)公钥提取查询：当A查询用户IDi的公钥时，C运行KeyGen算法生成用户公钥UKPi返回给A.

(3)秘密值提取查询：当A查询用户IDi的秘密值时，C运行KeyGen算法生成秘密值xi返回给A.第一类攻击者查询时，当公钥已被替换则返回⊥.

(5)密钥提取查询：当A查询用户IDi的初始密钥和协助器密钥时，C运行KeyGen算法生成USKi,j,0,HPK,HSK返回给A.

(6)临时签名密钥提取查询：当A查询用户IDi的t时间段的临时签名密钥时，C运行UpdateU算法生成USKi,j,t返回给A.

(7)签名查询：当A查询t时间段用户IDi对消息mi的签名时，C运行Sign算法生成(t，σi)返回给A.

当且仅当以下条件成立时，我们说算法A赢得了这个游戏：

(2)如果是第一类攻击者，没有查询ID1的部分私钥.

(3)如果是第二类攻击者，没有查询ID1的秘密值.

(4)没有查询t*时间段ID1临时签名密钥.

定义5如果没有敌手A在多项式时间内以不可忽略的概率赢得以下游戏，我们称方案是强密钥隔离安全的.

其中系统建立阶段，部分私钥提取查询，公钥提取查询，秘密值提取查询，公钥替换查询，签名查询同定义4.

当且仅当以下条件成立时，我们说算法A赢得了这个游戏：

(2)如果是第一类攻击者，没有查询ID1的部分私钥.

(3)如果是第二类攻击者，没有查询ID1的秘密值.

定义6当用户i在时间段t将临时私钥从USKi,j,t-1更新到USKi,j,t时，若敌手对用户设备进行攻击，敌手会获得USKi,j,t-1，USKi,j,t和UKi,j,t，这与直接将USKi,j,t-1和USKi,j,t交给敌手相比，敌手获得的用户私钥信息等同，我们称方案满足安全密钥更新.

4　本文提出的方案

本文提出的密钥隔离的无证书聚合签名方案具体算法描述如下：

(1)系统建立算法Setup(k，N)，输入安全参数k和总时间段数N，该算法按如下步骤生成KGC的主密钥s和公开参数param：

(b)选择群G的任意生成元P∈G.

(2)部分私钥生成算法PartialKey(s，IDi，param)，输入KGC的主密钥s和签名者身份IDi(1≤i≤n)，KGC按如下方式生成部分私钥：

(a)计算Pi,j=H1(IDi,j)∈G，其中j∈{0,1}，PSKi,j=s·Pi,j.

(b)KGC将部分私钥PSKi,j发送给签名者IDi.

(3)密钥生成算法KeyGen(PSKi,j，IDi，param)，输入给定签名者身份IDi，按如下方式生成签名者的初始私钥，签名者公钥和协助器的公私钥：

(d)计算UPKi=xi·Q.

(e)算法输出签名者IDi的初始私钥USKi,j,0，签名者公钥UPKi，协助器公钥HPKi，协助器私钥HSKi.

(4)更新消息生成算法UpdateM(t，IDi，HSKi，param)，协助器根据签名者身份IDi计算并输出t时间段的更新消息：

UKi,j,t=HSKi·(bi,t-bi,t-1)，发送给签名者IDi.

(5)签名者临时私钥更新算法UpdateU(t，IDi，USKi,j,t-1，UKi,j,t，param)，签名者IDi根据更新消息和t-1时间段的临时私钥，计算其在t时间段的临时私钥：

USKi,j,t=USKi,j,t-1+UKi,j,t

=xi·Pi,j+HSKi·bi,t-1+HSKi·(bi,t-bi,t-1)

=xi·Pi,j+HSKi·bi,t

(6)签名算法Sign(t，IDi，mi，USKi,j,t，param)，在t时间段，签名者IDi按如下步骤对其对应消息mi进行签名：

(a)与文献[2]的思想类似，第一个签名者选择一个字符串w并广播给其他签名者，保证w是唯一的.

(b)计算Pw=H3(w)∈G.

当等式成立时，该算法输出1，等式不成立时，该算法输出0.

5　方案的正确性和安全性分析

5.1方案的正确性

方案的正确性由以下推导可知：

+ci·(xi·s·Pi,1+x′·s·bi,t·QH)),P)

5.2方案的安全性

下面介绍方案的5个安全性定理，考虑篇幅的原因，安全性定理的详细证明见文献[19].

定理1假设群G中的CDH问题成立，则我们所提出的方案在随机预言模型下是密钥隔离安全的.若敌手AI可以在时间t内通过qHi(i=1,2,3,4)次Hi预言查询，qP次部分私钥提取查询，qPK次公钥提取查询，qK次密钥提取查询，qT次临时签名密钥提取查询，qS次签名查询，以至少概率ε攻破所示方案的密钥隔离安全，则就存在(t′,ε′)算法B可以攻破CDH假设，其中

t≤t′-cG(2qH1+qH3+2qH4+2qP+qPK+6qSK+4qT+12qS+2N+3).

定理2假设群G中的CDH问题成立，则我们所提出的方案在预言模型下是强密钥隔离安全的.若敌手AI可以在时间t内通过qHi(i=1,2,3,4)次Hi预言查询，qP次部分私钥提取查询，qPK次公钥提取查询，qH次协助器密钥提取查询，qS次签名查询，以至少概率ε攻破所示方案的强密钥隔离安全，则就存在(t′,ε′)算法B可以攻破CDH假设，其中，

t≤t′-cG(2qH1+qH3+2qH4+2qP+qPK+6qSK+3qH+10qS+2N+3).

定理3本文提出的方案在两类攻击者的攻击下是满足安全密钥更新的.

定理4假设群G中的CDH问题成立，则我们所提出的方案在预言机模型下是强密钥隔离安全的.若敌手AII可以在时间t内通过qHi(i=1,2,3,4)次Hi预言查询，qP次部分私钥提取查询，qPK次公钥提取查询，qH次协助器密钥提取查询，qS次签名查询，以至少概率ε攻破所示方案的强密钥隔离安全，则就存在(t′,ε′)算法B可以攻破CDH假设，其中，

t≤t′-cG(2qH1+qH3+2qH4+qPK+5qSK+4qT+12qS+2N+3).

定理5假设群G中的CDH问题成立，则我们所提出的方案在预言机模型下是强密钥隔离安全的.若敌手AI可以在时间t内通过qHi(i=1,2,3,4)次Hi预言查询，qP次秘密值提取查询，qPK次公钥提取查询，qH次协助器密钥提取查询，qS次签名查询，以至少概率ε攻破所示方案的强密钥隔离安全，则就存在(t′,ε′)算法B可以攻破CDH假设，其中

6　方案性能分析与比较

本节将提出的无证书密钥隔离聚合签名同另外几个签名方案在性能方面的比较见表1.

表1　本方案与其他方案的比较

从表1中可以看出，本方案同时满足无证书，聚合和密钥隔离等性质，这是其他方案所没有的.文献[2,18]是基于身份的签名方法，具有密钥托管问题，本方案和文献[5]不存在这个问题.在安全性方面，本方案和文献[18]可以提供前向安全性和后向安全性，而文献[2,5]的方案均没有提供这些安全性质，它们不能抵御密钥泄露问题.

表2中，n表示聚合签名中签名者的个数，Pairing表示一次群G中的配对运算，MUL表示一次群G中的乘法运算，忽略群G中的加法运算.一般来说，群中的加法运算耗时可以忽略，配对运算耗时最多.本方案在生成聚合签名的整个过程中，只需要群G中的乘法运算；而验证阶段只需要4次配对运算和乘法运算，因此，本方案具有较高的效率.

表2　本方案的效率分析

7　结论

为了解决无证书的聚合签名中密钥泄漏的问题，将密钥隔离安全机制嵌入到无证书的聚合签名中，首次提出了密钥隔离的无证书聚合签名的概念和安全模型，并给出第一个具体的方案.本文提出的无证书密钥隔离聚合签名不需要私用公钥证书，并且不存在密钥托管的问题；同时，运用密钥隔离机制，减少了密钥泄漏带来的危害；方案满足密钥隔离安全，强密钥隔离安全和安全密钥更新等性质，具有很高的安全性；聚合后的签名长度与单个签名长度相同，与签名者人数无关.

[1]Boneh D,Gentry C,Lynn B,et al.Aggregate and verifiably encrypted signatures from bilinear maps[A].Proceedings of Cryptology-EUROCRYPT 2003[C].Berlin:Springer-Verlag,2003.416-432.

[2]Craig G,Zulfikar R.Identity-based aggregate signatures[A].Proceedings of Public Key Cryptography 2006[C].Berlin:Springer-Verlag,2006.257-273.

[3]Kyung A S.An ID-based aggregate signature scheme with constant pairing computations[J].Journal of Systems and Software,2010,83(10):1873-1880.

[4]Al-Riyami S S,Paterson K.Certificateless public key cryptography[A].Proceedings of Cryptology-ASIACRYPT 2003[C].Berlin:Springer-Verlag,2003.452-473.

[5]Zheng G,Yu L,Xuan H,Chen K.Practical Certificateless aggregate signatures from bilinear maps[J].Journal of Information Science and Engineering,2008,26(6):2093-2106.

[6]Zhang L,Zhang F T.Security model for certificateless aggregate signature schemes[A].Proceedings of Computational Intelligence and Security 2008[C].Suzhou:IEEE,2008.2.364-368.

[7]Xiong H,Guang Z,Chen Z,Li F G.An Efficient certificateless aggregate signature with constant pairing computations[J].Information Science,2013,219(10):225-235.

[8]Chen Y,Horng G,Liu C,et al.Efficient certificateless aggregate signature scheme[J].J.Electronic Science and Technology,2012,10(3):209-214.

[9]Zhou M,Zhang M,Wang C,et al.CCLAS:A practical and compact certificateless aggregate signature with share extraction[J].International Journal of Network Security,2014,16(2):157-164.

[10]Zhang F,Shen L,Wu G.Notes on the security of certificateless aggregate signature schemes[J].Information Sciences,2014,287(10):32-37.

[11]Zhang L,Qin B,Wu Q H,Zhang F T.Novel efficient certificateless aggregate signatures[A].Proceedings of Applied Algebra,Algebraic Algorithms and Error-Correcting Codes[C].Berlin:Springer-Verlag,2009.235-238.

[12]Zhang L,Zhang F T.A new certificateless aggregate signature scheme[J].Computer Communications,2009,32(6):1079-1085.

[13]Zhang J,Mao J.An efficient RSA-based certificateless signature scheme[J].Journal of Systems and Software,2012,85(3):638-642.

[14]Chen H,Song W G,Zhao B.Certificateless aggregate signature scheme[A].Proceedings of International Conference on E-Business and E-Government[C].Guangzhou:IEEE,2010.3790-3793.

[15]Gong Z,Long Y,Hong X,Chen K F.Practical certificateless aggregate signatures from bilinear maps[J].Journal of Information Science and Engineering,2010,26(6):2093-2106.

[16]Dodis Y,Katz J,et al.Key-insulated public-key cryptosystems[A].Proceedings of Cryptology-Eyrocrypt 2002[C].Berlin:Springer-Verlag,2002.65-82.

[17]Wan Z,Lai X,Weng J,et al.Certificateless key-insulated signature without random oracles[J].Journal of Zhejiang University Science A,2009,10(2):1790-1800.

[18]Wan Z M,Lai X J,Weng J,Li J G.Certificateless strong key-insulated signature[A].Proceedings of Information Science and Technology [C].Nanjing:IEEE,2011.270-276.

[19]寻甜甜.密钥隔离的聚合签名的研究[D].青岛:青岛大学硕士论文,2015.34-51.

寻甜甜女，1988年出生于山东济宁.青岛大学硕士，现为山东外事翻译职业学院助教，主要研究方向信息安全.

于佳(通信作者)男，1976年生于山东青岛.青岛大学教授，信息安全系主任，研究生导师.主要研究方向为密码学与信息安全.

E-mail:qduyujia@gmail.com

Key-Insulated Certificateless Aggregate Signature

XUN Tian-tian1,YU Jia1,2,YANG Guang-yang1,JIANG Xiu-xiu1,HAO Rong1

(1.CollegeofInformationEngineering,QingdaoUniversity,Qingdao,Shandong266071,China；2.ShandongProvincialKeyLaboratoryofComputerNetwork,ShandongAcademyofSciences,Jinan,Shandong250014,China)

Certificateless aggregate signature is proposed to solve the key escrow problem and the complex certificate management problem.If the private key of any signer is exposed,the certificateless aggregate signature generated by the users including this signer will no longer be secure.To mitigate the damages of key-exposure in certificateless aggregate signature,we firstly integrate the key isolation mechanism into certificateless aggregate signature,and proposed the definition of key-insulated certificateless aggregate signature and its security model.We give a practical scheme,which achieves the periodical update of the signer′s secret key by the interaction with the helper.We prove the proposed scheme is secure in the random oracle model,i.e.,the scheme has key insulated security,strong key insulated security and secure key updates.

aggregate signature;key insulation;certificateless signature;key escrow;bilinear pairings

2014-10-20;

2015-07-01；责任编辑：马兰英

国家自然科学基金(No.61272425,No.61572267);山东省计算机网络重点实验室开放课题(No.SDKLCN-2013-03);青岛市建设事业发展项目(No.JK2015-26)

TP309

A

0372-2112 (2016)05-1111-06

电子学报URL:http://www.ejournal.org.cn10.3969/j.issn.0372-2112.2016.05.014