新的格上变色龙签名方案

丁 亮*，陈 岩，胡鸿宣，鲁国阳，高 淼

（1.河南中烟工业有限责任公司，河南 郑州；2.郑州轻工业大学 计算机科学与技术学院，河南 郑州）

数字签名可用来鉴别文件的真伪，又能够防止通信双方中由任意一方所造成的抵赖。然而，传统的数字签名往往是公开可验证的，无法阻止不诚实的验证者对签名者所签署的敏感文件进行二次传播。为避免该行为，1989 年，Chaum 和Antwerpen[1]提出了不可否认签名（Undeniable Signature, US），其通过控制签名的验证解决该问题，但在验证环节要求签名者必须在线参与，且不可避免地涉及到繁重的零知识证明。1996 年，Jakobsson 等人[2]提出了指定验证者签名（Designated Verifier Signature, DVS），签名者和指定验证者拥有相同的签名权限，任意第三方无法确认签名是由签名者真实生成还是由指定验证者模拟，但在签名的真实性出现争议时无法提供有效的仲裁机制。1998 年，Krawczyk 和Rabin[3]创造性地提出了变色龙签名（Chameleon Signature, CS），更简便地解决了签名的二次传递问题。

变色龙签名在签名算法中嵌入一个有效的变色龙哈希函数（Chameleon Hash Function, CHF）来对消息进行散列。对指定验证者而言，其利用秘密持有的陷门来计算CHF 的碰撞是可行的，即能够在变色龙哈希值不变的条件下随意更换原始消息，从而使得二次传递的消息在任意第三方前失去“可信度”；相反地，对不拥有陷门的任意用户，CHF 仍保持抗碰撞性。相较于US，CS 不依赖复杂的交互式协议和零知识证明，而是采用“哈希- 签名”范式来实现离线验证。相较于DVS，对于指定验证者的伪造，CS 中的签名者能够对其“证伪”，即满足签名者可拒绝性。显然地，CS在云医疗、电子选举和数字版权保护等应用场景中尤为适用[4-5]。

在后量子密码时代，基于传统数论难题的CS 方案将面临在多项式时间内被量子计算机攻破的现实威胁[6]。2008 年，Gentry 等人[7]创造性地设计出格上原像采样算法，并基于经典的小整数解（Small Integer Solution, SIS）难题假设，构造了格上强不可伪造的签名方案。2010 年，Cash 等人[8]给出了格上安全的CHF。2013 年，基于文献[7-8]的工作，谢等人[9]宣称构造了格上第一个CS 方案。2016 年，采用文献[8]的CHF，Noh 等人[10]给出了格上标准模型下安全的强指定验证者签名方案，缺陷是签名必须携带大尺寸密文，且无法解决签名的争议问题。2017 年，Xie 等人[11]提出了同态CHF的概念，并宣称构造了一个格上有限级数的全同态签名方案，缺陷是同态CHF 的设计存在天然的计算错误。2021 年，Thanalakshmi 等人[12]构造了基于哈希的CS 方案，缺陷是签名者和指定验证者必需各自存储一个复杂的有向无环图，且签名的生成过程比较繁琐。

本文对文献[9]中的格上第一个CS 方案进行密码学分析，指出其不满足抗选择消息攻击下的第三方不可伪造性和签名者可拒绝性；进一步地，提出了一个新的格上CS 方案，并在随机预言机模型下严格证明了新方案满足抗适应性选择消息攻击下强不可伪造性、签名不可传递性、签名者可拒绝性以及不可抵赖性。

1 预备知识

1.1 格

1.2 变色龙签名

令消息空间为 M，随机数空间为 R以及签名值空间为 S。一个标准的CS 方案[3]主要包括三个参与方：签名者 S，指定验证者V 以及仲裁者：

(1) Setup：输入安全参数λ，输出公共参数pp。

(2) KeyGen：输入pp，输出 S和V 的公私钥对和。

(3) Sign：由 S运行的概率性算法。输入pp，公钥pkV，公私钥对和消息 μ ∊M， 输出随机数r∊R和签名值 σ ∊S。

一个安全的CS 方案需满足以下性质：

定义6 若 (μ, r,σ) ∊ M× R × S 为指定验证者V 伪造，且签名者S 有能力说服仲裁者J 拒绝该签名，则称CS 方案满足签名者可拒绝性；相反地，若 (μ, r,σ)为S 真实生成，且其无法否认，则称CS 方案满足签名者不可抵赖性。

2 谢等人方案的安全性分析

定理1 谢等人的格上CS 方案不满足抗选择消息攻击下的第三方不可伪造性。

证明 对于谢等人的方案，通过分析其签名过程，本文发现任意第三方可以伪造出一个有效的签名，且S 无法使J 拒绝该签名：

综上可知，谢等人的格上CS 方案不满足抗选择消息攻击下的第三方不可伪造性。

定理2 谢等人的格上CS 方案不满足签名者可拒绝性。

综上可知，谢等人的CS 方案不满足签名者可拒绝性。

3 新的格上CS 方案

3.1 方案描述

3.2 安全分析

定理4 新方案满足签名不可传递性。

定理5 新方案满足签名者可拒绝性和不可抵赖性。

证明 因篇幅所限，定理3、4 和5 的证明过程不再赘述，任何需要的读者可联系通讯作者。

4 性能分析

将给出的新的格上CS 方案与其他抗量子计算攻击的可传递性签名方案[9-12]在功能性、存储与传输成本方面相比较，结果如表1 所示，其中，k0表示同态计算的数据集尺寸，k1表示有向无环图的内部顶点集；×表示不满足，√表示满足，- 表示不考虑。显然地，本文方案在功能方面更加全面，可适用于更加广泛的应用场景；在存储和传输成本方面，减少了公共参数的存储以及签名生成和传输的开销，满足轻量级设备进行签名的实用性需求。

表1 不同方案的性能对比

结束语

结合抗量子计算攻击的格密码体制和CS 原语的安全特性，本文对格上第一个CS 方案进行了密码学分析，指出其不满足抗选择消息攻击下的第三方不可伪造性和签名者可拒绝性；进一步地，给出了一个新的格上CS 方案，并在随机预言机模型下严格证明了其满足抗适应性选择消息攻击下强不可伪造性、签名不可传递性、签名者可拒绝性以及不可抵赖性。此外，给出的新方案也减少了签名生成和传输的开销，符合轻量级签名的实用性需求。