格上基于身份的变色龙签名方案

张彦华 陈 岩 刘西蒙 尹毅峰 胡予濮

①(郑州轻工业大学计算机与通信工程学院 郑州 450001)

②(福州大学数学与计算机科学学院 福州 350108)

③(西安电子科技大学通信工程学院 西安 710071)

1 引言

一个传统的数字签名应该是公开可验证、可传递且不可伪造的，即任意用户都能够验证并相信(或拒绝)某文件的真实性及其签名者的身份信息。然而，这些性质无法满足某些旨在防止验证者对文件内容传播的特殊场景。1989年，Chaum和Van Antwerpen[1]提出的不可否认签名(Undeniable Signature, US)要求验证者在尝试验证前必须向签名者发出在线请求，且不可避免地涉及繁重的零知识证明系统，致使签名效率普遍不高。1996年，Jakobsson等人[2]提出了指定验证者签名(Designated Verifier Signature, DVS)，签名者和指定验证者拥有同等级的签名权限，除二者之外的任意第三方均无法确认签名的真实生成者，因此，当双方对签名的真伪产生争议时无法提供任何仲裁手段。1998年，Krawczyk和Rabin[3]提出的变色龙签名(Chameleon Signature, CS)更巧妙地解决了指定验证者对被签名的文件二次传递的问题。

相较于US和DVS, CS同样能够实现不可传递性，且不使用复杂的交互协议，避免了US中为设计零知识证明系统而产生的复杂性。特别地，CS通过在签名算法中嵌入变色龙哈希函数，使得持有该函数陷门的验证者获得伪造签名的能力，进而使得验证者二次传递的签名在第三方面前“失信”。此外，对于指定验证者伪造的签名，签名者有能力说服仲裁者予以拒绝，即满足签名者可拒绝性；而对于签名者真实生成的签名，签名者无法否认，即满足不可抵赖性。1984年，Shamir[4]提出基于身份的密码体制，用户的公钥可根据身份标识公开计算，相应的私钥由私钥生成器(Private Key Generator,PKG)根据身份为其派发，因此不再依赖传统公钥密码系统的数字证书。结合基于身份的密码体制的优点和变色龙签名的安全特性，基于身份的变色龙签名在云医疗系统、版权保护、电子竞拍及在线/离线签名等应用场景中尤为适用[5-8]。

基于经典数论难题的密码体制无法抵御量子计算机的攻击，这意味着后量子时代大多数现有密码方案将在多项式时间内被攻破[9,10]。具备抗量子计算攻击特性的格密码体制之所以脱颖而出，得益于格上轻量级的代数运算，且格上一些困难问题的难度存在平均情况到最坏情况的安全规约。2010年，Cash等人[11]设计出格上变色龙哈希函数。2013年，谢璇等人[12]宣称构造了格上首个CS方案，但是不满足签名者可拒绝性，且签名中必须携带的大尺寸矩阵严重影响了传输效率。2016年，Noh等人[13]构造了格上强指定验证者签名方案，缺陷是无法解决签名者和指定验证者的争议问题。2017年，Xie等人[14]提出了同态变色龙哈希函数的概念，并宣称构造了一个格上有限级数全同态签名方案，缺陷是同态变色龙哈希函数的设计存在天然的计算错误。2021年，Thanalakshmi等人[15]构造了基于哈希的CS方案，缺陷是签名者和指定验证者必须各自存储一个复杂的有向无环图，且签名的生成过程比较繁琐。

进一步地，现有的大多数CS方案在解决签名争议时，往往要求签名者向仲裁者(一个可信的第三方)出示真实的消息和签名，进而与指定验证者的伪造产生变色龙哈希函数的碰撞。由于除指定验证者外任何用户都不具备伪造的能力，这足以证明签名者未对假消息进行过签名。然而，一旦签名者发起对某个伪造的“打假”，也意味着其本欲保护的签名失去了不可传递性。

该文提出了格上基于身份的变色龙签名(Identity-Based CS, IBCS)方案，避免了文献[12]中存在的任意第三方可伪造签名和签名者无法拒绝指定验证者伪造的签名的安全性漏洞，并将最终签名的传输开销由平方级降为线性级。在此基础上，给出的变色龙签名方案2能够在签名者不暴露消息内容的条件下辅助仲裁者拒绝任意敌手伪造的签名。假设平均情况下的小整数解(Small Integer Solution, SIS)问题是困难的，在随机预言机模型下严格证明了两个方案满足抗选择身份和自适应性选择消息攻击下强不可伪造性、签名不可传递性、签名者可拒绝性和不可抵赖性，以及方案2的抗消息暴露性。

