网络与信息安全学报, 2018, 4(12): 44-53 doi: 10.11959/j.issn.2096-109x.2018102

学术论文

基于批量签名思想的可截取签名构造

唐紫鑫1,2, 黄欣沂,1,2

1 福建师范大学数学与信息学院,福建 福州 350007

2 福建省网络安全与密码技术重点实验室,福建 福州 350007

Construction of the content extraction signature scheme based on the thought of the batch scheme

TANG Zixin1,2, HUANG Xinyi,1,2

1 School of Mathematics and Information,Fujian Normal University,Fuzhou 350007,China

2 Fujian Provincial Key Laboratory of Network Security and Cryptology,Fuzhou 350007,China

通讯作者: 黄欣沂,xyhuang81@yahoo.com

修回日期: 2018-11-20   网络出版日期: 2018-12-15

基金资助: 国家自然科学基金资助项目.  61822202
国家自然科学基金资助项目.  61872089

Revised: 2018-11-20   Online: 2018-12-15

Fund supported: The National Natural Science Foundation of China.  61822202
The National Natural Science Foundation of China.  61872089

作者简介 About authors

唐紫鑫(1993-),男,湖南株洲人,福建师范大学硕士生,主要研究方向为密码学和信息安全。 。

黄欣沂(1981-),男,江苏仪征人,福建师范大学教授、博士生导师,主要研究方向为密码学和信息安全。 E-mail:xyhuang81@yahoo.com

摘要

根据批量签名的思想,将 Waters 数字签名方案批量化,进而构造可截取签名。所构造的方案是Steinfeld、Bull、Zheng ( ICISC 2001) 提出的RSAProd方案的改进,以较长的截取签名长度为代价节省整体的运算时间,并证明所构造方案在适应性选择消息攻击下具有不可伪造性和隐私性。

关键词: 可截取签名 ; Waters数字签名 ; 批量签名 ; RSAProd方案

Abstract

The Waters scheme was transformed into the content extraction signature scheme at the bridge of the thought from the batch signature scheme.The proposed scheme is improved by the RSAProd scheme,presented by Steinfeld,Bull,Zheng (ICISC 2001).The operation time is saved in every stage at the slight sacrifice of the length of extraction signatures.The security was proved that the proposed scheme is existentially unforgeable under chosen message attacks while the privacy is maintained.

Keywords: content extraction signature ; Waters scheme ; batch signature ; RSAProd scheme

PDF (642KB) 元数据 多维度评价 相关文章 导出 EndNote| Ris| Bibtex  收藏本文

本文引用格式

唐紫鑫, 黄欣沂. 基于批量签名思想的可截取签名构造. 网络与信息安全学报[J], 2018, 4(12): 44-53 doi:10.11959/j.issn.2096-109x.2018102

TANG Zixin. Construction of the content extraction signature scheme based on the thought of the batch scheme. Chinese Journal of Network and Information Security[J], 2018, 4(12): 44-53 doi:10.11959/j.issn.2096-109x.2018102

1 引言

数据和信息之间是相互联系的。数据是反映客观事物属性的记录,是信息的具体表现形式[1]。数据经过加工处理之后,就成为信息;而信息需要经过数字化转变成数据才能存储和传输[1]。数据不仅是用户的隐私,更是互联网财富的源泉。众多科研机构、研究人员将问题与生活实际联系起来时,数据提供着必不可少的支撑。在数据驱动型经济背景下,企业的决策和国家的发展战略制定都需要以数据为依据,各大企业乃至世界各国陷入一场前所未有的数据争夺战。数据安全问题的保障、隐私数据的保护也成为数据争夺战中应当考虑的重要问题。

数字签名[2]是保证数据安全的核心技术之一,在电子政务、电子商务、医疗数据、电子现金等领域有广泛的用途。数字签名可提供数据内容的完整性和数据源的真实性检测。

数字签名的标准安全要求是在自适应选择消息攻击下满足EUF-CMA安全——存在不可伪造性(existential unforgeability under adaptive chosen message attacks)[3]。EUF-CMA安全的含义:已知签名者的公钥,PPT(probability polynomial-time)攻击者通过适应性询问获得需要的有效消息签名对后,能为某个新消息计算出有效签名的概率是可以忽略的。若数字签名方案满足此标准安全要求,则该数字签名有效并能让消息接收者相信收到的消息是完整的且未被恶意篡改,同时消息的来源是相应公钥的持有者。经典数字签名方案有ElGamal[4,5]、DSA、ECDSA[6]、RSA-FDH[7]和Schnorr[8]签名等。

尽管数字签名方案的标准安全要求能够满足数据认证的基本要求,却也阻碍了签名持有者对已签名数据的合理操作。

为了满足相应的实际需求,Steinfeld、Bull、Zheng(ICISC 2001)提出可截取签名(CES, content extraction signature)[9]。截取中“截”意味着删除,“取”作提取之意。在不与初始签名人进行交互的情况下,可截取签名允许签名的持有者将可以公开进行验证的数据提取出来组成新数据,并根据初始签名计算出对新数据的签名。换言之,可截取签名允许签名的持有者对删除敏感数据后的新数据集生成新的签名。

