无证书聚合签名方案的分析*

(三亚学院信息与智能工程学院,海南三亚 572000)

0 引言

2003年Al-Riyami和Paterson第一次提出无证书密码[1]。该方法可以作为解决传统公钥基础设施(Public Key Infrastructure,PKI)和基于身份的公钥密码(identity-based Public Key Cryptography,ID-PKC)问题的中间方案。传统的PK I需要一个可信机构来将实体的身份与其公钥绑定,而ID-PKC需要一个可信的私钥生成器(Private Key Generator,PKG)来根据用户身份生成用户的私钥。因此,在基于身份的密码中,公钥设置的证书管理问题实际上被密钥托管问题所取代。

在无证书公钥密码体制(Certificateless Public Key Cryptography,CL-PKC)中,仍然使用第三方密钥生成中心(Key Generation Center,KGC)来帮助用户生成私钥[2-4]。然而,KGC 不能访问用户自己选择的秘密信息和从KGC接收的部分私钥生成的最终私钥。KGC 使用一个称为主密钥的秘密值产生部分私钥。用户的公钥由用户根据自己选择的秘密信息和KGC 的公共参数计算出来,并由用户自己发布。

无证书密码提出来以后,出现了很多基于无证书环境的密码方案。无证书密码体制的安全性也备受关注。无证书环境下的敌手模型主要包括两种类型的对手。I类对手A1无权访问主密钥,但可以访问任何实体的秘密值,并可以用另一个值替换其公钥;II类对手A2可以访问主密钥,但无法执行公钥替换。

2003年,Boneh等人提出了聚合签名的概念[5]。聚合签名方案是一种数字签名方案,它允许将n个不同的签名者在n个不同消息上产生的签名聚合为单个签名。发送和验证聚合签名分别需要较少的通信和计算开销。这样就产生了很多无证书聚合签名[6-8](Certificateless Aggregate Signature,CLAS)。在大多数的CLAS方案中,配对操作(这是基于配对的密码方案中常用的最耗时的操作)的数量和聚合签名的大小随着签名者的数量线性增长。在文献[8]中,Nie等人提出了一个有效的CLAS方案,其中聚合签名的长度和在聚合签名验证过程中执行的配对操作的数量都不取决于签名者的数量。

文献[8]声称他们的聚合签名方案在随机预言模型中对自适应选择消息攻击是存在不可伪造的,并试图在包含上述两种对抗类型CLAS 方案的标准安全模型中证明这一点。在本文中,我们根据该安全模型证明了Nie等人的CLAS方案是不安全的,即它对于无证书密码学中的I型对手不存在不可伪造性。更具体地说,我们证明了A1可以通过获得一对消息和该签名者的相应签名,可以在任何消息上伪造任何签名者的签名。

1 无证书聚合签名方案

在本节中,提供了CLAS方案的框架及其安全性定义。

1.1 CLAS方案框架

假设KGC是密钥生成中心,U1、U2、……Un表示n个参与者,其身份标识分别为ID1、ID2、……、IDn。

一个CLAS方案由六个算法(algorithm)组成:系统建立、用户密钥生成、部分私钥提取、签名、聚合签名和聚合验证。

系统建立:输入为安全参数k,输出为主密钥λ和系统参数列表params。该算法由密钥生成中心KGC运行。

用户密钥生成:输入为系统参数params和用户身份IDi,生成用户公钥/密钥对(xi,pki)。该算法由系统中得每个用户运行。

部分私钥提取:输入为主密钥λ、系统参数params和用户Ui的身份标IDi∈{0,1}*;生成一个部分私钥Di。该算法由KGC对每个用户运行一次,并假设通过安全信道将Di安全地发送给对应的用户。

签名:由身份为IDi的签名者Ui运行,输入为系统参数params、两个状态信息Δ和、消息mi∈{0,1}*以及Ui的私钥(Di,xi),输出为签名σi。

聚合签名:输入为用户U1、U2、……、Un生成的n 个签名σ1、σ2、……、σn,输出为消息(m1、m2、……、mn)的聚合签名σ。

1.2 安全模型

在无证书环境下,对抗模型由两种类型的对手组成。I型对手A1没有访问主密钥权限,但可以访问任何实体的密钥值并用另一个值替换其公钥;II型对手A2可以访问主密钥,但无法执行公钥替换。

CLAS方案的安全性是通过挑战者C和对手A1或对手A2之间的两次攻击游戏来建模的。我们的目的是证明文献[8]的CLAS方案没有提供针对I型对手A1所需的安全性。这里仅介绍包含A1的游戏1,定义如下:

C通过输入一个安全参数k,运行系统建立算法,得到系统参数params和主密钥λ;然后C将params发送给对手A1,同时保留主密钥λ。

对手A1可以自适应地进行多项式有界次数的下列查询操作:

(1)哈希查询:输入消息的时候,由C返回对应的哈希值。

(2)部分私钥提取查询:在输入签名者Ui的身份IDi时,C运行部分私钥提取算法生成Di并输出。

(3)公钥查询:输入用户Ui的身份IDi后,C通过运行用户密钥生成算法返回相应的公钥pki。

