可修订的数字签名研究

黄欣沂

福建师范大学

一 研究背景概述

随着社会的日益数字化，我们已经进入数据时代，数据的价值得到越来越广泛的认同，随之而来的数据安全问题已成为关系国家经济、政治、国防、文化安全的重大问题。数字签名是验证数据内容完整性和真实性的一种重要密码技术。数字签名的传统安全目标为在自适应选择消息攻击下具有存在不可伪造性（Existential Unforgeability under Adaptive Chosen Message Attacks，EUF-CMA）。如果数字签名方案满足EUF-CMA，那么有效的数字签名能让数据接收者相信其收到的数据没有被篡改。

虽然EUF-CMA能满足验证数据真实性的基本要求，但满足EUF-CMA的传统数字签名算法不支持对数据的认证修订：即使稍稍修改数据的内容，原始数字签名也会失效，不能用于验证经过合理修改后数据的真实性。为了获得修改后数据的有效数字签名，数据持有人可将修改后的数据发给签名人，签名人在核对后再次对修改后的数据重新签名，用以验证数据的真实性。该过程需要数据持有人和签名人进行交互，在签名人离线的情况下，很难实现实时交互。为了避免该问题，签名人也可以预先对所有子数据的组合分别进行签名，该过程虽然避免了签名持有人和签名人之间的交互，但计算和通信开销均过大。

可修订签名是一类支持编辑操作的具有同态性质的数字签名，其概念由Steinfeld等^[1]和Johnson等^[2]分别独立提出。在不与签名人交互的情况下，签名持有人（修订者）可删除已签名数据中的子数据，并计算修订后数据的有效签名。自2001年被正式提出以来，可修订签名一直是应用密码学领域的研究热点，在电子投票、智能电网、电子医疗记录系统等很多实际场合有着广泛应用。近年来，国内外学者从形式化安全定义、提取规则、计算效率、通信效率等多个方面对可修订数字签名进行了研究，相继取得了一批有意义的研究成果。但是网络技术及其应用的快速发展不断地对可修订数字签名提出新的要求，依然有许多值得进一步研究的问题。

二 主要科学问题

尽管国内外学者陆续提出了一批有意义的研究成果，但仍然有一些值得进一步研究的问题。

1.修订内容可控的可修订签名方案只能实现粗粒度的修订内容控制，亟待研究修订内容细粒度可控的可修订签名。

2.修订人员可控的可修订签名中的模型不够完整，方案不够丰富，亟待研究可审计-可修订的数字签名。

3.未见抗量子计算的可修订数字签名方案在主流的会议/期刊上发表，亟待突破。因此，对上述3个关键问题进行研究具有重要的理论和现实意义，相关的研究成果将为实际应用中数据的安全保护提供理论和技术支撑，为充分实现数据的价值创造更加良好的支撑环境。

三 国际研究现状

现有的绝大多数可修订签名算法没有考虑对修订内容的控制，无法控制数据持有人对数据的恶意修订等行为。Steinfeld等^[1]最早引入了内容截取访问结构实现签名持有人对被签名消息的修订控制。但后续的可修订签名方案只有少数几个考虑到修订控制：Miyazaki等^[3,4]实现了对单个数据块的修订控制，但没有考虑到数据块之间的关联性；Bull等^[5,6]考虑到数据块之间的关联性，实现了对多个数据块的修订控制。但文献[3-6]中方案均属于粗粒度的修订控制，虽然文献[1]中方案具有细粒度修订控制功能，但其内容截取访问结构的编码长度偏长，实际可用性较低。修订内容细粒度可控的可修订数字签名的研究仍处于起步阶段，亟需开展进一步的研究。

除了限制可修订的内容外，还可以通过限制执行修订操作的人员控制滥用修订的现象。在大部分现有的设计中，任何持有数据、签名和签名人公钥的用户都可以删除原数据中的子数据，并计算修订后数据的有效签名。只有极少数的可修订签名方案考虑了对修订人员的限制。虽然文献[7-8]最早对如何限制执行修订操作的人员展开了初步研究，但直到2015年Pöhls和Samelin^[9]才对这个问题进行了正式的研究，并将该类方案命名为Accountable Redactable Signatures（ARS）。但ARS的研究仍处于起步阶段，相关的模型和定义还不够完整，方案的设计还不够丰富，亟需结合实际应用场景开展进一步的研究。

随着量子计算理论和实践的快速发展，研究抗量子计算的密码算法已成为共识。目前未见具有抗量子计算能力的可修订签名设计方案在主流的会议/期刊上发表，因此亟需研究基于格上困难问题的可修订签名，填补没有抗量子计算的可修订数字签名算法的空白。

四 国内研究现状