由于相对数字签名所拥有的此种特殊功能,可截取签名的应用场景相当广泛。本文以电子病历为例阐述可截取签名的功能。假设研究所C为研究某种疾病的治疗方案,需要征集广大患者的病历。以患者B为例,设B可提供就诊医院A签发的电子病历。电子病历通常记录着患者的姓名、性别、身份证号、家庭地址、联系电话、病史和诊疗记录(包括病情描述和处方)等相关信息。但是B不愿向研究所透露身份证号、家庭地址、联系电话等信息。如果A直接用普通数字签名算法对病历签名,那么B无法对病历进行删改以保护隐私信息,从而B可能拒绝C的请求。可截取签名则较好地解决此类问题。若A在签名阶段使用可截取签名对病历签名,则B可以对病历进行适当的操作,再提供给 C。相比普通数字签名,可截取签名最大的优势在于支持删除操作,且不需要私钥即可通过初始数据和初始签名计算出新的数字签名,并证实所保留数据的真实性。自提出以来,国内外学者对可截取签名进行了大量深入的研究。

文献[10将可截取签名应用于以数字图书馆为典型代表的环境,提出采用分级群组策略的可截取签名方案,这是对文献[9]提出的可截取签名的直接应用。文献[11]提出新的基于身份的可截取签名方案,该方案不需要对每个子消息进行签名,这提高了签名效率,且能够防止私钥产生机构伪造签名。文献[12]提出一种满足强安全性、基于离散对数困难问题的可截取签名方案,此方案还包含身份信息,指数计算较少,相应地减少了计算量。文献[13]的方案基于FDH-RSA签名方案改进,在保持原方案安全性能不变的基础上,优化截取文档的结构,解决了截取后文档存在的板式凌乱问题。文献[14]提出一种能把密钥泄露带来的损失减小到最低的可截取签名方案。文献[15]提出一种细粒度的访问控制,在加密数据的同时把符合属性的子消息传送给用户,对存储中访问控制的问题进行细化,提高消息的利用率。文献[16]则将截取消息分为必须截取和可选截取两部分,允许对部分消息进行统一签名和验证。这些重要研究在文献[9]的基础上从不同角度继承和发展,丰富了可截取签名的研究。

上述应用方案的改进与文献[9]中提出的 CV (commit vector)、HT(hash tree)、RSA积(RSAP, RSAProd)、MERP(multi-exponent RSAProd)4种方案联系密切。CV方案基于向量承诺设计,用n个签名取代一个签名。方案以n个承诺为代价,只要能减少承诺的计算量,那么签名的计算量也会相应减少。但提取子消息的随机值和删除的子消息的承诺值使签名长度很长,与子消息的数量呈线性关系。为了减少删除的子消息的承诺值造成的签名冗长,改进的 HT 方案巧妙地使用抗碰撞的散列函数构造二叉树,将数据存储在二叉树中,减少了签名长度,然而计算量仍很大。RSAP 方案的构造基于RSA签名的同态性质,因而验证者只需验证 RSA 签名的乘积模 N 的值是否等于散列值乘积的签名模N的值。因此,方案减少了传送给验证者的签名长度,缺点在于没有减少签名者与数据持有者之间所传递签名的长度。而MERP方案对这个缺点进行了改进,节省了签名者的计算量但失去了快速验证的性质。这几个方案的设计目标都是既能快速签名又能快速验证的可截取签名,且都是基于批量签名[17]设计的。

批量签名的概念由Fiat于1989年提出,能够用一次签名对若干个不同消息签名,并且可以对每一条消息进行独立验证。此后,批量签名得到广泛的应用和发展,其中影响很大的工作之一是文献[18]提出的基于树结构的批量签名算法。此结构与任何可证明安全的数字签名进行结合都可以得到安全的批量签名方案。文献[9]中的HT方案所用的树结构便是根据树结构的批量签名改造而来。不同之处在于,文献[18]的方案不能满足可截取签名隐私性的要求,于是文献[9]中的一个方案运用向量承诺[19]的隐藏性保证隐私性,此即为 HT 方案奠定基础的 CV 方案。文献[9]中的RSAP 方案具有批量验证的性质,但是不能批量签名。MERP 方案应用文献[17]中的 Fiat 变换进行多指数RSA批量化,使方案具有批量签名的性质,但失去快速验证的性质。另外,文献[13]也引入批量签名的思想,改进了签名和认证部分。由此,将批量签名改进成可截取签名是构造可截取签名值得研究的一个方向,改进的过程中关键在于如何在保护数据隐私性的同时使计算量和签名长度同时达到最优。

本文从Waters签名方案[20]着手,先把数字签名批量化,构造批量化的Waters签名,再将批量签名转化为可截取签名(称之为基于Waters签名方案的可截取签名WCES)。此方案为可截取签名的构造提供了较为一般的方法,与其他可截取签名方案进行横纵向对比,说明此方案运行速度较快。

2 预备知识

2.1 双线性对

GG1分别是素数p阶乘法群,g为群G的生成元,映射e^:G×GG1具有以下性质。

1) 双线性:若a,b,有 e^(ga,gb)=e^(gb,ga)=e^(g,g)ab

2) 非退化性:若a,bG,使e^(a,b)1,其中,1为G1的单位元。

3) 可计算性:存在多项式时间算法计算e^(ga,gb)ˆ。

2.2 困难假设

在循环群G中定义计算性DH假设(CDH, computational Diffie-Hellman)。简单地说,CDH假设表示以下问题是困难的:对于任意生成元gG,已知 ga,gbG(a,b均是随机选取的指数),输出gabG,将此假设正式化为下列定义。

定义1[21]G中的CDH问题是困难的,对任意多项式时间算法A,以下概率可忽略。

Pr[paramsG(1k);

a,bq:A(params,ga,gb)=gab]

2.3 数字签名

定义 2 [21]数字签名方案包括 3 个多项式算法(KeyGen,Sign ,Verify )。