(4)秘密值查询:输入用户Ui的身份IDi时,如果Ui的公钥没有被替换则C返回秘密值xi,否则返回⊥。

(5)公钥替换查询:输入用户Ui的身份IDi和公钥pki’后,C用新的接收值替换用户Ui的公钥,并记录此替换。

(6)签名查询:在输入用户Ui身份、消息mi和状态信息Δ和时,C通过运行签名算法以响应对应的签名σi。

·A1输出一个元组(m*,Δ*,,ID*,σ*),其中Δ*和是状态信息,m*=(m*1,m*2,…,m*n),ID*=(ID*1,ID*2,…,ID*n),σ*是聚合签名。

当且仅当满足下列条件时,A1赢:

(1)σ*是用户身份ID*=(ID*1,ID*2,…,ID*n)、状态信息为Δ*和、对应公钥为(pk*1,pk*2,…,pk*n)的消息m*上的有效聚合签名;

(2)在部分私钥查询中至少有一个身份(假设为ID*1∈ID*)没有被查询到,且在签名查询中未查询到(Δ*,,m*1,ID*1,)。

定义1:如果对手A1不能在概率多项式时间以不可忽视的优势赢得游戏I,那么该CLAS方案是类型I安全的。

2 CLAS方案评述

这里将对文献[8]提出的CLAS方案进行简单的评述。

假设KGC 是密钥生成中心,U1、U2、……、Un表示一组参与者。该CLAS 方案包含下述算法:

2.1 系统建立:由KGC执行

输入:安全参数k∈Z;

过程:

(1)在生成器P上生成的素数阶q≥2k的椭圆曲线上选取一个循环加群G1;

(2)选择具有相同阶数和双线性映射e:G1×G1→G2的循环乘法群G2;

(3)选择加密哈希函数:H1:{0,1}*×G1→G1,H2:{0,1}*→G1,H3:{0,1}*×G1→Z*q;

(4)选择一个随机数λ∈Zq并计算Ppub=λP。

输出:KGC保护的主密钥λ和发布的系统参数params=(q,G1,G2,e,P,Ppub,H1,H2,H3)。

2.2 用户密钥生成:由系统中的每个签名者Ui执行

输入:系统参数params和用户身份IDi;

过程:

(1)选择一个随机值xi∈Z*q作为该用户的秘密值;

(2)计算Pi=xiP;

输出:由Ui保护的秘密值xi和公开发布的公钥pki=。

2.3 部分私钥提取:KGC执行

输入:系统参数params、主密钥λ、用户身份IDi∈{0,1}*及其公钥Pi;

过程:

(1)计算Qi=H1(IDi||Pi);

(2)计算Di=λQi;

输出:安全地发送给身份为IDi的用户的部分私钥Di。

2.4 签名:身份为IDi的用户执行

输入:系统参数params、任意消息mi∈{0,1}*、状态信息Δ和和签名者Ui’的秘密值xi、部分私钥Di以及其公钥pki;

过程:

(1)选择一个随机的ri∈Z*q并计算Ri=riP;

(2)计算W=H2(Δ),

(3)计算Si=Di+hixiW+(xi+ri)T

输出:Ui’在消息mi的签名σi=(Ri,Si)

2.5 聚合签名

输入:系统参数params、n个不同签名者的n个签名(R1,S1),…,(Rn,Sn);

输出:聚合签名σ=(R,S)。

2.6 聚合验证

输入:n个签名者以公钥(pk1,…,pkn)在消息(m1,…,mn)上状态为Δ和的聚合签名σ=(R,S)

过程:

(1)计算W=H2(Δ),T=H3();

(2)对于i=1,…,n,计算Qi=H1(IDi||Pi),hi=H3(mi||IDi||Δ||||Pi);

(3)验证e(S,P)=e(∑ni=1Qi,Ppub)e(∑ni=1hiPi,W)e(R+∑ni=1Pi,T)

输出:如果(3)的等式成立返回True,否则为False。

3 密码分析

定理1:在[8]的方案在定义1的意义上是不安全的,即类型I对手可以在游戏1中成功的伪造聚合签名。

证明:为了简单起见,先假设n=1。设签名者U,其公钥为pk=,使用该CLAS方案。为了在状态信息Δ和下代表U在消息m’生成有效的伪造签名σ’,A1在游戏1中针对挑战者C 采取如下行动:

(1)C运行系统建立算法并输出系统参数params;

(3)以U的身份ID进行秘密值查询,获取输出x;

(4)计算S’=S-hxW,其中W=H2(Δ),h=H3(m||ID||Δ||||PU);

如上所述,只是考虑到一个签名者的情况。伪造的过程很容易推广到一般情况:首先伪造一个签名人的签名,然后在聚合签名中用原始签名替换伪造签名。

4 小结

本文研究了最近提出的一个无证书聚合签名方案的安全性,并证明了该方案对于无证书密码学中的I型对手不存在不可伪造性。更具体地说,我们证明了A1可以通过获得一对消息和该签名者的相应签名,可以在任何消息上伪造任何签名者的签名。