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

唐紫鑫，黄欣沂



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

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

（1. 福建师范大学数学与信息学院，福建 福州 350007；2. 福建省网络安全与密码技术重点实验室，福建 福州 350007）

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

可截取签名；Waters数字签名；批量签名；RSAProd方案

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，contentextraction 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方案基于向量承诺设计，用个签名取代一个签名。方案以个承诺为代价，只要能减少承诺的计算量，那么签名的计算量也会相应减少。但提取子消息的随机值和删除的子消息的承诺值使签名长度很长，与子消息的数量呈线性关系。为了减少删除的子消息的承诺值造成的签名冗长，改进的HT方案巧妙地使用抗碰撞的散列函数构造二叉树，将数据存储在二叉树中，减少了签名长度，然而计算量仍很大。RSAP方案的构造基于RSA签名的同态性质，因而验证者只需验证RSA签名的乘积模的值是否等于散列值乘积的签名模的值。因此，方案减少了传送给验证者的签名长度，缺点在于没有减少签名者与数据持有者之间所传递签名的长度。而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 双线性对

2.2 困难假设

2.3 数字签名

2.4 Waters签名方案

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

2.5 批量签名

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

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

2.6 可截取签名

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

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

2.7 弱序CES不可伪造性

3 批量化Waters数字签名方案

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

3.1 方案描述

3.2 方案安全性分析

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

4.1 方案描述

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

4.2 方案正确性分析

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

(2)

4.3 方案安全性分析

应用引理1，有

经计算得

这包含要证的式子。

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

4.4 效率分析

表1 符号说明

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

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

5 结束语

[1] 中兴通讯学院.对话多媒体通信[M]. 北京: 人民邮电出版社, 2010. ZTE UNIVERSITY. Talk to multimedia communication[M]. Beijing: Posts and Telecom Press, 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.

[3] 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.

[4] 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.

[5] ELGAMAL T. A public key cryptosystem and a signature scheme based on discrete logarithms[J]. IEEE Trans inf theory, 1984, 31(4): 469-472.

[6] STANDARDS N I O. Digital signature standard (DSS)[J]. Federal Information Processing Standards Publication 186-2, 2000, 25.

[7] 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.

[8] SCHNORR C P. Efficient signature generation by smart cards[J]. Journal of Cryptology, 1991, 4(3): 161-174.

[9] STEINFELD R, BULL L, ZHENG Y. Content extraction signatures[C]//The International Conference on Information Security and Cryptology ( ICISC 2001). 2001: 285-304.

[10] 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.

[11] 蓝才会, 王彩芬. 基于身份的可截取签名方案[J]. 计算机应用, 2007, 27(10): 2456-2458.LAN C H, WANG C F. ID-based content extraction signature[J]. Journal of Computer Applications, 2007.

[12] 曹素珍, 王彩芬. 基于离散对数问题的可截取签名方案[J]. 计算机工程, 2013, 39(4): 132-136.CAO S Z, WANG C F. Content extraction signature scheme based on DLP[J]. Computer Engineering, 2013, 39(4): 132-136.

[13] 李旭, 杜小妮, 王彩芬,等. 基于RSA的可截取签名改进方案[J]. 计算机工程与应用, 2014,50(24): 96-99.XU L I, XIAONI D U, WANG C, et al. Improved scheme of content extraction signatures based on RSA[J]. Computer Engineering & Applications, 2014.

[14] 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.

[15] 王彩芬, 徐婷, 张玉磊, 等. 基于可截取签名和属性加密的云存储访问控制方案[J]. 计算机工程与科学, 2015, 37(2): 238-244. 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.

[16] 王敏, 马金花, 刘江华,等. 两类可截取签名方案的改进[J]. 网络与信息安全学报, 2017,3(4): 69-77.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.

[17] FIAT A. Batch RSA[J]. Journal of Cryptology, 1997, 10(2): 75-88.

[18] 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.

[19] CATALANO D, FIORE D. Vector commitments and their applications[M]//Public-Key Cryptography–PKC 2013. Springer Berlin Heidelberg, 2013: 55-72.

[20] WATERS B. Efficient identity-based encryption without random oracles[J]. Eurocrypt, 2005, 2004(2004): 114-127.

[21] KATZ J. Digital signatures[M]. Springer US, 2010: 127-128.

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

TANG Zixin1,2, HUANG Xinyi1,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

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.

content extraction signature, Waters scheme, batch signature,RSAProd scheme

TP393

A

10.11959/j.issn.2096-109x.2018102

2018-10-25；

2018-11-20

黄欣沂，xyhuang81@yahoo.com

国家自然科学基金资助项目（No.61822202，No.61872089）

The National Natural Science Foundation of China (No.61822202, No.61872089)

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

黄欣沂（1981-），男，江苏仪征人，福建师范大学教授、博士生导师，主要研究方向为密码学和信息安全。