1) 随机的密钥生成算法(KeyGen):输入安全参数1k,输出公私钥对(pk,sk)。记作

(pk,sk)KeyGen(1k)

2) 签名算法(Sign):输入私钥sk和消息m,输出消息m的签名σ。记作

σSign(sk,m)

3) 确定性的验证算法(Verify):输入公钥pk,消息m和待验证的签名σ,输出0或1。如果σ是m的有效签名,则输出 1,否则输出 0。记作

{0,1}Verify(pk,m,σ)

定义3[21](CMA实验)数字签名方案需要满足的安全性质是在自适应选择消息攻击下具有存在不可伪造性。本文用挑战者C和攻击者A之间的实验来描述不可伪造性。

初始化:C运行密钥生成算法KeyGen(1k)获得公私钥对(pk,sk),并将pk传送给A。

询问:A可以通过访问签名预言机Sign的方式向挑战者询问至多q个消息的签名。

对每个消息mi(i=1,2,,q) ,C运行签名算法Sign(sk,mi),并将算法的输出(mii)返回给A。本文用Q表示A向预言机询问过的消息集合Q={m1,m2,,mn}

输出伪造:在完成所有消息询问后,设A输出伪造的消息签名对是(m**)。若此消息签名对满足条件Verify(pk,m**)=1且m*∉Q,则A攻击成功。

在选择消息攻击下,如果任意的概率多项式敌手A攻击成功的概率是可忽略的,则称签名方案(KeyGen,Sign ,Verify )具有存在不可伪造性。

2.4 Waters签名方案

定义 4[21]Waters 签名方案包括 3 个多项式时间算法。

1) 密钥生成算法:输入安全参数1k,计算参数 params=(G,G1,q,g,e^)G(1k);随机选择aq 并设 g1:=ga;选择随机数 g2,u0,,ukG;输出公钥(params,g1,g2,u0,,uk),私钥g2a

H(m)=u0i=1kuimi,其中,m=m1m2mk{0,1}k

2) 签名算法:给定消息m {0,1}k∈ ,输入签名者所选随机数rq,输出签名(g2aH(m)r,gr)

3) 验证算法:输入消息m和对应签名(σ12),检查e^(g,σ1)=e^(σ2,H(m))e^(g1,g2)是否成立,如若成立,则输出1,否则输出0。

定理 1[21]如果群G中的CDH问题是困难的,那么Waters签名方案在适应性选择消息攻击下满足存在不可伪造性。

2.5 批量签名

对很多消息同时签名时,批量签名能够用一次签名完成对若干个不同的消息签名,并且可以对每一条消息进行独立验证[17],从而批量对消息签名大大提高了效率。

批量签名应用非常广泛,能用于电子商务、电子现金等领域。因其应用领域的相似性,可考虑转化为可截取签名。与批量签名不同的是,可截取签名可将待签名消息做适当处理以保护隐私信息。

2.6 可截取签名