2 预备知识

2.1 格理论

2.2 基于身份的变色龙签名

令消息空间为M，身份空间为ID，随机数空间为R以及签名空间为S。基于身份的变色龙签名[5]由以下5个多项式时间算法构成：

Setup ：由 PKG运行的概率性算法。输入安全参数λ，输出公共参数 pp 和系统主私钥 msk。特别地， pp是以下算法的一个公共输入。

KeyGen： 由 PKG运行的概率性算法。输入主私钥m sk以 及身份 id∈ID， 输出与 id相 关联的私钥 skid。

Sign ：由身份为 idS的用户运行的概率性算法。输入签名者身份 idS ∈ID，指定验证者身份idV ∈ID，签名者私钥 skidS以及消息µ∈M，输出随机数r ∈R和 签名值σ ∈S。

Verify ：由身份为 idV的用户运行的确定性算法。输入签名者身份 idS ∈ID，指定验证者身份idV ∈ID，消息µ∈M，随机数r ∈R以及签名值σ ∈S，输出1或0。

Forge ：由身份为 idV的用户运行的概率性算法。输入指定验证者身份 idV ∈ID，私钥 skidV，消息µ∈M以及由签名者 idS ∈ID运行算法 Sign生成的随机数r∈R和 签名值σ ∈S， 输出新消息µ′∈M和随机数r′∈R，满足Verify(pp,idS,idV,µ′,r′,σ)→1。

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

定义4[5]若对于任意的PPT敌手A在以下游戏中的优势是可忽略的，则称IBCS是抗选择身份和自适应性选择消息攻击下强不可伪造的。挑战者C与敌手A之间的交互游戏如下：

Initial:A宣布其攻击的目标身份 idS∗∈ID和idV ∗∈ID。

Setup:C运行算法 Setup 生成公共参数 pp和主私钥 msk。C秘密持有m sk ，并将p p 发送给A。

Queries:A向C发出多项式有界次的以下询问：

(1) Key query:A适应性地询问任意身份id∈ID(除i dS∗和i dV ∗外)的私钥，C返回s kid；

(2) Sign query:A适应性地询问任意身份idi ∈ID为身份 idj ∈ID生成的关于任意消息µ∈M的签名，C返回 (µ,r,σ) ，其中 idi和 idj分别为签名者和指定验证者的身份。

Outputs:A输出一个伪造(µ∗,r∗,σ∗)∈M×R×S。A赢得游戏的前提是以下条件成立：

(1) Verify(pp,idS∗,idV ∗,µ∗,r∗,σ∗)→1；

(2)A未曾对 idS∗和 idV ∗进行过 Key query，且(µ∗,r∗,σ∗) 不是S ign query的返回。

Setup: 与定义4中相同，C生成公共参数 pp和主私钥 msk ，并将 pp 发送给A。

Challenge:A选 择目标身份 idS∗∈ID和 idV ∗∈ID。C运行算法 KeyGen 生 成私钥 skidS∗和 skidV ∗，随机选取消息µ0∈M， 运行算法Sign(pp,idS∗,idV ∗,skidS∗,µ0) 生成随机数r0∈R和签名值σ ∈S；运行算法Forge(pp,idV ∗,skidV ∗,µ0,r0,σ)生 成新消息µ1∈M和随机数r1∈R； 随机选取b ∈{0,1}， 并返回 (µb,rb,σ)。

Outputs:A输出b∗∈{0,1}。若b∗=b，则A赢得游戏。

定义6[5]若签名 (µ,r,σ)∈M×R×S为指定验证者 idV ∗∈ID伪造，且签名者 idS∗∈ID有能力说服仲裁者拒绝该签名，则称IBCS满足签名者可拒绝性；相反地，若 (µ,r,σ)∈M×R×S为签名者idS∗∈ID真实生成，且其无法否认，则称IBCS满足签名者不可抵赖性。上述两个性质可由签名者 idS∗与仲裁者之间的一个公开的拒绝协议(Denial Protocol)来保证：

对 于 idV ∗运 行 算 法 Forge 伪 造 的(µ,r,σ)∈M×R×S，idS∗可向仲裁者提交碰撞(µ′,r′,σ)：

(1) 若µ̸=µ′，且Verify(pp,idS∗,idV ∗,µ′,r′,σ)→1 ，则仲裁者断定 (µ,r,σ) 非 idS∗生成，而是idV ∗伪造；

(2) 否则，仲裁者判定 (µ,r,σ) 为 idS∗生成。

3 格上基于身份的变色龙签名