目前，我国针对可修订数字签名的一流研究成果较少。文献[10]针对可修订签名算法中修订控制的问题进行了初步研究，基于单调访问结构、单调张成、线性秘密共享方案和聚合器等密码学组件，提出了首个具有单调修订控制功能的高效可修订数字签名方案（RSS-FGRC），实现了对修订内容的细粒度可控。

文献[10]形式化定义了RSS-FGRC的安全模型，并给出了具体的方案构造。具体地，先调用传统数字签名方案生成签名人的公私钥对(sk,pk)。签名人将原始数据M分成n个数据块，并设置M的修订控制策略，即单调扩张程序P，并将P转化为访问二叉树T，数据块均被分配到叶子节点上；由T得到n行t列访问矩阵E（其中，t为二叉树T的高度-1）；签名人选择向量=(s,y₂,…,y_t)，其中，s为秘密值；计算线性秘密共享向量=(s₁,s₂,…,s_n)^T，将s_i顺序分配给二叉树T叶子节点上的数据块；利用聚合器计算聚合值d←Acc(r,m₁||s₁,m₂||s₂,…,m_n||s_n)；利用标准数字签名方案进行签名σ←sgn_sk(d||s)；输出签名结果。消息块集合X为删除子集，包含j个数据块；修订者更新r′，输出修订签名结果。只有当修订后数据满足单调扩张程序P的修订规则时，验证者才可以恢复出秘密值s′，计算集合值d′，验证签名的有效性1/0←Verify_pk(d′||s′)，当签名有效时输出1，否则为0。当修订后数据M′不满足单调扩张程序P的修订规则时，验证者将无法恢复出正确的秘密值s，无法验证签名的有效性。

文献[10]中方案具有不可伪造性、隐私性和透明性。不可伪造性要求在已知签名人公钥pk的情况下，概率多项式时间的攻击者可以自适应地询问签名预言机，攻击者的目标是输出一个有效的数据签名对(M*,σ*)，并且数据M*满足M*不是被询问的任一数据的子集，或者M*是被询问过的某一数据的子集，但M*不满足修订控制规则。可修订签名的不可伪造性要求攻击者实现上述目标的概率是可忽略的。隐私性要求在已知签名人公钥pk的情况下，概率多项式时间的攻击者可以自适应地询问签名预言机，可修订签名的隐私性要求攻击者很难推导出被移除数据的信息。透明性要求攻击者很难判断出收到的签名是否被修订过。此外，文献[10]从理论和实验两个方面分析了方案的有效性和实用性。

五 未来研究建议

未来研究建议如下。

（1）借鉴基于属性加密和签名的优秀设计方案，结合聚合器等具有特殊性质的密码学组件，设计修订内容细粒度可控的可修订数字签名。

（2）借鉴群签名、不可否认签名、可审计的优化公平交换协议等密码方案的设计，解决透明性和可审计性相互兼容的难题，加强可修订签名中的可审计性，设计高效安全的可审计-可修订签名。

（3）以抗量子计算的普通数字签名方案和密码学聚合器为基础组件，构建抗量子计算的可修订签名方案。

参考文献：

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

[2] JOHNSON R, MOLNAR D, SONG D, et al. Homomorphic signature schemes[C]//Cryptographers' Track at the RSA Conference. 2002: 244-262.

[3] MIYAZAKI K, IWAMURA M, MATSUMOTO T, et al. Digitally signed document sanitizing scheme with disclosure condition control[J]. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, 2005, 88(1): 239-246.

[4] MIYAZAKI K, HANAOKA G, IMAI H. Digitally signed document sanitizing scheme based on bilinear maps[C]//2006 ACM Symposium on Information, Computer and Communications Security, 2006: 343-354.

[5] BULL L, SQUIRE D M, NEWMARCH J, et al. Grouping verifiable content for selective disclo sure[C]//Australasian Conference on Information Security and Privacy. 2003: 1-12.

[6] BULL L, SQUIRE D M, ZHENG Y L. A hierarchical extraction policy for content extraction signatures[J].International Journal on Digital Libraries, 2004,4(3): 208-222.

[7] MEER H, PÖHLS H C, POSEGGA J, et al. Redactable signature schemes for trees with signer-controlled non-leaf-redactions[C]//International Conference on E-Business and Telecommunications. 2012: 155-171.

[8] SAMELIN K, PÖHLS H C, BILZHAUSE A, et al. On structural signatures for tree data structures[C]// International Conference on Applied Cryptography and Network Security. 2012: 171-187.

[9] POHLSAND H C, SAMELIN K. Accountable redactable signatures[C]//2015 10th International Conference on Availability, Reliability and Security (ARES). 2015: 60-69.

[10] MA J H, LIU J H, HUANG X Y , et al. Authenticated data redaction with fine-grained control[C]//IEEE Transactions on Emerging Topics in Computing. 2017.