由于普通的数字签名不允许对数据进行任何修改,为了让签名持有者能够从初始数字签名计算出截取签名(对删除隐私信息后的数据生成的签名),一种简易的方法是签名者A把消息划分为若干子消息,逐个对子消息进行签名,并把所有子消息的签名传送给签名的使用者B。B保留需要的子消息,并从得到的签名中挑选对应的子消息的签名组成的集合作为截取消息的签名。这是可截取签名的一种经典设计思路。验证者能够对此签名集合中的每一签名逐个验证。但如果签名者不能对消息的截取进行控制,将容易导致消息被恶意截取以致消息泄露。为此,文献[9在可截取签名中引入可截取访问规则(CEAS,content extraction access structure),使签名者能够通过CEAS控制消息M的截取,从而有效阻止消息被恶意截取进而泄露隐私。

本文用消息M={m1,m2,,mn}表示由n个子消息组成的原消息。新消息M={m1',m2',,mn'}

CI (M')表示保留消息编号的集合。为保证签名者对原消息M的截取方式具有完全控制权, CEAS对每个子消息段规定必须保留和可保留2种方式,分别用1和0表示。故CEAS是由若干个向量组成的,每一个向量代表一个可截取规则。截取者根据CEAS选择的截取子集X 确定CI(M')以及M'。其中,M'中的子消息数量、排列位置必须和M中的子消息保持一致。若M中子消息mi的编号在CI(M')中,则M'中的mi'=mi,否则,用符号“?”替换mi。如果截取方式合法,则表示为CI(M')∈CEAS。

例如,设任意消息M ={m1,m2,m3,m4,m5,m 6},不妨设CEAS={(1,1,0,0,0,0),(1,0,1,0,0,0)}。若X =(1,1,0,0,0,0)∈CEAS,则CI(M')={1,2}和对 应 的 M'={m1,m2,?,?,?,?} 是 合 法 的;CI(M')={1,2,3}和对应的M'={m1,m2,m3,?,?,?}也是合法的。但是,CI(M')={1,3}和对应的M'={m1,?,m3,?,?,?}是不合法的,因为没有保留必须保留的消息m2;CI(M')={1,2,3}和对应的M'={m1,m2,m3,?,?}也是不合法的,因为M'和M中子消息数量不一致。

定义 5[9]可截取签名包括 4 个多项式算法CES=(Gen,Sig,Ext,Ver)。

1) 密钥生成算法(Gen):输入安全参数1k,输出公私钥对(pk,sk)。记作

(pk,sk)Gen(1k)

2) 签名算法(Sig):输入私钥sk、M和可截取访问规则CEAS,输出可截取签名σF。记作

(M,σF)Sig(sk,M,CEAS)

3) 截取算法(Ext):输入公钥pk、M、可截取签名σF和截取子集X,输出截取签名σE。记作

(M',σE)Ext(pk,M,σF,X)

4) 验证算法(Ver):输入公钥pk、消息M和签名σ,输出0或者1。如果σ是M的有效签名,输出1,否则输出0。记作

{0,1}Ver(pk,M,σ)

可截取签名的正确性要求:可截取签名(CES)需要满足下述一致性条件。

(签名算法的正确性要求)对任意的安全参数1k,任意的公私钥对(pk,sk)←Gen(1k)、CEAS、M和(M,σF)←Sig(sk,M,CEAS),必须能够通过算法Ver的验证,即Ver(pk,M,σF)=1。

(验证算法的正确性要求)对任意的安全参数1k,任意的公私钥对(pk,sk)←Gen(1k)、CEAS、M、(M,σF)←Sig(sk,M,CEAS)、截取子集X∈CEAS和(M',σE)←Ext(pk,M,σF,X),必须能够通过算法Ver的验证,即Ver(pk,M',σE)=1。

可截取签名的安全模型包括不可伪造性和隐私性两部分。

CES不可伪造性指除了按照可截取访问规则生成原签名消息的子消息之外,攻击者不能再对其他消息产生有效的可截取签名。

假设概率多项式算法能够以自适应选择消息的方式攻击可截取签名方案(Gen,Sig,Ext,Ver),可以用挑战者C和伪造者F 之间的实验描述可截取签名方案的不可伪造性。

C运行Gen(1k)获得公私钥对(pk,sk),并将公钥pk传送给F。

F 可以自适应地访问签名预言机。F 以(Mi,CEASi)向预言机进行至多q次询问,C运行签名算法Sig(sk,Mi,CEASi)并返回有效的消息签名对(Mii)给F。本文用M表示F向预言机询问过的消息集合M={M1,M2,,Mq}

最终F输出伪造的消息签名对(M**)。

挑战者运行验证算法,如果下列条件成立,那么F伪造成功:

1) Ver(pk,M**)=1;

2) 若F 伪造的消息M*不是曾经询问过的消息Mi的子集,则F 伪造了一个新的有效消息,或者,M*是Mi的子集但伪造的消息中保留的消息不满足相应截取规则,即CI(M*)∉CEASi

在适应性选择消息攻击下,如果对任意的概率多项式伪造者F 在实验中获胜的概率是可忽略的,那么称可截取签名方案(Gen,Sig,Ext,Ver)在适应性选择消息攻击下满足存在不可伪造性。

隐私性是指已知截取消息和截取签名,攻击者不能知道被删除消息的内容。

假设概率多项式算法能够以自适应选择消息的方式攻击可截取签名方案(Gen,Sig,Ext,Ver),可以用挑战者F 和区分者D之间的实验描述可截取签名方案的隐私性。

实验主要包括2个阶段:在询问阶段中,D可以自适应请求询问Sig预言机,询问阶段结束后,DC提出挑战(M 0,M1),作为回应,C产生随机数c∈{0,1},筛选出M 0和M1其中一个,并对随机筛选出的消息计算截取签名返回给D。在猜测阶段,D仍然可询问Sig预言机,最后给出猜测值c'。

初始化:F 运行Gen(1k)获得公私钥对(pk,sk),并将公钥pk传送给D

询问阶段:D可以自适应地询问签名预言机Sig。D以(Mi,CEASi)向预言机进行至多q次询问,然后C运行Sig(sk,Mi,CEASi)并返回有效的消息签名对(Mii)给D。本文用M表示D向预言机询问过的消息集合M ={M1,M 2,",M q}。

D自适应地选择合法的签名,利用截取算法Ext计算得到截取签名。

挑战阶段:询问阶段结束后,D输出2个消息(M 0,M1),它们除了在位置i*处的子消息不同外,在其他位置的子消息是相同的。即*M 0[i]=M1[i],i≠i。这组消息分别在位置i*上有着对应的消息 M0 和 M1,即 M0[i*]=M0,*M1[i ]=M1。同时,D对 2 个消息选择相同的CEAS*,且D可选择待保留消息编号的集合X*∈CEAS*,i*∉X*

作为回应,C利用产生的随机数c∈{0,1},筛选出M0和M1其中一个,选出的消息设为M*,即 M*=Mc。根据 D 选择的 CEAS* 以及X*∈CEAS*,C依次计算

σF*Sig(sk,M*,CEAS*)

σE*Ext(pk,M*,σF*,X*)

最终将计算结果σE*返回给D

猜测阶段:收到C返回的签名后,D仍然可以询问Sig,最后给出猜测值c'。

猜测值:最后D输出猜测的值c',如果c'=c且i*∉X*,那么D区分成功。

在适应性选择消息攻击下,设区分者D区分成功的概率为Pr[c'=c],定义D能区分成功的优势为AdvD,CESCMA,pk,那么AdvD,CESCMA,pk=Pr[c'=c]12

如果对于任意的概率多项式区分者而言,该优势都是可忽略的,则可截取签名方案(Gen,Sig,Ext,Ver)在选择消息攻击下满足隐私性。

2.7 弱序CES不可伪造性

定义 6[9]对于能访问 CES 签名预言机的任意攻击者A,如果A产生有效的消息签名对(M, σ)是不可行的,则称可截取签名方案CES具有弱序 CES 不可伪造性(WO-UF),其中有效的消息签名对(M,σ)满足下列条件:

1) 签名σ是消息M的有效签名;

2) 消息M包含某个位置i上的子消息,此子消息不同于所有向CES签名预言机询问过的消息位置i处的子消息。