令消息空间M={0,1}m(任意消息可采用抗碰撞哈希函数映射到M)，身份空间ID={0,1}∗，随机数空间R=DZm,s以及签名空间S=DZm,s，idS ∈ID和idV ∈ID分别对应签名者和指定验证者的身份。

3.1 方案构造

(5) 运行 SamplePre(FS,TFS,h,s)，生成签名值σ ∈Zm；

(6) 输出 (µ,r,σ) ，并存储 (idV,µ,r,σ)于本地签名库。

(5) 若以上条件全部成立，输出1，否则输出0。

Forge(pp,idV,skidV,µ,r,σ)→(µ′,r′,σ):输入参数 pp ，指定验证者身份 idV，私钥 skidV=TFV以及由签名者生成的 (µ,r,σ)∈M×R×S，指定验证者执行以下操作：

(4) 输出 (µ′,r′,σ)。

3.2 安全性分析

定理1假设 SISq,m,2s√m是困难的，则本文方案满足抗选择身份和自适应性选择消息攻击下强不可伪造性。

Initial:A宣布其攻击的目标身份 idS∗∈ID和idV ∗∈ID。

Setup:C随机选取B ∈Zqn×m和可逆矩阵R∗∈Dm×m， 令A=A∗·R∗modq， 并将 (A,B)发 送给A。

H1query:A输 入 idi ∈ID， 若 idi ̸=idS∗，C查找本地密钥库是否存储( idi,Ri,Fi,TFi)。若存在，则返回H1(idi)=Ri； 否则，运行算法SampleRwithBasis(A)， 生成Ri ∈Dm×m，Fi ∈Zqn×m和Λ⊥q(Fi)的陷门TFi， 其中Fi=A·Ri1modq， 将 (idi,Ri,Fi,TFi)保存至本地密钥库，并返回H1(idi)=Ri。 若 idi=idS∗，则将 (idS∗,R∗,A∗,⊥) 保存至C的本地密钥库，并返回H1(idS∗)=R∗。

H2query:A输 入 idi,idj ∈ID和µ∈M，C查找本地密钥库是否存储 ( idi,Ri,Fi,TFior⊥)和本地签名库是否存储 (idi,idj,µ,r,σ)。若存在，则返回H2(idi,idj,bin(y))=Fi·σmodq； 否则，采用H1query生 成 (idi ̸=idS∗,Ri,Fi,TFi) 或(idi=idS∗,R∗,A∗,⊥) ，选取随机数r ∈R，计算y=CH(µ,r)=B·µ+Fj·rmodq， 随 机 选 取σ ∈DZm,s， 将(idi,idj,µ,r,σ)保 存 至 本 地 签 名 库，并 返 回H2(idi,idj,bin(y))=Fi·σmodq。

由引理5 知， SampleRwithBasis(A)的输出Ri ∈Dm×m；由引理3知，Fi·σmodq统计接近均匀分布。综上可知，H1query和H2query的返回值与真实方案中H1和H2的输出统计不可区分。

Key query:A输入 idi ∈ID， idi ̸=idS∗，idi ̸=idV ∗，C查 找密钥库 (idi,Ri,Fi,TFi)， 返回 skidi=TFi。

Sign query:A输 入 idi ∈ID， idj ∈ID( idi和idj分别对应签名者和指定验证者)和µ∈M，C查找 本 地 签 名 库 (idi,idj,µ,r,σ) ，返 回(µ,r,σ)∈M×R×S。

不失一般性，假设A在输出伪造 (µ∗,r∗,σ∗)之前向C发起过 (idS∗,idV ∗,µ∗)的H2query ，则C已在本地存储 (idS∗,idV ∗,µ∗,rµ∗,σµ∗)。

Outputs:A输 出 idS∗为 idV ∗生 成 的 一 个 伪 造(µ∗,r∗,σ∗)∈M×R×S，满足：

(1) Verify(pp,idS*,idV ∗,µ∗,r∗,σ∗)→1；

(2)A未曾对 idS∗和 idV ∗进行过 Key query，且(idS∗,idV ∗,µ∗,r∗,σ∗) 不是S ign query的返回。

当A输出伪造 (idS∗,idV ∗,µ∗,r∗,σ∗) 后，C查找本地签名库 (idS∗,idV ∗,µ∗,rµ∗,σµ∗) ，得到(µ∗,rµ∗,σµ∗) 。 由于 (µ∗,r∗,σ∗)∈M×R×S是一个成功的伪造，易知FS∗·σ∗=FS∗·σµ∗，因此：

通过以下两种情况来说明A的伪造(µ∗,r∗,σ∗)与C的本地签名库中(µ∗,rµ∗,σµ∗)不同：