定义 7[9](不可伪造变换TWO(·))变换TWO(·)将任何CES 方案CES1=(Gen1,Sig1,Ext1,Ver1) 作为输入,都可以将其转化为新方案,即CES2=TWO(CES1)=(Gen2,Sig2,Ext2,Ver2)。

引理 1[9]变换TWO(·)将任何具有弱序不可伪造性的方案CES1转化为CES2=TWO(CES1),使方案CES2具备完整的CES存在不可伪造性。具体以公式表示为

InsecCES2CESUF(t,qs,n,l)

InsecCES1WOUF(t,qs,n,l)+qs(qs1)2ltag+1(1)

t是攻击者最大运行时间,qs是询问签名预言机的最大次数,n是询问子消息的个数,l是签名长度,且t′=t,qs′=qs,n′=n,l′=l+lCEAS+ltag+log(n)。另外,定义InsecCES2CESUF(t,qs,n,l)=maxAASRPSuccA,CES2CESUF,将攻击成功的最大概率考虑为不安全性。其中,资源参数RP=(t,qs,n,l),A∈ASRP是所有攻击者的集合。

3 批量化Waters数字签名方案

本节呈现由数字签名到批量签名的转换过程。

3.1 方案描述

定义8 批量化Waters数字签名方案包括3个多项式算法。

1) 密钥生成算法(KeyGen):输入安全参数1k,确定参数组params=(G,G1,q,g,e^)G(1k)|G|=|G1|=q,且q是一个大素数。GG1的生成元是g。随机选择aq并设g1:=ga。选择随机数g2,u0,,ukG

输出公钥(params,g1,g2,u0,",uk),私钥g2a

2) 签名生成算法(Sign):输入待签名的消息M(按需被分为n个子消息)和私钥g2a,签名过程如下。

① 计算每个子消息的散列值jH(mi)=u0j=1kujmijmi=mi1mi2min{0,1}k

H(m)=H(H(m1)H(m2)H(mn))

③ 签名者选择随机数rq,计算消息M签名(σ1,σ2)=(g2aH(m)r,gr)

④ 输出消息M的批量签名((σ1,σ2),H(m),h1,h2,,hn),hi=H(mi)

3) 签名验证算法(Verify):输入公钥(params,g1,g2,u0,,uk)、消息M'和对应的签名(σ12)。验证过程如下。

① 验证hi=H(mi),i=1,2,n

② 检查e^(g,σ1)=e^(σ2,H(m))e^(g1,g2)是否成立。若成立,则输出1,否则输出0。

3.2 方案安全性分析

定理2 如果Waters方案在适应性选择消息攻击下满足存在不可伪造性,那么批量化的Waters方案是安全的。

说明 ((σ1,σ2),H(m),h1,h2,,hn),hi=H(mi)是消息M的批量签名,则对每一个消息,都可以考虑单独的Waters签名。因此接下来只需考虑单个Waters签名的伪造。假设存在敌手成功攻破批量签名,敌手每选择一个消息,能产生相应的Waters签名,最终对一个新消息m˜形成批量签名。

因此,本文将问题归结为,在适应性选择消息攻击下对Waters签名方案的攻击。而由定理1知Waters签名方案在适应性选择消息攻击下具有存在不可伪造性,可证批量化的Waters签名的安全性。

4 基于Waters签名方案的可截取签名

4.1 方案描述

定义9 基于Waters签名方案的可截取签名(WCES)包括4个多项式算法。

1) 密钥生成算法(Gen):输入安全参数1k,由此确定参数组 params=(G,G1,q,g,e^)G(1k)|G|=|G1|=q,且q是一个大素数。GG1的生成元是g。随机选择aq并设g1:=ga。 选择随机数g2,u0,,ukG

输出公钥(params,g1,g2,u0,,uk),私钥g2a

2) 签名生成算法(Sig):输入待签名的消息M(按需被分为n个子消息)、可截取访问规则CEAS和私钥g2a。定义T为CEAS标记,在签名过程中随机选取。签名过程如下。

① 对M的每个子消息mi,附上可截取访问规则CEAS,CEAS标记T,消息长度n,消息编号i,即mi ←(CEAS,T,n,i,Mi),其中M'对应于消息mi,且Mi=(mi1mi2min),mij{0,1}k

② 计算子消息散列值jH(mi)u0j=1kujmij

③ 签名者选择随机数rq,计算每个子消息的签名(σi1,σ2)=(g2aH(mi)r,gr)

④ 输出σF(CEAS,T,(σi1,σ2)i[n])

3) 签名截取算法(Ext):输入消息M、可截取访问规则CEAS和可截取签名σF,截取者执行如下过程:首先截取者验证收到的签名是否有效,若有效,则执行下列步骤,否则返回失败。

删除相应子消息的签名,截取过程如下。

① 根据签名者指定的可截取访问规则CEAS构造截取子集X。

② 根据截取子集,生成保留的消息集合M'。

③ 取出保留消息对应的签名 (σi1,σ2)iX

④ 输出 σE(CEAS,T,M',(σi1,σ2)iX)

4) 签名验证算法(Ver):输入公钥(params,g1,g2,u0,,uk)、消息M'和对应的签名σE,验证者执行如下过程。

① 令X'←CI(M'),签名者首先验证X'∈CEAS是否成立,若成立,则执行下列步骤,否则返回失败。