(1) 若A曾发起过 (idS∗,idV ∗,µ∗) 的 Sign query，且C返回 (µ∗,rµ∗,σµ∗) 。 由于A赢得游戏的条件是输出 一 个 有 效 的 强 伪 造 签 名， 即(idS∗,idV ∗,µ∗,r∗,σ∗) 不 是 Sign query的 返 回， 因 此，σ∗̸=σµ∗；

定理2本文方案满足签名不可传递性。

证明A选择目标身份 idS∗∈ID和idV ∗∈ID。C运行 KeyGen 生成 (FS∗,TFS∗) 和 (FV ∗,TFV ∗)；随机选取µ0∈M， 运行Sign(pp,idS∗,idV ∗,TFS∗,µ0)生成r0∈R和 签 名 值σ ∈S；运 行Forge(pp,idV ∗,TFV ∗,µ0,r0,σ)生 成新消息µ1∈M和 随机数r1∈R；随 机 选 取b ∈{0,1}，并 最 终 返 回(µb,rb,σ)∈M×R×S。

在上述过程中，r0∈DZm,s，r1为运行算法SamplePre 生成。由引理6知，短向量r0和r1统计不可区分。对于(µ0,r0,σ)和 (µ1,r1,σ)， 有CH(µ0,r0)=CH(µ1,r1) ， 即B·µ0+FV ∗·r0=B·µ1+FV ∗·r1modq；又知当H2的输入相同时，其输出也一定相同。因此，算法 Verify中的条件(4)成立，即

综上可知，对敌手A而言，由挑战者C返回的关于µ0∈M和µ1∈M的变色龙签名是统计不可区分的。因此，任意敌手即使能够运行算法 Verify对签名 (µb,rb,σ)∈M×R×S进行验证，仍无法判定出真实生成者为 i dS∗∈ID或 idV ∗∈ID， 敌手A的优势是可忽略的，即。 证毕

定理3本文方案满足签名者可拒绝性和不可抵赖性。

证明对于签名者 idS∗∈ID运行 Sign生成，并发送给 idV ∗∈ID的签名 (µ,r,σ)∈M×R×S，idS∗无法对其抵赖。不妨假设 idS∗为尝试进行抵赖的签名者，根据 Denial Protocol ，签名者 idS∗需要出示一个伪造 (µ′,r′,σ)∈M×R×S。若 idS∗成功输出 (µ′̸=µ,r′,σ) ，则仲裁者可断定 (µ,r,σ)不是idS∗生成的，即 idS∗对其生成的签名抵赖成功。由于(µ′,r′,σ)∈M×R×S满足算法 V erify，则有

相反的， idS∗生成签名 (µ,r,σ)∈M×R×S，发送给指定验证者 idV ∗，而 idV ∗运行算法 Forge生成一个伪造(µ′,r′,σ)∈M×R×S。 在Denial Protocol中， idS∗可通过出示其真实生成的 (µ,r,σ)来说服仲裁者对伪造 (µ′,r′,σ)进行拒绝。由于方案是签名者不可抵赖的，即 idS∗不具备伪造其真实生成的(µ,r,σ) 的 能力，对于 idS∗出示的 (µ,r,σ)，仲裁者可完全断定是由 idS∗真实生成的；进一步地，仲裁者由µ′̸=µ可完全断定 (µ′,r′,σ) 为 idV ∗伪造。特别地，由于方案是抗选择身份和自适应性选择消息攻击下强不可伪造的， idV ∗伪造出一个 idS∗无法拒绝的(µ′,r′,σ)∈M×R×S的概率是可忽略的，即本文方案满足签名者可拒绝性。 证毕

4 格上抗消息暴露的基于身份的变色龙签名

大多数变色龙签名方案均不具备抗消息暴露安全性，即若签名者试图拒绝指定验证者伪造的签名，必须在仲裁阶段出示自己真实生成的消息和签名，这将导致签名者原本希望防止二次传递的签名被完全公开，从而造成不可传递性的失效。本节给出格上抗消息暴露的IBCS方案，使得签名者仅需出示某些不暴露真实消息和签名的信息，仍能够辅助仲裁者有效地拒绝指定验证者伪造的签名。

新方案采用对消息的随机分割策略，通过增添拒绝算法 Denial来实现签名者在仲裁阶段的抗消息暴露性。算法 Setup 和 KeyGen与已给出的格上IBCS方案中相同，将不再赘述，重点介绍新的算法设计细节。

4.1 方案构造

Setup(1λ)→(pp,msk) ：输入安全参数λ，输出公共参数 pp=(A,B,H1,H2) 和 主私钥 msk=TA。