② 对每个子消息mi,i∈X',计算H(mi)。

③ 计算 H(m)iXH(mi)

④ 检查iXe^(g,σi1)=e^(σ2,H(m))e^(g1,g2)是否成立。若成立,则算法输出1,否则输出0。

4.2 方案正确性分析

该方案的正确性包括以下两部分。

1) (签名算法的正确性要求)对任意的安全参数1k,任意的公钥(params,g1,g2,u0,,uk)、私钥g2a、可截取访问规则CEAS、CEAS标记T、消息M,mi ←(CEAS,T,n,i,Mi),计算每个子消息的散列值,生成签名(σi1,σ2)=(g2aH(mi)r,gr),则σF(CEAS,T,(σi1,σ2)i[n])必须能够通过算法Ver的验证,即Ver(pk,M,σF)=1满足

iXe^(g,σi1)=iXe^(g,g2aH(mi)r)

=e^(g,g2a)e^(g,H(m1)r)e^(g,g2a)

e^(g,H(m2)r)e^(g,g2a)e^(g,H(mn)r)

=e^(ga,g2)e^(gr,H(m1))e^(ga,g2)

e^(gr,H(m2))e^(ga,g2)e^(gr,H(mn))

=e^(g1,g2)e^(σ2,H(m1))e^(g1,g2)

e^(σ2,H(m2))e^(g1,g2)e^(σ2,H(mn))

=e^(σ2,H(m))e^(g1,g2)(2)

2) (验证算法的正确性要求)对任意的安全参数1k,任意的公钥(params,g1,g2,u0,,uk)、私钥g2a、可截取访问规则CEAS、CEAS标记T、消息M',生成签名(σi1,σ2)(g2aH(mi)r,gr)、进而构成σF(CEAS,T,(σi1,σ2)i[n]),且对任意的截取子集X∈CEAS和(M',σE)← Ext(pk,M ,σF,X),必须能够通过算法Ver的验证,即Ver(pk,M',σE)=1,且当n=len(M')时,式(2)成立。

4.3 方案安全性分析

定理 3 1) 如果标准的数字签名Waters方案在适应性选择消息攻击下满足存在不可伪造性,则WCES方案具有CES存在不可伪造性,满足

InsecWCESCESUF(t,qs,n,l)

InsecWatersCMA(t[F],qs[F],l[F])+qs(qs1)2ltag+1(3)

其中,t是攻击者最大运行时间,qs是询问签名预言机的最大次数,n是询问子消息的个数,l是签名长度。

2) WCES方案具有CES隐私性(完善且无条件的),即InsecWCESCES-PR(,n,l)=0

证明 1)首先,方案WCES将一般性安全加强变换TWO(·)(定义 7)作用于简易的WCES1方案转化而来,即WCES=TWO(WCES1),其中,简易的WCES1方案中签名的子消息不包括(CEAS,n,T)。

应用引理1,有

InsecWCESCES-UF(t,qs,n,l)InsecWCES1WO-UF(t,qs,n,l)+qs(qs1)2ltag+1(4)

其中,t′=t,qs′=qs,n′=n,l′=l+lCEAS+ltag+log(n)。

要表示攻击WCES方案成功的概率与攻击Waters方案成功的概率的关系,只需证明

InsecWCES1WO-UF(t,qs,n,l)InsecWatersCMA(t[F],qs[F],l[F])(5)

其中,t[F]=t′+O(qs′n′),qs[F]=(qs′+1)n′,n′=n,l[F]=l′+log(n′)。

令攻击 A1 在WO-UF 下攻击签名方案WCES1=(Gen1,Sig1,Ext1,Ver1),攻击者A2在CMA下攻击签名方案Waters=(KeyGen,Sign ,Verify )。根据对A1的攻击限制攻击者A2成功的概率。

A2调用CMA实验,输入Waters方案的公钥(params,g1,g2,u0,,uk)和安全参数1k,其中params=(G,G1,q,g,e^)G(1k),随 机 选 择aq 并设 g1:=g a,选择随机数 g2,u0,",ukG,相应的私钥是g2a。A2能询问Waters方案签名预言机S。

初始化:输入1k(params,g1,g2,u0,,uk), A2运行A1,其中A1作为A2的子程序。

询问:当A1向预言机Sig1做出第 j个CES询问(CEAS j,M j),A2使用询问预言机S返回的结果通过模拟Sig1算法做出回答。

令nj =len(M j)。对任意的i∈[nj],A2定义消息M¯j[i]=(i,Mj[i]),且向签名预言机S询问此消息的签名σ¯j[i]。最终,A2设置模拟的签名为σj=(σ¯j)i[nj]。假设A2保存此询问记录。

输出:A1终止询问并输出伪造的消息签名对(M**),其中H(M*)=iXH(M*[i])σ*=(σ*[1],σ*[2])=(g2aH(M*)r,ga)

令n*=len(M*)且X*=CI(M*)。A2搜索存储的询问记录,试图寻找位置(设单个消息截取满足截取规则)i*(∈X*)处的子消息满足

M*[i*]Mj[i*],j[qs]

如果 A2 找到这样的一个位置i*,则对每个i∈X*−{ *i},向签名预言机S对消息M¯*[i]=(i,M*[i])进行询问,获得签名

(σ*[i1],σ*[2])=(g2aH(M¯*[i])r,ga)

经计算得

σ¯*=(g2aH(M¯*[i])r,ga)

最终,A2 输出的伪造消息签名对是(M¯*[i*],σ¯*[i*])