KeyGen(pp,msk,id)→(skid): 输入参数 pp，主私钥 msk 以及身份 id∈ID，输出私钥 skid=TFid。

Sign(pp,idS,idV,skidS,µ)→(µ0,µ1,r0,r1,σ)：输入参数 pp ， 签名者身份 idS ∈ID，指定验证者身份idV ∈ID，签名者私钥 skidS=TFS以及消息µ∈{0,1}m，签名者执行以下操作：

(1) 首先查找本地签名库是否存储(idV,µ0,µ1,r0,r1,σ) ， 其 中µ0,µ1∈{0,1}m， 且µ0+µ1=µmod2。若存在，执行(6)，否则执行(2)；

(3) 随机选取µ0∈{0,1}m，计算µ1=µ0+µmod2；

(4) 随机选取r0,r1∈R， 计算关于µ0和µ1的变色龙哈希值y0=CH(µ0,r0)=B·µ0+FV·r0modq和y1=CH(µ1,r1)=B·µ1+FV·r1modq；

(5) 令h=H2(idS,idV,bin(y0,y1))，运行SamplePre(FS,TFS,h,s) ，生成签名值σ∈Zm；

(6) 输出 (µ0,µ1,r0,r1,σ) ，并存储(idV,µ0,µ1,r0,r1,σ)于本地签名库。

Verify(pp,idS,idV,µ0,r0,µ1,r1,σ)→(1 or 0)：输入参数 pp ， 签名者身份 idS ∈ID，指定验证者身份idV ∈ID，比 特 串µ0,µ1∈{0,1}m，随机 数r0,r1∈R以 及签名值σ ∈S，指定验证者执行以下操作：

4.2 安全性分析

定理4 假设 SISq,m,2s√m是困难的，则本文方案满足抗选择身份和自适应性选择消息攻击下强不可伪造性、签名不可传递性、签名者可拒绝性和不可抵赖性以及抗消息暴露性。

证明 证明思路与已给出的格上IBCS方案的安全性证明思路基本相同；因篇幅所限，将不再赘述。

5 效率分析

本文提出的两个格上IBCS方案与其他抗量子攻击的不可传递性签名方案在功能、存储与传输成本方面的对比，如表1所示。

表1 效率分析

从功能方面看，方案1结合了格密码体制和基于身份的变色龙签名的安全特性，避免了文献[12]中任意第三方可伪造签名和签名者无法拒绝指定验证者伪造的签名的安全性漏洞，弥补了格上安全的变色龙签名的空缺；解决了文献[13]中签名者与指定验证者关于签名的争议问题。方案2采用了对消息的随机分割策略，增添了新的拒绝算法，解决了方案1在仲裁阶段签名不可传递性失效的问题，获得了抗消息暴露安全性。

从存储和传输成本方面看，方案1将最终签名中的随机矩阵作为公共参数，不再由签名者每次选取后与随机数和签名值一起发送，降低了文献[12]中签名的传输代价；公共参数仅包含Zqn×m上的两个随机矩阵，最终的签名仅包含一个消息µ∈M和DZm,s上的两个短向量，减少了文献[13-15]中公共参数的存储成本，提高了签名的传输效率。方案2的签名过程采用了对消息的随机分割进行两次变色龙哈希计算和一次高斯原像采样，最终的签名仅包含两个比特串µ0∈M和µ1∈M，以及DZm,s上的3个短向量，即签名长度虽有所增加，但渐进复杂度仍与方案1相同。

综上所述，本文提出的两个方案在功能方面更加全面，获得了抗选择身份和自适应性选择消息攻击下强不可伪造性、签名不可传递性、签名者可拒绝性和不可抵赖性以及抗消息暴露性；在存储和传输成本方面，减少了公共参数的存储成本与签名生成和传输的开销，可满足轻量级设备进行数字签名的实用性需求。

6 结束语

通过结合抗量子计算攻击的格密码体制和基于身份的变色龙签名的安全特性，本文提出了格上基于身份的变色龙签名方案，弥补了格上安全的变色龙签名方案的空缺；进一步地，针对变色龙签名在仲裁阶段签名不可传递性失效的问题，提出了格上抗消息暴露的基于身份的变色龙签名方案。本文在随机预言机模型下严格证明了两个方案满足抗选择身份和自适应性选择消息攻击下强不可伪造性、签名不可传递性、签名者可拒绝性和不可抵赖性，以及方案2的抗消息暴露性。此外，给出的两个变色龙签名方案也减少了签名生成和传输的开销，符合轻量级签名的实用性需求。