至此完成A2的描述,A2的资源参数可以从上述描述中得到验证。为了证明此论点,还需要描述A2在选择消息攻击下攻击成功的概率。

使用Pr[⋅]exp表示实验exp的概率;

CES方案WCES1(在WO-UF下)和Waters方案(在CMA下)的攻击实验分别记作w1和w。

定义以下事件。Succ1表示A1在WO-UF意义下攻击成功。Succ1意味着(M¯*,σ¯*) 能通过方案WCES1的验证算法(称此事件为Valid1),且存在i*(∈X*)满足M*[i*]≠M j[i*],∀j∈[qs](称此事件为NewM1)。事件Succ2表示A2在CMA意义下攻击成功。Succ2意味着(M¯*,σ¯*) 能通过方案Waters的验证算法(称此事件为Valid 2),且消息M¯*从未询问过签名预言机 S(称此事件为NewM 2)。

下面证明如果Succ1发生,则Succ2也发生。因为A2在攻击实验exp.w中模拟A1的视图,如同在攻击实验w1,所以事件Succ2在2 个实验中有相同的概率,因此有SuccA2,WatersCMA(k)SuccA1,WCESCESUF(k)

这包含要证的式子。

为了完成证明,还需证Succ1包含Succ2。首先Succ1包含Valid1,事件Succ1表示A1成功攻破方案WCES1,则伪造的消息签名对是一个有效的Waters签名,同时Valid 2发生。下面说明NewM 2发生。因为 Succ1 发生,则 NewM1发生,即M *[i*]≠M j[i*],∀j∈[qs],M¯*[i*]M¯j[i*],∀j∈[qs],且A2对预言机S的其他询问(即M¯*[i]M¯j[i], i≠i*,∀j∈[qs]均和伪造的消息M¯*[i*]有着不同前缀)。所以Succ1发生,伪造的消息不会询问过预言机S。此即NewM 2发生。

2) 此可截取签名的隐私性是显然的,因为截取签名统计上独立于删除的子消息。

4.4 效率分析

本节对基于Waters签名方案的可截取签名的算法复杂度进行分析。

纵向上,由于WCES方案可视为文献[2]提出的RSAP方案的平行改进,因此将其与RSAP方案进行比较,符号说明如表1所示,比较结果如表2所示。

表1可得,由于Waters签名方案运算速度的优越性,WCES方案在空间复杂度与RSAP方案相近的情况下,能够保持时间复杂度较优。

横向上,文献[13]提出的方案改进的可截取签名方案(IRSAP,Improved RSAP)以及文献[9]中的HT方案都是应用批量签名思想对可截取签名进行的改进,其中,IRSAP也是根据RSAP方案改进而来,因而可考虑与CEAS方案进行对比分析,如表3所示,符号说明也如表1所示。

表3可看出,IRSAP的算法复杂度略高于RSAP方案。HT方案引入批量签名的思想固然提高了签名速度,签名长度亦相应减少,但其算法复杂度很大程度上依赖于数字承诺的应用。可见WCES乃折中有效的改进。

5 结束语

本文主要呈现可截取签名较为一般的构造方法。根据批量签名的思想,将Waters数字签名方案批量化,进而改进为可截取签名。所构造的方案可视为RSAP方案的平行改进,以较长的截取签名长度为代价节省整体的运算时间。通过与其他方案的横向对比说明了所构造方案的优点。并证明所构造方案在适应性选择消息攻击下具有不可伪造性和隐私性。

表1   符号说明

符号符号说明符号符号说明
n原消息中子消息的数目TExtWaters截取签名所用时间
m截取消息中子消息的数目TProdH计算散列值乘积的时间
TSRSA执行一次RSA签名所需时间lSRSARSA签名长度
TSWaters执行一次Waters签名所需时间lSWatersWaters签名长度
TS执行一次签名所需时间ltagCES-tag长度
TC执行一承诺所需时间ln消息的个数为n
TH计算一次散列函数所需时间lCEASCEAS编码长度
NRSA中模数因子lm子消息长度,假设每个子消息等长
TProdRSA一次求积模N 所需时间li子消息编码长度
TVRSA执行一次RSAP方案验证算法时间lH散列值长度lH =l tag+lCEAS+lm+ln+li
TVWaters执行一次Waters方案验证算法时间lC承诺的长度
TV执行一次签名验证算法所需时间f (m,n)min(mlb(nm),nm)

新窗口打开| 下载CSV


表2   2种方案算法复杂度纵向比较

方案签名时间截取时间验证时间签名长度截取长度
RSAPn(TH(lH)+TSRSA)TProdRSAmTH(lH)+TProdRSA+TVRSAltag+lCEAS+nlSRSAltag+lCEAS+lSRSA
WCESn(TH(lH)+TSWaters)TExtWatersmTH(lH)+TProdH+TVWatersltag+lCEAS+nlSWatersltag+lCEAS+mlSWaters

新窗口打开| 下载CSV


表3   3种方案算法复杂度横向比较

方案签名时间截取时间验证时间签名长度截取长度
WCESn(TH(lH)+TSWaters)TExtWatersmTH(lH)+TProdH+TVWatersltag+lCEAS+nlSWatersltag+lCEAS+mlSWaters
IRSAPn(TH(lH)+TSRSA)+TbatchTProdRSAmTH(lH)+TProdRSA+TVRSA+Tbatchltag+lCEAS+nlSRSA+lbatchltag+lCEAS+lSRSA+lbatch
HTTs(lH)+3nTc(lm)TExtHT+3nTc(lm)TV(lH)+(2n+m)TC(lm)lS+lrlS+mlr+f(m,n)lC

新窗口打开| 下载CSV


本文的构造是根据批量签名中批量验证的思想降低各个算法的时间复杂度,但所需传递的签名长度有待进一步优化。文献[9所提出的MERP方案应用批量签名中一次签名的优点缩短签名长度,提高截取者与验证者的传递效率,不足之处是失去快速验证的性质,使验证效率略低。因此,构造时间复杂度和空间复杂度同时较低的可截取签名是一个值得挑战的研究问题。

The authors have declared that no competing interests exist.
作者已声明无竞争性利益关系。

参考文献

中兴通讯学院.

对话多媒体通信

[M]. 北京: 人民邮电出版社, 2010.

[本文引用: 2]

ZTE UNIVERSITY..

Talk to multimedia communication

[M]. Beijing: Posts and Telecom PressPress, 2010.

[本文引用: 2]

RIVEST R L , SHAMIR A , ADLEMAN L A .

Method for obtaining digital signatures and public-key cryptosystems

[J]. Communications of the ACM, 1978,21(2): 120-126.

[本文引用: 2]

GOLDWASSER S , MICALI S , RIVEST R L .

A digital signature scheme secure against adaptive chosen-message attacks

[J]. Siam Journal of Computing, 1988,17(2): 281-308.

[本文引用: 1]

ELGAMAL T , .

A public key cryptosystem and a signature scheme based on discrete logarithms

[C]// Workshop on the Theory and Application of Cryptographic Techniques (Eurocrypt 1984). 1984: 10-18.

[本文引用: 1]

ELGAMAL T .

A public key cryptosystem and a signature scheme based on discrete logarithms

[J]. IEEE Trans inf theory, 1984,31(4): 469-472.

[本文引用: 1]

STANDARDS N I O .

Digital signature standard (DSS)

[J].,2000,25. Federal Information Processing Standards Publication 186-2, 2000,25.

[本文引用: 1]

BELLARE M , ROGAWAY P .

The exact security of digital signatures-how to sign with RSA and rabin

[C]// International Conference on Theory and Application of Cryptographic Techniques. 1996: 399-416.

[本文引用: 1]

SCHNORR C P .

Efficient signature generation by smart cards

[J]. Journal of Cryptology, 1991,4(3): 161-174.

[本文引用: 1]

STEINFELD R , BULL L , ZHENG Y .

Content extraction signatures

[C]// The International Conference on Information Security and Cryptology ( ICISC 2001). 2001: 285-304.

[本文引用: 14]

BULL L , SQUIRE D M G , ZHENG Y .

A hierarchical extraction policy for content extraction signatures

[J]. International Journal on Digital Libraries, 2004,4(3): 208-222.

[本文引用: 1]

蓝才会, 王彩芬 .

基于身份的可截取签名方案

[J]. 计算机应用, 2007,27(10): 2456-2458.

[本文引用: 1]

LAN C H , WANG C F .

ID-based content extraction signature

[J]. Journal of Computer Applications, 2007

[本文引用: 1]

曹素珍, 王彩芬 .

基于离散对数问题的可截取签名方案

[J]. 计算机工程, 2013,39(4): 132-136.

[本文引用: 1]

CAO S Z , WANG C F .

Content extraction signature scheme based on DLP

[J]. Computer Engineering, 2013,39(4): 132-136.

[本文引用: 1]

李旭, 杜小妮, 王彩芬 ,.

基于RSA的可截取签名改进方案

[J]. 计算机工程与应用, 2014,50(24): 96-99.

[本文引用: 3]

XU L I , XIAONI D U , WANG C ,et al.

Improved scheme of content extraction signatures based on RSA

[J]. Computer Engineering& Applications, 2014

[本文引用: 3]

WANG C , LI Y , HUANG S Y ,et al.

A new forward secure content extraction signature scheme

[C]// International Conference on Fuzzy Systems and Knowledge Discovery. 2016: 1698-1702.

[本文引用: 1]

王彩芬, 徐婷, 张玉磊 ,.

基于可截取签名和属性加密的云存储访问控制方案

[J]. 计算机工程与科学, 2015,37(2): 238-244.

[本文引用: 1]

WANG C F , TING X U , ZHANG Y L ,et al.

An access control scheme in cloud storage based on content extraction signature and attribute encryption

[J]. Computer Engineering & Science, 2015

[本文引用: 1]

王敏, 马金花, 刘江华 ,.

两类可截取签名方案的改进

[J]. 网络与信息安全学报, 2017,3(4): 69-77.

[本文引用: 1]

WANG M , MA J H , LIU J H ,et al.

The two improvements of the content extraction signature

[J]. Chinese Journal of Network and Information Security, 2017,3(4): 69-77.

[本文引用: 1]

FIAT A .

Batch RSA

[J]. Journal of Cryptology, 1997,10(2): 75-88.

[本文引用: 3]

PAVLOVSKI C J , BOYD C .

Efficient batch signature generation using tree structures

[C]// International Workshop on Cryptographic Techniques and E-Commerce (CrypTEC 1999). 1999: 70-77.

[本文引用: 2]

CATALANO D , FIORE D .

Vector commitments and their applications

[M]// Public-Key Cryptography–PKC 2013. Springer Berlin Heidelberg, 2013: 55-72.

[本文引用: 1]

WATERS B .

Efficient identity-based encryption without random oracles

[J]. Eurocrypt, 2005,2004(2004): 114-127.

[本文引用: 1]

KATZ J .

Digital signatures

[M]. Springer US, 2010: 127-128.

[本文引用: 5]

/