A Linearly Constrained LSCM Algorithm Based on Subspace

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   格理论

定义1^[16]　设$q$, $n$和$m$为正整数，给定矩阵${\boldsymbol{A}} \in Z_q^{n \times m}$和向量${\boldsymbol{u}} \in Z_q^n$，有以下定义：

定义2^[16]　设$m$为正整数，给定${\boldsymbol{c}} \in {R^m}$和${\rho _{s,{\boldsymbol{c}}}}\left( {\boldsymbol{x}} \right) = \exp \left( { - \pi {{{{\left\| {{\boldsymbol{x}} - {\boldsymbol{c}}} \right\|}^2}} \mathord{\left/ {\vphantom {{{{\left\| {{\boldsymbol{x}} - {\boldsymbol{c}}} \right\|}^2}} {{s^2}}}} \right. } {{s^2}}}} \right)$，有以下定义：

${\mathcal{D}_{\varLambda ,s,{\boldsymbol{c}}}}\left( {\boldsymbol{x}} \right) = {{{\rho _{s,{\boldsymbol{c}}}}\left( {\boldsymbol{x}} \right)} \mathord{\left/ {\vphantom {{{\rho _{s,{\boldsymbol{c}}}}\left( {\boldsymbol{x}} \right)} {\sum\nolimits_{{\boldsymbol{x}} \in \Lambda } {{\rho _{s,{\boldsymbol{c}}}}\left( {\boldsymbol{x}} \right)} }}} \right. } {\displaystyle\sum\nolimits_{{\boldsymbol{x}} \in \varLambda } {{\rho _{s,{\boldsymbol{c}}}}\left( {\boldsymbol{x}} \right)} }}$：一个$m$维格$\varLambda$上以${\boldsymbol{c}}$为中心，$s \in {R^ + }$为高斯参数的离散高斯分布。

定义3^[16,17]　给定素数$q$，矩阵${\boldsymbol{A}} \in Z_q^{n \times m}$和实数$\beta > 0$，小整数解问题${{{\rm{SIS}}} _{q,m,\beta }}$定义为：求解齐次线性方程组${\boldsymbol{A}} \cdot {\boldsymbol{e}} = {\boldsymbol{0}}{\rm {mod}} q$的非零小尺寸整数解${\boldsymbol{e}} \in {Z^m}$，满足$0 < \left\| {\boldsymbol{e}} \right\| \le \beta$。

引理1^[16,17]　设整数$m$，实数$\beta = {{\rm{poly}}} \left( n \right)$，素数$q \ge \beta \cdot \omega \left( {\sqrt {n{{\log }_2}n} } \right)$和渐进因子$\gamma \ge \beta \cdot \tilde {\mathcal{O}}\left( {\sqrt n } \right)$，则平均情况下的${{{\rm{SIS}}} _{q,m,\beta }}$问题与最坏情况下的最短独立向量组问题${\text{SIV}}{{\text{P}}_\gamma }$的困难性是等价的。

引理2^[17-19]　设素数$q \ge 2$，存在概率多项式时间(Probabilistic Polynomial Time, PPT)算法${\text{TrapGen}}$，输入$q$，$n$和$m \ge 2n{\log _2}q$，输出${\boldsymbol{A}} \in Z_q^{n \times m}$和$\varLambda _q^ \bot \left( {\boldsymbol{A}} \right)$的一组陷门${{\boldsymbol{T}}_{\boldsymbol{A}}}$，其中${\boldsymbol{A}}$统计接近$Z_q^{n \times m}$上的均匀分布$\mathcal{U}$。

引理3^[16]　设素数$q \ge 2$，整数$m \ge 2n{\log _2}q$，参数$s \ge \omega \left( {\sqrt {{{\log }_2}m} } \right)$，若${\boldsymbol{A}} \in Z_q^{n \times m}$的列向量可生成$Z_q^n$，则对于任意的${\boldsymbol{e}} \in {\mathcal{D}_{{Z^m},s}}$，${\boldsymbol{A}} \cdot {\boldsymbol{e}}{\rm {mod}} q$统计接近$Z_q^n$上的均匀分布$\mathcal{U}$。

引理4^[20]　设素数$q > 2$，整数$m > 2n{\log _2}q$，存在PPT算法${\text{BasisDel}}$，输入${\boldsymbol{A}} \in Z_q^{n \times m}$，$R\in \mathcal{D}{m\times m}_{}$，$\varLambda _q^ \bot \left( {\boldsymbol{A}} \right)$的陷门${{\boldsymbol{T}}_{\boldsymbol{A}}}$和参数$s > \left\| {{{{\boldsymbol{\tilde T}}}_{\boldsymbol{A}}}} \right\| \cdot {s_{\boldsymbol{R}}}\sqrt m \cdot \omega \left( {\log _2^{{3 \mathord{\left/ {\vphantom {3 2}} \right. } 2}}m} \right)$，输出$\varLambda _q^ \bot \left( {{\boldsymbol{B}} = {\boldsymbol{A}} \cdot {{\boldsymbol{R}}^{ - 1}}} \right)$的陷门${{\boldsymbol{T}}_{\boldsymbol{B}}} \in {Z^{m \times m}}$，其中$\mathcal{D}{m\times m}_{}$是${Z^{m \times m}}$上${\rm {mod}} q$可逆且列向量服从${\mathcal{D}_{{Z^m},{s_{\boldsymbol{R}}}}}$的分布，${s_{\boldsymbol{R}}} = \sqrt {n{{\log }_2}q} \cdot \omega \left( {\sqrt {{{\log }_2}m} } \right)$。

引理5^[20]　设素数$q > 2$，整数$m > 2n{\log _2}q$，存在PPT算法${\text{SampleRwithBasis}}$，输入${\boldsymbol{A}} \in Z_q^{n \times m}$，输出可逆矩阵$R\in \mathcal{D}{m\times m}_{}$和$\varLambda _q^ \bot \left( {\boldsymbol{B}} \right)$的陷门${{\boldsymbol{T}}_{\boldsymbol{B}}}$，其中${\boldsymbol{B}} = {\boldsymbol{A}} \cdot {{\boldsymbol{R}}^{ - 1}}$统计接近$Z_q^{n \times m}$上的均匀分布。

引理6^[16]　设素数$q \ge 2$，整数$m \ge 2n{\log _2}q$，存在PPT算法${\text{SamplePre}}$，输入${\boldsymbol{A}} \in Z_q^{n \times m}$，$\varLambda _q^ \bot \left( {\boldsymbol{A}} \right)$的陷门${{\boldsymbol{T}}_{\boldsymbol{A}}}$，参数$s > \left\| {{{{\boldsymbol{\tilde T}}}_{\boldsymbol{A}}}} \right\| \cdot \omega \left( {\sqrt {{{\log }_2}m} } \right)$和${\boldsymbol{u}} \in Z_q^n$，输出统计接近${\mathcal{D}_{\Lambda _q^{\boldsymbol{u}}\left( {\boldsymbol{A}} \right),s}}$的短向量${\boldsymbol{e}} \in {Z^m}$，满足${\boldsymbol{u}} = {\boldsymbol{A}} \cdot {\boldsymbol{e}}{\rm {mod}} q$。

2.2   基于身份的变色龙签名

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

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

${\text{KeyGen}}$：由${{\rm{PKG}}}$运行的概率性算法。输入主私钥${\text{msk}}$以及身份${{\rm{id}}} \in \mathcal{I}\mathcal{D}$，输出与${{\rm{id}}}$相关联的私钥${{{\rm{sk}}} _{{{\rm{id}}} }}$。

${\text{Sign}}$：由身份为${{{\rm{id}}} _S}$的用户运行的概率性算法。输入签名者身份${{{\rm{id}}} _S} \in \mathcal{I}\mathcal{D}$，指定验证者身份${{{\rm{id}}} _V} \in \mathcal{I}\mathcal{D}$，签名者私钥${{{\rm{sk}}} _{{{{{\rm{id}}} }_S}}}$以及消息$\mu \in \mathcal{M}$，输出随机数$r \in \mathcal{R}$和签名值$\sigma \in \mathcal{S}$。

${\text{Verify}}$：由身份为${{{\rm{id}}} _V}$的用户运行的确定性算法。输入签名者身份${{{\rm{id}}} _S} \in \mathcal{I}\mathcal{D}$，指定验证者身份${{{\rm{id}}} _V} \in \mathcal{I}\mathcal{D}$，消息$\mu \in \mathcal{M}$，随机数$r \in \mathcal{R}$以及签名值$\sigma \in \mathcal{S}$，输出1或0。

${\text{Forge}}$：由身份为${{{\rm{id}}} _V}$的用户运行的概率性算法。输入指定验证者身份${{{\rm{id}}} _V} \in \mathcal{I}\mathcal{D}$，私钥${{{\rm{sk}}} _{{{{{\rm{id}}} }_V}}}$，消息$\mu \in \mathcal{M}$以及由签名者${{{\rm{id}}} _S} \in \mathcal{I}\mathcal{D}$运行算法${\text{Sign}}$生成的随机数$r \in \mathcal{R}$和签名值$\sigma \in \mathcal{S}$，输出新消息$\mu ' \in \mathcal{M}$和随机数$r' \in \mathcal{R}$，满足${\text{Verify}}\left( {{\rm{pp}}} ,{{{{\rm{id}}} }_S},{{{{\rm{id}}} }_V}, \mu ',r', \sigma \right) \to 1$。

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

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

${\text{Initial:}}$ $\mathcal{A}$宣布其攻击的目标身份${{{\rm{id}}} _{{S^ * }}} \in \mathcal{I}\mathcal{D}$和${{{\rm{id}}} _{{V^ * }}} \in \mathcal{I}\mathcal{D}$。

${\text{Setup:}}$ $\mathcal{C}$运行算法${\text{Setup}}$生成公共参数${{\rm{pp}}}$和主私钥${\text{msk}}$。$\mathcal{C}$秘密持有${\text{msk}}$，并将${{\rm{pp}}}$发送给$\mathcal{A}$。

${\text{Queries:}}$ $\mathcal{A}$向$\mathcal{C}$发出多项式有界次的以下询问：

(1) ${\text{Key query:}}$ $\mathcal{A}$适应性地询问任意身份${{\rm{id}}} \in \mathcal{I}\mathcal{D}$(除${{{\rm{id}}} _{{S^ * }}}$和${{{\rm{id}}} _{{V^ * }}}$外)的私钥，$\mathcal{C}$返回${{{\rm{sk}}} _{{\rm{id}}}}$；

(2) ${\text{Sign query:}}$ $\mathcal{A}$适应性地询问任意身份${{{\rm{id}}} _i} \in \mathcal{I}\mathcal{D}$为身份${{{\rm{id}}} _j} \in \mathcal{I}\mathcal{D}$生成的关于任意消息$\mu \in \mathcal{M}$的签名，$\mathcal{C}$返回$\left( {\mu ,r,\sigma } \right)$，其中${{{\rm{id}}} _i}$和${{{\rm{id}}} _j}$分别为签名者和指定验证者的身份。

${\text{Outputs:}}$ $\mathcal{A}$输出一个伪造$\left( {{\mu ^ * },{r^ * },{\sigma ^ * }} \right) \in \mathcal{M} \times \mathcal{R} \times \mathcal{S}$。$\mathcal{A}$赢得游戏的前提是以下条件成立：

(1) ${\text{Verify}}\left( {{{\rm{pp}}} ,{{{{\rm{id}}} }_{{S^ * }}},{{{{\rm{id}}} }_{{V^ * }}},{\mu ^ * },{r^ * },{\sigma ^ * }} \right) \to 1$；

(2) $\mathcal{A}$未曾对${{{\rm{id}}} _{{S^ * }}}$和${{{\rm{id}}} _{{V^ * }}}$进行过${\text{Key query}}$，且$\left( {{\mu ^ * },{r^ * },{\sigma ^ * }} \right)$不是${\text{Sign query}}$的返回。

定义5^[5]　若对于任意的PPT敌手$\mathcal{A}$在以下游戏中的优势${{\rm{Adv}}} _{{{\rm{IBCS}}} ,\mathcal{A}}^{{{\rm{non}}} - {\rm{transferability}}}$是可忽略的，则称IBCS是不可传递的。挑战者$\mathcal{C}$与敌手$\mathcal{A}$之间的交互游戏如下：

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

${\text{Challenge:}}$ $\mathcal{A}$选择目标身份${{{\rm{id}}} _{{S^ * }}} \in \mathcal{I}\mathcal{D}$和${{{\rm{id}}} _{{V^ * }}} \in \mathcal{I}\mathcal{D}$。$\mathcal{C}$运行算法${\text{KeyGen}}$生成私钥${{{\rm{sk}}} _{{{{{\rm{id}}} }_{{S^ * }}}}}$和${{{\rm{sk}}} _{{{{{\rm{id}}} }_{{V^ * }}}}}$，随机选取消息${\mu _0} \in \mathcal{M}$，运行算法${\text{Sign}}\left( {{\rm{pp}}} ,{{{{\rm{id}}} }_{{S^ * }}},{{{{\rm{id}}} }_{{V^ * }}},{{{{\rm{sk}}} }_{{{{{\rm{id}}} }_{{S^ * }}}}}, {\mu _0} \right)$生成随机数${r_0} \in \mathcal{R}$和签名值$\sigma \in \mathcal{S}$；运行算法${\text{Forge}}\left( {{{\rm{pp}}} ,{{{{\rm{id}}} }_{{V^ * }}},{{\rm{sk} }_{{{\rm{id} }_{{V^ * }}}}},{\mu _0},{r_0},\sigma } \right)$生成新消息${\mu _1} \in \mathcal{M}$和随机数${r_1} \in \mathcal{R}$；随机选取$b \in \left\{ {0,1} \right\}$，并返回$\left( {{\mu _b},{r_b},\sigma } \right)$。

${\text{Outputs:}}$ $\mathcal{A}$输出${b^ * } \in \left\{ {0,1} \right\}$。若${b^ * } = b$，则$\mathcal{A}$赢得游戏。

定义6^[5]　若签名$\left( {\mu ,r,\sigma } \right) \in \mathcal{M} \times \mathcal{R} \times \mathcal{S}$为指定验证者${{{\rm{id}}} _{{V^ * }}} \in \mathcal{I}\mathcal{D}$伪造，且签名者${{{\rm{id}}} _{{S^ * }}} \in \mathcal{I}\mathcal{D}$有能力说服仲裁者拒绝该签名，则称IBCS满足签名者可拒绝性；相反地，若$\left( {\mu ,r,\sigma } \right) \in \mathcal{M} \times \mathcal{R} \times \mathcal{S}$为签名者${{{\rm{id}}} _{{S^ * }}} \in \mathcal{I}\mathcal{D}$真实生成，且其无法否认，则称IBCS满足签名者不可抵赖性。上述两个性质可由签名者${{{\rm{id}}} _{{S^ * }}}$与仲裁者之间的一个公开的拒绝协议(${\text{Denial Protocol}}$)来保证：

对于${{{\rm{id}}} _{{V^ * }}}$运行算法${\text{Forge}}$伪造的$\left( {\mu ,r,\sigma } \right) \in \mathcal{M} \times \mathcal{R} \times \mathcal{S}$，${{{\rm{id}}} _{{S^ * }}}$可向仲裁者提交碰撞$\left( {\mu ',r',\sigma } \right)$：

(1) 若$\mu \neq \mu^{\prime}$，且${\text{Verify}}\left( {{\rm{pp}}} ,{{{{\rm{id}}} }_{{S^ * }}},{{{{\rm{id}}} }_{{V^ * }}}, \mu ',r', \sigma \right) \to 1$，则仲裁者断定$\left( {\mu ,r,\sigma } \right)$非${{{\rm{id}}} _{{S^ * }}}$生成，而是${{{\rm{id}}} _{{V^ * }}}$伪造；

(2) 否则，仲裁者判定$\left( {\mu ,r,\sigma } \right)$为${{{\rm{id}}} _{{S^ * }}}$生成。

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

令消息空间${\mathcal{M}}={\left\{0,1\right\}}^{m}$(任意消息可采用抗碰撞哈希函数映射到${\mathcal{M}}$)，身份空间$\mathcal{I}\mathcal{D} = {\left\{ {0,1} \right\}^ * }$，随机数空间$\mathcal{R} = {\mathcal{D}_{{Z^m},s}}$以及签名空间$\mathcal{S} = {\mathcal{D}_{{Z^m},s}}$，${{{\rm{id}}} _S} \in \mathcal{I}\mathcal{D}$和${{{\rm{id}}} _V} \in \mathcal{I}\mathcal{D}$分别对应签名者和指定验证者的身份。

3.1   方案构造

${\text{Setup}}\left( {{1^\lambda }} \right) \to \left( {{\text{pp}},{\text{msk}}} \right)$：输入安全参数$\lambda$，令素数$q = {{\rm{poly}}} \left( \lambda \right)$，整数$m = 2n\left\lceil {{{\log }_2}q} \right\rceil$, $n = {{\rm{poly}}} \left( \lambda \right)$，高斯参数$s = \tilde {\mathcal{O}}\left( {{n^2}} \right)$。${{\rm{PKG}}}$执行以下操作：

(1) 运行${{\rm{TrapGen}}} \left( {q,n,m} \right)$，生成${\boldsymbol{A}} \in Z_q^{n \times m}$和$\varLambda _q^ \bot \left( {\boldsymbol{A}} \right)$的陷门${{\boldsymbol{T}}_{\boldsymbol{A}}}$；

(2) 随机选取${\boldsymbol{B}} \in Z_q^{n \times m}$，作为构造变色龙哈希函数$\mathcal{C}\mathcal{H}$的公共矩阵；

(3) 选取抗碰撞哈希函数${\mathcal{H}_1}:{\left\{ {0,1} \right\}^ * } \to {\mathcal{D}_{m \times m}}$和${\mathcal{H}_2}:{\left\{ {0,1} \right\}^ * } \to Z_q^n$，其中$\mathcal{D}_{m\times m}$见引理4；

(4) 输出公共参数${{\rm{pp}}} = \left( {{\boldsymbol{A}}{\text{,}}{\boldsymbol{B}},{\mathcal{H}_1},{\mathcal{H}_2}} \right)$和系统主私钥${{\rm{msk}}} = {{\boldsymbol{T}}_{\boldsymbol{A}}}$。

${\text{KeyGen}}\left( {{{\rm{pp}}} ,{{\rm{msk}}} ,{{\rm{id}}} } \right) \to \left( {{{{{\rm{sk}}} }_{{\rm{id}}}}} \right):$输入参数${{\rm{pp}}}$，主私钥${\text{msk}}$以及身份${{\rm{id}}} \in \mathcal{I}\mathcal{D}$，${{\rm{PKG}}}$执行以下操作：

(1) 令${{\boldsymbol{R}}_{{\text{id}}}} = {\mathcal{H}_1}\left( {{{\rm{id}}} } \right) \in {\mathcal{D}_{m \times m}}$，计算${{\boldsymbol{F}}_{{id} }} = {\boldsymbol{A}} \cdot {\boldsymbol{R}}_{{{\rm{id}}} }^{ - 1} {\rm {mod}} q \in Z_q^{n \times m}$(以下将${{\boldsymbol{F}}_{{{{{\rm{id}}} }_S}}}$和${{\boldsymbol{F}}_{{{{{\rm{id}}} }_V}}}$分别简记为${{\boldsymbol{F}}_S}$和${{\boldsymbol{F}}_V}$)；

(2) 运行${\text{BasisDel}}\left( {{\boldsymbol{A}},{{\boldsymbol{R}}_{{{\rm{id}}} }},{{\boldsymbol{T}}_{\boldsymbol{A}}},s} \right)$，生成$\varLambda _q^ \bot \left( {{{\boldsymbol{F}}_{{{\rm{id}}} }}} \right)$的陷门${{\boldsymbol{T}}_{{{\boldsymbol{F}}_{{{\rm{id}}} }}}}$；

(3) 输出私钥${{{\rm{sk}}} _{{\rm{id}}}} = {{\boldsymbol{T}}_{{{\boldsymbol{F}}_{{{\rm{id}}} }}}}$。

${\text{Sign}}\left( {{{\rm{pp}}} ,{{{{\rm{id}}} }_S},{{{{\rm{id}}} }_V},{{{{\rm{sk}}} }_{{{{{\rm{id}}} }_S}}},\mu } \right) \to \left( {\mu ,{\boldsymbol{r}},{\boldsymbol{\sigma}} } \right)$：输入参数${{\rm{pp}}}$，签名者身份${{{\rm{id}}} _S} \in \mathcal{I}\mathcal{D}$，指定验证者身份${{{\rm{id}}} _V} \in \mathcal{I}\mathcal{D}$，签名者私钥${{{\rm{sk}}} _{{{\rm{id}}_S}}} = {{\boldsymbol{T}}_{{{\boldsymbol{F}}_S}}}$以及消息$\mu \in {\left\{ {0,1} \right\}^m}$，签名者执行以下操作：

(1) 首先查找本地签名库是否存储$\left( {{{{{\rm{id}}} }_V},\mu ,{\boldsymbol{r}},\sigma } \right)$，若存在，执行步骤(6)，否则执行步骤(2)；

(2) 令${{\boldsymbol{R}}_{{{{{\rm{id}}} }_S}}} = {\mathcal{H}_1}\left( {{{{{\rm{id}}} }_S}} \right)$和${{\boldsymbol{R}}_{{{{{\rm{id}}} }_V}}} = {\mathcal{H}_1}\left( {{{{{\rm{id}}} }_V}} \right)$，计算${{\boldsymbol{F}}_S} = {\boldsymbol{A}} \cdot {\boldsymbol{R}}_{{{{{\rm{id}}} }_S}}^{ - 1}{\rm {mod}} q$和${{\boldsymbol{F}}_V} = {\boldsymbol{A}} \cdot {\boldsymbol{R}}_{{{{{\rm{id}}} }_V}}^{ - 1}{\rm {mod}} q$；

(3) 随机选取${\boldsymbol{r}} \in \mathcal{R}$，计算关于${\boldsymbol{\mu}}$的变色龙哈希值${\boldsymbol{y}} = \mathcal{C}\mathcal{H}\left( {{\boldsymbol{\mu}} ,{\boldsymbol{r}}} \right) = {\boldsymbol{B}} \cdot {\boldsymbol{\mu}} + {{\boldsymbol{F}}_V} \cdot {\boldsymbol{r}}{\rm {mod}} q$；

(4) 令${\boldsymbol{h}} = {\mathcal{H}_2}\left( {{{{{\rm{id}}} }_S},{{{{\rm{id}}} }_V},{{\rm{bin}}} \left( {\boldsymbol{y}} \right)} \right)$，其中${{\rm{bin}}} \left( {\boldsymbol{y}} \right) \in {\left\{ {0,1} \right\}^{n\left\lceil {{{\log }_2}q} \right\rceil }}$为${\boldsymbol{y}} \in Z_q^n$的二进制表示；

(5) 运行${{\rm{SamplePre}}} \left( {{{\boldsymbol{F}}_S},{{\boldsymbol{T}}_{{{\boldsymbol{F}}_S}}},{\boldsymbol{h}},s} \right)$，生成签名值${\boldsymbol{\sigma}} \in {Z^m}$；

(6) 输出$\left( {\mu ,{\boldsymbol{r}},{\boldsymbol{\sigma}} } \right)$，并存储$\left( {{{{{\rm{id}}} }_V},\mu ,{\boldsymbol{r}},{\boldsymbol{\sigma}} } \right)$于本地签名库。

${\text{Verify}}\left( {{{\rm{pp}}} ,{{{{\rm{id}}} }_S},{{{{\rm{id}}} }_V},{\boldsymbol{\mu}} ,{\boldsymbol{r}},{\boldsymbol{\sigma}} } \right) \to \left( {1{\text{ or }}0} \right):$输入参数${{\rm{pp}}}$，签名者身份${{{\rm{id}}} _S} \in \mathcal{I}\mathcal{D}$，指定验证者身份${{{\rm{id}}} _V} \in \mathcal{I}\mathcal{D}$，消息${\boldsymbol{\mu}} \in {\left\{ {0,1} \right\}^m}$，随机数${\boldsymbol{r}} \in \mathcal{R}$以及签名值$\sigma \in \mathcal{S}$，指定验证者执行以下操作：

(1) 验证$0 < \left\| {\boldsymbol{r}} \right\|,\left\| {\boldsymbol{\sigma}} \right\| \le s\sqrt m$是否成立；

(2) 令${{\boldsymbol{R}}_{{{{{\rm{id}}} }_S}}} = {\mathcal{H}_1}\left( {{{{{\rm{id}}} }_S}} \right)$和${{\boldsymbol{R}}_{{{{{\rm{id}}} }_V}}} = {\mathcal{H}_1}\left( {{{{{\rm{id}}} }_V}} \right)$，计算${{\boldsymbol{F}}_S} = {\boldsymbol{A}} \cdot {\boldsymbol{R}}_{{{{{\rm{id}}} }_S}}^{ - 1}{\rm {mod}} q$和${{\boldsymbol{F}}_V} = {\boldsymbol{A}} \cdot {\boldsymbol{R}}_{{{{{\rm{id}}} }_V}}^{ - 1}{\rm {mod}} q$；

(3) 计算${\boldsymbol{y}} = \mathcal{C}\mathcal{H}\left( {{\boldsymbol{\mu}} ,{\boldsymbol{r}}} \right) = {\boldsymbol{B}} \cdot {\boldsymbol{\mu}} + {{\boldsymbol{F}}_V} \cdot {\boldsymbol{r}}{\rm {mod}} q$；

(4) 验证${{\boldsymbol{F}}_S} \cdot {\boldsymbol{\sigma}} = {\mathcal{H}_2}\left( {{{{{\rm{id}}} }_S},{{{{\rm{id}}} }_V},{{\rm{bin}}} \left( {\boldsymbol{y}} \right)} \right){\rm {mod}} q$是否成立；

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

${\text{Forge}}\left( {{{\rm{pp}}} ,{{{{\rm{id}}} }_V},{{{{\rm{sk}}} }_{{{{{\rm{id}}} }_V}}},{\boldsymbol{\mu }},{\boldsymbol{r}},{\boldsymbol{\sigma}} } \right) \to \left( {{\boldsymbol{\mu}} ',{\boldsymbol{r'}},{\boldsymbol{\sigma}} } \right):$输入参数${{\rm{pp}}}$，指定验证者身份${{{\rm{id}}} _V}$，私钥${{{\rm{sk}}} _{{{{{\rm{id}}} }_V}}} = {{\boldsymbol{T}}_{{{\boldsymbol{F}}_V}}}$以及由签名者生成的$\left( {{\boldsymbol{\mu}} ,{\boldsymbol{r}},{\boldsymbol{\sigma}} } \right) \in \mathcal{M} \times \mathcal{R} \times \mathcal{S}$，指定验证者执行以下操作：

(1) 令${{\boldsymbol{R}}_{{{{{\rm{id}}} }_V}}} = {\mathcal{H}_1}\left( {{{{{\rm{id}}} }_V}} \right)$，计算${{\boldsymbol{F}}_V} = {\boldsymbol{A}} \cdot {\boldsymbol{R}}_{{{{{\rm{id}}} }_V}}^{ - 1}{\rm {mod}} q$和${\boldsymbol{y}} = \mathcal{C}\mathcal{H}\left( {\mu ,{\boldsymbol{r}}} \right) = {\boldsymbol{B}} \cdot {\boldsymbol{\mu}} + {{\boldsymbol{F}}_V} \cdot {\boldsymbol{r}}{\rm {mod}} q$；

(2) 选取${\boldsymbol{\mu}} ' \in {\left\{ {0,1} \right\}^m}$且${\boldsymbol{\mu}} ' \ne {\boldsymbol{\mu}}$，计算${\boldsymbol{v}} = {\boldsymbol{y}} - {\boldsymbol{B}} \cdot {\boldsymbol{\mu}} '{\rm {mod}} q$；

(3) 运行${\text{SamplePre}}\left( {{{\boldsymbol{F}}_V},{{\boldsymbol{T}}_{{{\boldsymbol{F}}_V}}},{\boldsymbol{v}},s} \right)$，生成随机数${\boldsymbol{r'}} \in \mathcal{R}$；

(4) 输出$\left( {{\boldsymbol{\mu}} ',{\boldsymbol{r'}},{\boldsymbol{\sigma}} } \right)$。

3.2   安全性分析

定理1　假设${\text{SI}}{{\text{S}}_{q,m,2s\sqrt m }}$是困难的，则本文方案满足抗选择身份和自适应性选择消息攻击下强不可伪造性。

证明　假设$\mathcal{A}$为向本文方案发起攻击的PPT敌手，且能够以不可忽略的优势$\varepsilon$伪造签名，$\mathcal{C}$为试图求解${\text{SI}}{{\text{S}}_{q,m,2s\sqrt m }}$难题实例${{\boldsymbol{A}}^ * } \cdot {{\boldsymbol{e}}^ * } = {\boldsymbol{0}}{\rm {mod}} q$的挑战者，其中${{\boldsymbol{A}}^ * } \in Z_q^{n \times m}$。$\mathcal{C}$与敌手$\mathcal{A}$之间的交互游戏如下：

${\text{Initial:}}$ $\mathcal{A}$宣布其攻击的目标身份${{{\rm{id}}} _{{S^ * }}} \in \mathcal{I}\mathcal{D}$和${{{\rm{id}}} _{{V^ * }}} \in \mathcal{I}\mathcal{D}$。

${\text{Setup:}}$ $\mathcal{C}$随机选取${\boldsymbol{B}} \in Z_q^{n \times m}$和可逆矩阵${{\boldsymbol{R}}^ * } \in {\mathcal{D}_{m \times m}}$，令${\boldsymbol{A}} = {{\boldsymbol{A}}^ * } \cdot {{\boldsymbol{R}}^ * }{\rm {mod}} q$，并将$\left( {{\boldsymbol{A}},{\boldsymbol{B}}} \right)$发送给$\mathcal{A}$。

${\mathcal{H}_1} {\rm{query}}{\text{:}}$ $\mathcal{A}$输入${{{\rm{id}}} _i} \in \mathcal{I}\mathcal{D}$，若${{{\rm{id}}} _i} \ne {{{\rm{id}}} _{{S^ * }}}$，$\mathcal{C}$查找本地密钥库是否存储$\left( {{{\rm{id}}_i},{R_i},{F_i},{T_{{F_i}}}} \right)$。若存在，则返回${\mathcal{H}_{\text{1}}}\left( {{\text{i}}{{\text{d}}_i}} \right) = {{\boldsymbol{R}}_i}$；否则，运行算法${\text{SampleRwithBasis}} \left( {\boldsymbol{A}} \right)$，生成${R}_{i}\in \mathcal{D}{m\times m}_{}$，${{\boldsymbol{F}}_i} \in Z_q^{n \times m}$和$\varLambda _q^ \bot \left( {{{\boldsymbol{F}}_i}} \right)$的陷门${{\boldsymbol{T}}_{{{\boldsymbol{F}}_i}}}$，其中${{\boldsymbol{F}}_i} = {\boldsymbol{A}} \cdot {\boldsymbol{R}}_i^{ - 1}{\rm {mod}} q$，将$\left( {{\text{i}}{{\text{d}}_i},{{\boldsymbol{R}}_i},{{\boldsymbol{F}}_i},{{\boldsymbol{T}}_{{{\boldsymbol{F}}_i}}}} \right)$保存至本地密钥库，并返回${\mathcal{H}_{\text{1}}}\left( {{\text{i}}{{\text{d}}_i}} \right) = {{\boldsymbol{R}}_i}$。若${{{\rm{id}}} _i} = {{{\rm{id}}} _{{S^ * }}}$，则将$\left( {{\text{i}}{{\text{d}}_{{S^ * }}},{{\boldsymbol{R}}^ * },{{\boldsymbol{A}}^ * }, \bot } \right)$保存至$\mathcal{C}$的本地密钥库，并返回${\mathcal{H}_1}\left( {{\text{i}}{{\text{d}}_{{S^ * }}}} \right) = {{\boldsymbol{R}}^ * }$。

${\mathcal{H}_{\text{2}}}{\text{ query:}}$ $\mathcal{A}$输入${{{\rm{id}}} _i},{{{\rm{id}}} _j} \in \mathcal{I}\mathcal{D}$和${\boldsymbol{\mu}} \in \mathcal{M}$，$\mathcal{C}$查找本地密钥库是否存储$\left( {{\text{i}}{{\text{d}}_i},{{\boldsymbol{R}}_i},{{\boldsymbol{F}}_i},{{\boldsymbol{T}}_{{{\boldsymbol{F}}_i}}}{\text{or}} \bot } \right)$和本地签名库是否存储$\left( {{\text{i}}{{\text{d}}_i},{\text{i}}{{\text{d}}_j},{\boldsymbol{\mu}} ,{\boldsymbol{r}},{\boldsymbol{\sigma}} } \right)$。若存在，则返回${\mathcal{H}_2}\left( {{\text{i}}{{\text{d}}_i},{\text{i}}{{\text{d}}_j},{\text{bin}}\left( {\boldsymbol{y}} \right)} \right) = {{\boldsymbol{F}}_i} \cdot \sigma {\rm {mod}} q$；否则，采用${\mathcal{H}_1} {\rm{query}}$生成$\left( {{\text{i}}{{\text{d}}_i} \ne {\text{i}}{{\text{d}}_{{S^ * }}},{{\boldsymbol{R}}_i},{{\boldsymbol{F}}_i},{{\boldsymbol{T}}_{{{\boldsymbol{F}}_i}}}} \right)$或$\left( {\text{i}}{{\text{d}}_i} = {\text{i}}{{\text{d}}_{{S^ * }}}, {{\boldsymbol{R}}^ * }, {{\boldsymbol{A}}^ * }, \bot \right)$，选取随机数${\boldsymbol{r}} \in \mathcal{R}$，计算${\boldsymbol{y}} = \mathcal{C}\mathcal{H}\left( {{\boldsymbol{\mu }},{\boldsymbol{r}}} \right) = {\boldsymbol{B}} \cdot \mu + {{\boldsymbol{F}}_j} \cdot {\boldsymbol{r}}{\rm {mod}} q$，随机选取${\boldsymbol{\sigma}} \in {\mathcal{D}_{{Z^m},s}}$，将$\left( {{\text{i}}{{\text{d}}_i},{\text{i}}{{\text{d}}_j},\mu ,{\boldsymbol{r}},{\boldsymbol{\sigma}} } \right)$保存至本地签名库，并返回${\mathcal{H}_2}\left( {{\text{i}}{{\text{d}}_i},{\text{i}}{{\text{d}}_j},{\text{bin}}\left( {\boldsymbol{y}} \right)} \right) = {{\boldsymbol{F}}_i} \cdot \sigma {\rm {mod}} q$。

由引理5知，${\text{SampleRwithBasis}}\left( {\boldsymbol{A}} \right)$的输出${R}_{i}\in \mathcal{D}{m\times m}_{}$；由引理3知，${{\boldsymbol{F}}_i} \cdot {\boldsymbol{\sigma}} {\rm {mod}} q$统计接近均匀分布。综上可知，${\mathcal{H}_1} {\rm{query}}$和${\mathcal{H}_{\text{2}}}{\text{ query}}$的返回值与真实方案中${\mathcal{H}_1}$和${\mathcal{H}_{\text{2}}}$的输出统计不可区分。

${\text{Key query:}}$ $\mathcal{A}$输入${{{\rm{id}}} _i} \in \mathcal{I}\mathcal{D}$，${{{\rm{id}}} _i} \ne {{{\rm{id}}} _{{S^ * }}}$，${{{\rm{id}}} _i} \ne {{{\rm{id}}} _{{V^ * }}}$，$\mathcal{C}$查找密钥库$\left( {{\text{i}}{{\text{d}}_i},{{\boldsymbol{R}}_i},{{\boldsymbol{F}}_i},{{\boldsymbol{T}}_{{{\boldsymbol{F}}_i}}}} \right)$，返回${\text{s}}{{\text{k}}_{{\text{i}}{{\text{d}}_i}}} = {{\boldsymbol{T}}_{{{\boldsymbol{F}}_i}}}$。

${\text{Sign query:}}$$\mathcal{A}$输入${{{\rm{id}}} _i} \in \mathcal{I}\mathcal{D}$，${{{\rm{id}}} _j} \in \mathcal{I}\mathcal{D}$(${{{\rm{id}}} _i}$和${{{\rm{id}}} _j}$分别对应签名者和指定验证者)和${\boldsymbol{\mu}} \in \mathcal{M}$，$\mathcal{C}$查找本地签名库$\left( {{\text{i}}{{\text{d}}_i},{\text{i}}{{\text{d}}_j},{\boldsymbol{\mu}} ,{\boldsymbol{r}},{\boldsymbol{\sigma}} } \right)$，返回$\left( {{\boldsymbol{\mu}} ,{\boldsymbol{r}},{\boldsymbol{\sigma}} } \right) \in \mathcal{M} \times \mathcal{R} \times \mathcal{S}$。

不失一般性，假设$\mathcal{A}$在输出伪造$\left( {{{\boldsymbol{\mu}} ^ * },{{\boldsymbol{r}}^ * },{{\boldsymbol{\sigma}} ^ * }} \right)$之前向$\mathcal{C}$发起过$\left( {{\text{i}}{{\text{d}}_{{S^ * }}},{\text{i}}{{\text{d}}_{{V^ * }}},{{\boldsymbol{\mu}} ^ * }} \right)$的${\mathcal{H}_{\text{2}}}{\text{ query}}$，则$\mathcal{C}$已在本地存储$\left( {{\text{i}}{{\text{d}}_{{S^ * }}},{\text{i}}{{\text{d}}_{{V^ * }}},{\mu ^ * },{{\boldsymbol{r}}_{{{\boldsymbol{\mu}} ^ * }}},{{\boldsymbol{\sigma}} _{{{\boldsymbol{\mu}} ^ * }}}} \right)$。

${\text{Outputs:}}$$\mathcal{A}$输出${{{\rm{id}}} _{{S^ * }}}$为${{{\rm{id}}} _{{V^ * }}}$生成的一个伪造$\left( {{{\boldsymbol{\mu}} ^ * },{{\boldsymbol{r}}^ * },{{\boldsymbol{\sigma}} ^ * }} \right) \in \mathcal{M} \times \mathcal{R} \times \mathcal{S}$，满足：

(1) ${\text{Verify}}\left( {{\text{pp}},{\text{i}}{{\text{d}}_{{S^{\text{*}}}}},{\text{i}}{{\text{d}}_{{V^ * }}},{{\boldsymbol{\mu}} ^ * },{{\boldsymbol{r}}^ * },{{\boldsymbol{\sigma}} ^ * }} \right) \to 1$；

(2) $\mathcal{A}$未曾对${{{\rm{id}}} _{{S^ * }}}$和${{{\rm{id}}} _{{V^ * }}}$进行过${\text{Key query}}$，且$\left( {{\text{i}}{{\text{d}}_{{S^ * }}},{\text{i}}{{\text{d}}_{{V^ * }}},{{\boldsymbol{\mu}} ^ * },{{\boldsymbol{r}}^ * },{{\boldsymbol{\sigma}} ^ * }} \right)$不是${\text{Sign query}}$的返回。

当$\mathcal{A}$输出伪造$\left( {{\text{i}}{{\text{d}}_{{S^ * }}},{\text{i}}{{\text{d}}_{{V^ * }}},{{\boldsymbol{\mu}} ^ * },{{\boldsymbol{r}}^ * },{{\boldsymbol{\sigma}} ^ * }} \right)$后，$\mathcal{C}$查找本地签名库$\left( {{\text{i}}{{\text{d}}_{{S^ * }}},{\text{i}}{{\text{d}}_{{V^ * }}},{{\boldsymbol{\mu}} ^ * },{{\boldsymbol{r}}_{{\mu ^ * }}},{{\boldsymbol{\sigma}} _{{\mu ^ * }}}} \right)$，得到$\left( {{\boldsymbol{\mu}} ^ * },{{\boldsymbol{r}}_{{\mu ^ * }}}, {{\boldsymbol{\sigma}} _{{\mu ^ * }}} \right)$。由于$\left( {{{\boldsymbol{\mu}} ^ * },{{\boldsymbol{r}}^ * },{\boldsymbol{{\sigma}} ^ * }} \right) \in \mathcal{M} \times \mathcal{R} \times \mathcal{S}$是一个成功的伪造，易知${{\boldsymbol{F}}_{{S^ * }}} \cdot {{\boldsymbol{\sigma}} ^ * } = {{\boldsymbol{F}}_{{S^ * }}} \cdot {{\boldsymbol{\sigma}} _{{\mu ^ * }}}$，因此：

通过以下两种情况来说明$\mathcal{A}$的伪造$\left( {{{\boldsymbol{\mu}} ^ * },{{\boldsymbol{r}}^ * },{{\boldsymbol{\sigma}}^ * }} \right)$与$\mathcal{C}$的本地签名库中$\left( {{{\boldsymbol{\mu}} ^ * },{{\boldsymbol{r}}_{{\mu ^ * }}},{{\boldsymbol{\sigma}} _{{\mu ^ * }}}} \right)$不同：

(1) 若$\mathcal{A}$曾发起过$\left( {{\text{i}}{{\text{d}}_{{S^ * }}},{\text{i}}{{\text{d}}_{{V^ * }}},{{\boldsymbol{\mu}} ^ * }} \right)$的${\text{Sign query}}$，且$\mathcal{C}$返回$\left( {{{\boldsymbol{\mu}} ^ * },{{\boldsymbol{r}}_{{\mu ^ * }}},{{\boldsymbol{\sigma}} _{{\mu ^ * }}}} \right)$。由于$\mathcal{A}$赢得游戏的条件是输出一个有效的强伪造签名，即$\left( {\text{i}}{{\text{d}}_{{S^ * }}},{\text{i}}{{\text{d}}_{{V^ * }}}, {{\boldsymbol{\mu}} ^ * },{{\boldsymbol{r}}^ * },{{\boldsymbol{\sigma}} ^ * }\right)$不是${\text{Sign query}}$的返回，因此，${{\boldsymbol{\sigma}} ^ * } \ne {{\boldsymbol{\sigma}} _{{\mu ^ * }}}$；

(2) 若$\mathcal{A}$未发起过$\left( {{\text{i}}{{\text{d}}_{{S^ * }}},{\text{i}}{{\text{d}}_{{V^ * }}},{{\boldsymbol{\mu}} ^ * }} \right)$的${\text{Sign query}}$，由于$\mathcal{A}$曾发起过${\mathcal{H}_{\text{2}}}{\text{ query}}$，$\mathcal{C}$已存储有$\left( {{{\boldsymbol{\mu}} ^ * },{{\boldsymbol{r}}_{{\mu ^ * }}},{{\boldsymbol{\sigma}} _{{{{\mu}} ^ * }}}} \right)$，且返回${\mathcal{H}_2}\left( {{\text{i}}{{\text{d}}_{{S^ * }}},{\text{i}}{{\text{d}}_{{V^ * }}},{\text{bin}}\left( {\boldsymbol{y}} \right)} \right) = {{\boldsymbol{A}}^ * } \cdot {{\boldsymbol{\sigma}} _{{\mu ^ * }}}$。由最小熵性质^[14]可知，给定原像采样函数${f_{{{\boldsymbol{A}}^ * }}}\left( {{{\boldsymbol{e}}^ * }} \right) = {{\boldsymbol{A}}^ * } \cdot {{\boldsymbol{e}}^ * }{\rm {mod}} q$，${{\boldsymbol{e}}^ * } \in {\mathcal{D}_{{Z^m},s}}$的最小熵为$\omega \left( {{{\log }_2}n} \right)$。因此，${{\boldsymbol{\sigma}} ^ * } \ne {{\boldsymbol{\sigma}} _{{\mu ^ * }}}$以压倒性概率$1 - {2^{ - \omega \left( {{{\log }_2}n} \right)}}$成立。

综上可知，若${{\boldsymbol{\sigma}} ^ * } \ne {{\boldsymbol{\sigma}} _{{\mu ^ * }}}$，则$\mathcal{C}$可求得原像采样函数${f_{{{\boldsymbol{A}}^ * }}}\left( {{{\boldsymbol{e}}^ * }} \right) = {{\boldsymbol{A}}^ * } \cdot {{\boldsymbol{e}}^ * }{\rm {mod}} q$的一个有效碰撞$\left( {{{\boldsymbol{\sigma}} ^ * },{{\boldsymbol{\sigma}} _{{\mu ^ * }}}} \right)$，即$\mathcal{C}$能够以优势${\text{Adv}}_{{\text{IBCS}},\mathcal{A}}^{{\text{unforgeability}}} = \left( {1 - {2^{ - \omega \left( {{{\log }_2}n} \right)}}} \right) \cdot \varepsilon$输出${\text{SI}}{{\text{S}}_{q,m,2s\sqrt m }}$难题的一个有效解${{\boldsymbol{e}}^ * } = {{\boldsymbol{\sigma}} ^ * } - {{\boldsymbol{\sigma}} _{{\mu ^ * }}} \in {Z^m}$，即满足${{\boldsymbol{A}}^ * } \cdot {{\boldsymbol{e}}^ * } = {\boldsymbol{0}}{\rm {mod}} q$，且$0 < \left\| {{{\boldsymbol{e}}^ * }} \right\| \le 2s\sqrt m$。证毕

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

证明　$\mathcal{A}$选择目标身份${\text{i}}{{\text{d}}_{{S^ * }}} \in \mathcal{I}\mathcal{D}$和${\text{i}}{{\text{d}}_{{V^ * }}} \in \mathcal{I}\mathcal{D}$。$\mathcal{C}$运行${\text{KeyGen}}$生成$\left( {{{\boldsymbol{F}}_{{S^ * }}},{{\boldsymbol{T}}_{{{\boldsymbol{F}}_{{S^ * }}}}}} \right)$和$\left( {{{\boldsymbol{F}}_{{V^ * }}},{{\boldsymbol{T}}_{{{\boldsymbol{F}}_{{V^ * }}}}}} \right)$；随机选取${\mu _0} \in \mathcal{M}$，运行${\text{Sign}}\left( {{\text{pp}},{\text{i}}{{\text{d}}_{{S^ * }}},{\text{i}}{{\text{d}}_{{V^ * }}},{{\boldsymbol{T}}_{{{\boldsymbol{F}}_{{S^ * }}}}},{{\boldsymbol{\mu}} _0}} \right)$生成${{\boldsymbol{r}}_0} \in \mathcal{R}$和签名值$\sigma \in \mathcal{S}$；运行${\text{Forge}}\left( {\text{pp}},{\text{i}}{{\text{d}}_{{V^ * }}}, {{\boldsymbol{T}}_{{{\boldsymbol{F}}_{{V^ * }}}}},{{\boldsymbol{\mu}} _0},{{\boldsymbol{r}}_0},{\boldsymbol{\sigma}} \right)$生成新消息${{\boldsymbol{\mu}} _1} \in \mathcal{M}$和随机数${{\boldsymbol{r}}_1} \in \mathcal{R}$；随机选取$b \in \left\{ {0,1} \right\}$，并最终返回$\left( {{{\boldsymbol{\mu}} _b},{{\boldsymbol{r}}_b},{\boldsymbol{\sigma}} } \right) \in \mathcal{M} \times \mathcal{R} \times \mathcal{S}$。

在上述过程中，${{\boldsymbol{r}}_0} \in {\mathcal{D}_{{Z^m},s}}$，${{\boldsymbol{r}}_1}$为运行算法${\text{SamplePre}}$生成。由引理6知，短向量${{\boldsymbol{r}}_0}$和${{\boldsymbol{r}}_1}$统计不可区分。对于$\left( {{{\boldsymbol{\mu}} _0},{{\boldsymbol{r}}_0},{\boldsymbol{\sigma}} } \right)$和$\left( {{{\boldsymbol{\mu}} _1},{{\boldsymbol{r}}_1},{\boldsymbol{\sigma}} } \right)$，有$\mathcal{C}\mathcal{H}\left( {{{\boldsymbol{\mu}} _0},{{\boldsymbol{r}}_0}} \right) = \mathcal{C}\mathcal{H}\left( {{{\boldsymbol{\mu}} _1},{{\boldsymbol{r}}_1}} \right)$，即${\boldsymbol{B}} \cdot {{\boldsymbol{\mu}} _0} + {{\boldsymbol{F}}_{{V^ * }}} \cdot {{\boldsymbol{r}}_0} = {\boldsymbol{B}} \cdot {{\boldsymbol{\mu}} _1} + {{\boldsymbol{F}}_{{V^ * }}} \cdot {{\boldsymbol{r}}_1}{\rm {mod}} q$；又知当${\mathcal{H}_2}$的输入相同时，其输出也一定相同。因此，算法${\text{Verify}}$中的条件(4)成立，即

综上可知，对敌手$\mathcal{A}$而言，由挑战者$\mathcal{C}$返回的关于${{\boldsymbol{\mu}} _0} \in \mathcal{M}$和${{\boldsymbol{\mu }}_1} \in \mathcal{M}$的变色龙签名是统计不可区分的。因此，任意敌手即使能够运行算法${\text{Verify}}$对签名$\left( {{{\boldsymbol{\mu}} _b},{{\boldsymbol{r}}_b},{\boldsymbol{\sigma}} } \right) \in \mathcal{M} \times \mathcal{R} \times \mathcal{S}$进行验证，仍无法判定出真实生成者为${\text{i}}{{\text{d}}_{{S^ * }}} \in \mathcal{I}\mathcal{D}$或${\text{i}}{{\text{d}}_{{V^ * }}} \in \mathcal{I}\mathcal{D}$，敌手$\mathcal{A}$的优势是可忽略的，即${\text{Adv}}_{{\text{IBCS}},\mathcal{A}}^{{\text{non-transferability}}} \approx 0$。 证毕

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

证明　对于签名者${\text{i}}{{\text{d}}_{{S^ * }}} \in \mathcal{I}\mathcal{D}$运行${\text{Sign}}$生成，并发送给${\text{i}}{{\text{d}}_{{V^ * }}} \in \mathcal{I}\mathcal{D}$的签名$\left( {{\boldsymbol{\mu}} ,{\boldsymbol{r}},{\boldsymbol{\sigma}} } \right) \in \mathcal{M} \times \mathcal{R} \times \mathcal{S}$，${\text{i}}{{\text{d}}_{{S^ * }}}$无法对其抵赖。不妨假设${\text{i}}{{\text{d}}_{{S^ * }}}$为尝试进行抵赖的签名者，根据${\text{Denial Protocol}}$，签名者${\text{i}}{{\text{d}}_{{S^ * }}}$需要出示一个伪造$\left( {{\boldsymbol{\mu}} ',{\boldsymbol{r'}},{\boldsymbol{\sigma}} } \right) \in \mathcal{M} \times \mathcal{R} \times \mathcal{S}$。若${\text{i}}{{\text{d}}_{{S^ * }}}$成功输出$\left( {{\boldsymbol{\mu}} ' \ne {\boldsymbol{\mu}} ,{\boldsymbol{r'}},{\boldsymbol{\sigma}} } \right)$，则仲裁者可断定$\left( {{\boldsymbol{\mu}} ,{\boldsymbol{r}},{\boldsymbol{\sigma}} } \right)$不是${\text{i}}{{\text{d}}_{{S^ * }}}$生成的，即${\text{i}}{{\text{d}}_{{S^ * }}}$对其生成的签名抵赖成功。由于$\left( {{\boldsymbol{\mu}} ',{\boldsymbol{r'}},{\boldsymbol{\sigma}} } \right) \in \mathcal{M} \times \mathcal{R} \times \mathcal{S}$满足算法${\text{Verify}}$，则有

综上可知，签名者${\text{i}}{{\text{d}}_{{S^ * }}}$可求得${\text{SI}}{{\text{S}}_{q,2m,2s\sqrt m }}$难题实例$\left( {{\boldsymbol{B}},{{\boldsymbol{F}}_{{V^ * }}}} \right) \cdot {\boldsymbol{e}} = 0{\rm {mod}} q$的一个解${\boldsymbol{e}} = \left( {\begin{array}{*{20}{c}} {{\boldsymbol{\mu}} - {\boldsymbol{\mu}} '} \\ {{\boldsymbol{r}} - {\boldsymbol{r'}}} \end{array}} \right) \in {Z^{2m}}$，且$0 < \left\| {\boldsymbol{e}} \right\| \le 2s\sqrt m$。由引理1知，这与${\text{i}}{{\text{d}}_{{S^ * }}}$没有$\varLambda _q^ \bot \left( {{\boldsymbol{B}},{{\boldsymbol{F}}_{{V^ * }}}} \right)$的任何陷门信息仍求得${\text{SI}}{{\text{S}}_{q,2m,2s\sqrt m }}$难题实例的一个有效解相矛盾，即本文方案满足签名者不可抵赖性。

相反的，${\text{i}}{{\text{d}}_{{S^ * }}}$生成签名$\left( {{\boldsymbol{\mu}} ,{\boldsymbol{r}},{\boldsymbol{\sigma}} } \right) \in \mathcal{M} \times \mathcal{R} \times \mathcal{S}$，发送给指定验证者${\text{i}}{{\text{d}}_{{V^ * }}}$，而${\text{i}}{{\text{d}}_{{V^ * }}}$运行算法${\text{Forge}}$生成一个伪造$\left( {{\boldsymbol{\mu}} ',{\boldsymbol{r'}},{\boldsymbol{\sigma}} } \right) \in \mathcal{M} \times \mathcal{R} \times \mathcal{S}$。在${\text{Denial Protocol}}$中，${\text{i}}{{\text{d}}_{{S^ * }}}$可通过出示其真实生成的$\left( {{\boldsymbol{\mu}} ,{\boldsymbol{r}},{\boldsymbol{\sigma}} } \right)$来说服仲裁者对伪造$\left( {{\boldsymbol{\mu}} ',{\boldsymbol{r'}},{\boldsymbol{\sigma}} } \right)$进行拒绝。由于方案是签名者不可抵赖的，即${\text{i}}{{\text{d}}_{{S^ * }}}$不具备伪造其真实生成的$\left( {{\boldsymbol{\mu}} ,{\boldsymbol{r}},{\boldsymbol{\sigma}} } \right)$的能力，对于${\text{i}}{{\text{d}}_{{S^ * }}}$出示的$\left( {{\boldsymbol{\mu}} ,{\boldsymbol{r}},{\boldsymbol{\sigma}} } \right)$，仲裁者可完全断定是由${\text{i}}{{\text{d}}_{{S^ * }}}$真实生成的；进一步地，仲裁者由$\mu ' \ne \mu$可完全断定$\left( {{\boldsymbol{\mu}} ',{\boldsymbol{r'}},{\boldsymbol{\sigma}} } \right)$为${\text{i}}{{\text{d}}_{{V^ * }}}$伪造。特别地，由于方案是抗选择身份和自适应性选择消息攻击下强不可伪造的，${\text{i}}{{\text{d}}_{{V^ * }}}$伪造出一个${\text{i}}{{\text{d}}_{{S^ * }}}$无法拒绝的$\left( {{\boldsymbol{\mu}} ',{\boldsymbol{r'}},{\boldsymbol{\sigma}} } \right) \in \mathcal{M} \times \mathcal{R} \times \mathcal{S}$的概率是可忽略的，即本文方案满足签名者可拒绝性。证毕

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

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

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

4.1   方案构造

${\text{Setup}}\left( {{1^\lambda }} \right) \to \left( {{\text{pp}},{\text{msk}}} \right)$：输入安全参数$\lambda$，输出公共参数${\text{pp}} = \left( {{\boldsymbol{A}}{\text{,}}{\boldsymbol{B}},{\mathcal{H}_1},{\mathcal{H}_2}} \right)$和主私钥${\text{msk}} = {{\boldsymbol{T}}_{\boldsymbol{A}}}$。

${\text{KeyGen}}\left( {{\text{pp}},{\text{msk}},{\text{id}}} \right) \to \left( {{\text{s}}{{\text{k}}_{{\text{id}}}}} \right):$输入参数${\text{pp}}$，主私钥${\text{msk}}$以及身份${\text{id}} \in \mathcal{I}\mathcal{D}$，输出私钥${\text{s}}{{\text{k}}_{{\text{id}}}} = {{\boldsymbol{T}}_{{{\boldsymbol{F}}_{{\text{id}}}}}}$。

${\text{Sign}}\left( {{\text{pp}},{\text{i}}{{\text{d}}_S},{\text{i}}{{\text{d}}_V},{\text{s}}{{\text{k}}_{{\text{i}}{{\text{d}}_S}}},{\boldsymbol{\mu}} } \right) \to \left( {{{\boldsymbol{\mu}} _0},{{\boldsymbol{\mu}} _1},{{\boldsymbol{r}}_0},{{\boldsymbol{r}}_1},{\boldsymbol{\sigma}} } \right)$：输入参数${\text{pp}}$，签名者身份${\text{id}}_{S}\in \mathcal{ID}$，指定验证者身份${\text{id}}_{V}\in \mathcal{ID}$，签名者私钥${\text{s}}{{\text{k}}_{{\text{i}}{{\text{d}}_S}}} = {{\boldsymbol{T}}_{{{\boldsymbol{F}}_S}}}$以及消息$\mu \in {\left\{ {0,1} \right\}^m}$，签名者执行以下操作：

(1) 首先查找本地签名库是否存储$\left( {\text{i}}{{\text{d}}_V},{{\boldsymbol{\mu}} _0},{{\boldsymbol{\mu}} _1}, {{\boldsymbol{r}}_0},{{\boldsymbol{r}}_1},{\boldsymbol{\sigma}} \right)$，其中${{\boldsymbol{\mu}} _0},{{\boldsymbol{\mu}} _1} \in {\left\{ {0,1} \right\}^m}$，且${{\boldsymbol{\mu}} _0} + {{\boldsymbol{\mu}} _1} = {\boldsymbol{\mu}} {\rm {mod}} 2$。若存在，执行(6)，否则执行(2)；

(2) 令${{\boldsymbol{R}}_{{\text{i}}{{\text{d}}_S}}} = {\mathcal{H}_1}\left( {{\text{i}}{{\text{d}}_S}} \right)$和${{\boldsymbol{R}}_{{\text{i}}{{\text{d}}_V}}} = {\mathcal{H}_1}\left( {{\text{i}}{{\text{d}}_V}} \right)$，计算${{\boldsymbol{F}}_S} = {\boldsymbol{A}} \cdot {\boldsymbol{R}}_{{\text{i}}{{\text{d}}_S}}^{ - 1}{\rm {mod}} q$和${{\boldsymbol{F}}_V} = {\boldsymbol{A}} \cdot {\boldsymbol{R}}_{{\text{i}}{{\text{d}}_V}}^{ - 1}{\rm {mod}} q$；

(3) 随机选取${{\boldsymbol{\mu}} _0} \in {\left\{ {0,1} \right\}^m}$，计算${{\boldsymbol{\mu}} _1} \,=\, {{\boldsymbol{\mu}} _0} \,+ {\boldsymbol{\mu}} {\rm {mod}} 2$；

(4) 随机选取${{\boldsymbol{r}}_0},{{\boldsymbol{r}}_1} \in \mathcal{R}$，计算关于${{\boldsymbol{\mu}} _0}$和${{\boldsymbol{\mu}} _1}$的变色龙哈希值${{\boldsymbol{y}}_0} = \mathcal{C}\mathcal{H}\left( {{{\boldsymbol{\mu}} _0},{{\boldsymbol{r}}_0}} \right) = {\boldsymbol{B}} \cdot {{\boldsymbol{\mu}} _0} + {{\boldsymbol{F}}_V} \cdot {{\boldsymbol{r}}_0}{\rm {mod}} q$和${{\boldsymbol{y}}_1} = \mathcal{C}\mathcal{H}\left( {{\mu _1},{{\boldsymbol{r}}_1}} \right) = {\boldsymbol{B}} \cdot {\mu _1} + {{\boldsymbol{F}}_V} \cdot {{\boldsymbol{r}}_1}{\rm {mod}} q$；

(5) 令${\boldsymbol{h}} = {\mathcal{H}_2}\left( {{\text{i}}{{\text{d}}_S},{\text{i}}{{\text{d}}_V},{\text{bin}}\left( {{{\boldsymbol{y}}_0},{{\boldsymbol{y}}_1}} \right)} \right)$，运行${{\rm{SamplePre}}} \left( {{{\boldsymbol{F}}_S},{{\boldsymbol{T}}_{{{\boldsymbol{F}}_S}}},{\boldsymbol{h}},s} \right)$，生成签名值 ${\boldsymbol{\sigma}} \in {Z^m}$；

(6) 输出$\left( {{{\boldsymbol{\mu}} _0},{{\boldsymbol{\mu}} _1},{{\boldsymbol{r}}_0},{{\boldsymbol{r}}_1},{\boldsymbol{\sigma}} } \right)$，并存储$\left({\text{i}}{{\text{d}}_V},{{\boldsymbol{\mu}} _0}, {{\boldsymbol{\mu}} _1},{{\boldsymbol{r}}_0}, {{\boldsymbol{r}}_1},{\boldsymbol{\sigma}} \right)$于本地签名库。

${\text{Verify}}\left( {{\text{pp}},{\text{i}}{{\text{d}}_S},{\text{i}}{{\text{d}}_V},{{\boldsymbol{\mu}} _0},{{\boldsymbol{r}}_0},{{\boldsymbol{\mu}} _1},{{\boldsymbol{r}}_1},{\boldsymbol{\sigma}} } \right) \to \left( {1{\text{ or }}0} \right)$：输入参数${\text{pp}}$，签名者身份${\text{id}}_{S}\in \mathcal{ID}$，指定验证者身份${\text{id}}_{V}\in \mathcal{ID}$，比特串${{\boldsymbol{\mu}} _0},{{\boldsymbol{\mu}} _1} \in {\left\{ {0,1} \right\}^m}$，随机数${{\boldsymbol{r}}_0},{{\boldsymbol{r}}_1} \in \mathcal{R}$以及签名值${\boldsymbol{\sigma}} \in \mathcal{S}$，指定验证者执行以下操作：

(1) 验证$0 < \left\| {{{\boldsymbol{r}}_0}} \right\|,\left\| {{{\boldsymbol{r}}_1}} \right\|,\left\| {\boldsymbol{\sigma}} \right\| \le s\sqrt m$是否成立；

(2) 令${{\boldsymbol{R}}_{{\text{i}}{{\text{d}}_S}}} = {\mathcal{H}_1}\left( {{\text{i}}{{\text{d}}_S}} \right)$和${{\boldsymbol{R}}_{{\text{i}}{{\text{d}}_V}}} = {\mathcal{H}_1}\left( {{\text{i}}{{\text{d}}_V}} \right)$，计算${{\boldsymbol{F}}_S} = {\boldsymbol{A}} \cdot {\boldsymbol{R}}_{{\text{i}}{{\text{d}}_S}}^{ - 1}{\rm {mod}} q$和${{\boldsymbol{F}}_V} = {\boldsymbol{A}} \cdot {\boldsymbol{R}}_{{\text{i}}{{\text{d}}_V}}^{ - 1}{\rm {mod}} q$；

(3) 计算${{\boldsymbol{y}}_0} = \mathcal{C}\mathcal{H}\left( {{{\boldsymbol{\mu}} _0},{{\boldsymbol{r}}_0}} \right) = {\boldsymbol{B}} \cdot {{\boldsymbol{\mu}} _0} + {{\boldsymbol{F}}_V} \cdot {{\boldsymbol{r}}_0}{\rm {mod}} q$和${{\boldsymbol{y}}_1} = \mathcal{C}\mathcal{H}\left( {{{\boldsymbol{\mu}} _1},{{\boldsymbol{r}}_1}} \right) = {\boldsymbol{B}} \cdot {{\boldsymbol{\mu}} _1} + {{\boldsymbol{F}}_V} \cdot {{\boldsymbol{r}}_1}{\rm {mod}} q$；

(4) 验证${{\boldsymbol{F}}_S} \cdot {\boldsymbol{\sigma}} = {\mathcal{H}_2}\left( {{\text{i}}{{\text{d}}_S},{\text{i}}{{\text{d}}_V},{\text{bin}}\left( {{{\boldsymbol{y}}_0},{{\boldsymbol{y}}_1}} \right)} \right)$是否成立；

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

${\text{Forge}}$ $\left( {{\text{pp}},{\text{i}}{{\text{d}}_V},{\text{s}}{{\text{k}}_{{\text{i}}{{\text{d}}_V}}},{{\boldsymbol{\mu}} _0},{{\boldsymbol{\mu}} _1},{{\boldsymbol{r}}_0},{{\boldsymbol{r}}_1},\sigma } \right) \to$$\left( {{{\boldsymbol{\mu}} '}_b}, {{\boldsymbol{\mu}} _{1{{ - }}b}}, {{{\boldsymbol{r'}}}_b},{{\boldsymbol{r}}_{1 - b}},{\boldsymbol{\sigma}} \right)$：输入参数${\text{pp}}$，指定验证者身份${\text{i}}{{\text{d}}_V}$，私钥${\text{s}}{{\text{k}}_{{\text{i}}{{\text{d}}_V}}} = {{\boldsymbol{T}}_{{{\boldsymbol{F}}_V}}}$以及由签名者生成的$\left( {{{\boldsymbol{\mu}} _0},{{\boldsymbol{\mu}} _1},{{\boldsymbol{r}}_0},{{\boldsymbol{r}}_1},{\boldsymbol{\sigma}} } \right) \in {\mathcal{M}^2} \times {\mathcal{R}^2} \times \mathcal{S}$，指定验证者执行以下操作：

(1) 令${{\boldsymbol{R}}_{{\text{i}}{{\text{d}}_V}}} = {\mathcal{H}_1}\left( {{\text{i}}{{\text{d}}_V}} \right)$，计算${{\boldsymbol{F}}_V} = {\boldsymbol{A}} \cdot {\boldsymbol{R}}_{{\text{i}}{{\text{d}}_V}}^{ - 1} {\rm {mod}} q$；

(2) 选取$b \in \left\{ {0,1} \right\}$和${{\boldsymbol{\mu}} '_b} \in {\left\{ {0,1} \right\}^m}$，其中${{\boldsymbol{\mu}} '_b} \ne {{\boldsymbol{\mu}} _b}$；

(3) 计算${{\boldsymbol{y}}_b} = \mathcal{C}\mathcal{H}\left( {{{\boldsymbol{\mu}} _b},{{\boldsymbol{r}}_b}} \right) = {\boldsymbol{B}} \cdot {{\boldsymbol{\mu}} _b} + {{\boldsymbol{F}}_V} \cdot {{\boldsymbol{r}}_b}{\rm {mod}} q$和${\boldsymbol{v}} = {{\boldsymbol{y}}_b} - {\boldsymbol{B}} \cdot {\mu '_b}{\rm {mod}} q$；

(4) 运行${\text{SamplePre}}\left( {{{\boldsymbol{F}}_V},{{\boldsymbol{T}}_{{{\boldsymbol{F}}_V}}},{\boldsymbol{v}},s} \right)$，生成随机数${{\boldsymbol{r'}}_b} \in \mathcal{R}$；

(5) 输出$\left( {{{{\boldsymbol{\mu}} '}_b},{{\boldsymbol{\mu}} _{1{\text{ - }}b}},{{{\boldsymbol{r'}}}_b},{{\boldsymbol{r}}_{1 - b}},{\boldsymbol{\sigma}} } \right)$。

请注意：在上述算法中，指定验证者${\text{i}}{{\text{d}}_V}$最终伪造的消息为${\boldsymbol{\mu}} ' = {{\boldsymbol{\mu}} _{1{-}b}} + {{\boldsymbol{\mu}} '_b}{\rm {mod}} 2$。事实上，${\text{i}}{{\text{d}}_V}$也可以同时任意选取${{\boldsymbol{\mu}} '_0} \in {\left\{ {0,1} \right\}^m}$和${{\boldsymbol{\mu}} '_1} \in {\left\{ {0,1} \right\}^m}$来进行伪造，此时，${\text{i}}{{\text{d}}_V}$最终伪造的消息为${\boldsymbol{\mu}} ' = {{\boldsymbol{\mu}} '_0} + {{\boldsymbol{\mu}} '_1}{\rm {mod}} 2$。

${\text{Denial}}\left( {{\text{pp}},{\text{i}}{{\text{d}}_S},{\text{i}}{{\text{d}}_V},{{{\boldsymbol{\mu}} '}_0},{{{\boldsymbol{\mu}} '}_1},{{{\boldsymbol{r'}}}_0},{{{\boldsymbol{r'}}}_1},{\boldsymbol{\sigma}} } \right) \to \left( {1{\text{ or }}0} \right)$：输入参数${\text{pp}}$，签名者身份${\text{i}}{{\text{d}}_S}$，指定验证者身份${\text{i}}{{\text{d}}_V}$以及由指定验证者伪造的$\left( {{{{\boldsymbol{\mu}} '}_0},{{{\boldsymbol{\mu}} '}_1},{{{\boldsymbol{r'}}}_0},{{{\boldsymbol{r'}}}_1},{\boldsymbol{\sigma}} } \right) \in {\mathcal{M}^2} \times {\mathcal{R}^2} \times \mathcal{S}$，签名者和仲裁者执行以下操作：

(1) 签名者查找本地签名库$\left( {{\rm{id}}_V},{{\boldsymbol{\mu}} _0},{{\boldsymbol{\mu}} _1},{{\boldsymbol{r}}_0}, {{\boldsymbol{r}}_1},{\boldsymbol{\sigma}} \right)$，其中${{\boldsymbol{\mu}} _0} \ne {{\boldsymbol{\mu}} '_0}$或${{\boldsymbol{\mu}} _1} \ne {{\boldsymbol{\mu}} '_1}$；

(2) 不失一般性，假设${{\boldsymbol{\mu}} _0} \ne {{\boldsymbol{\mu}} '_0}$，签名者输出碰撞$\left( {{{\boldsymbol{\mu}} _0},{{\boldsymbol{r}}_0}} \right)$；

(3) 仲裁者验证${{\boldsymbol{\mu}} _0} \ne {{\boldsymbol{\mu}} '_0}$和$\mathcal{C}\mathcal{H}\left( {{{\boldsymbol{\mu}} _0},{{\boldsymbol{r}}_0}} \right) = \mathcal{C}\mathcal{H}\left( {{{{\boldsymbol{\mu}} '}_0},{{{\boldsymbol{r'}}}_0}} \right)$是否成立；

(4) 若以上条件全部成立，仲裁者输出1，即断定$\left( {{{{\boldsymbol{\mu}} '}_0},{{{\boldsymbol{\mu}} '}_1},{{{\boldsymbol{r'}}}_0},{{{\boldsymbol{r'}}}_1},{\boldsymbol{\sigma}} } \right)$是由指定验证者伪造的，否则输出$0$。

4.2   安全性分析

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

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

5.   效率分析

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

表  1  效率分析

方案	公共参数长度	签名长度	不可伪造性	不可传递性	可拒绝性	不可抵赖性	抗消息暴露性	安全模型
文献[12]	$\tilde {\mathcal{O} }\left( { {n^2} } \right)$	$\tilde {\mathcal{O}}\left( {{n^2}} \right)$	$\times$	$\surd$	$\times$	$\surd$	$\times$	随机预言机
文献[13]	$\tilde {\mathcal{O}}\left( {{n^3}} \right)$	$\tilde {\mathcal{O}}\left( {{n^2}} \right)$	$\surd$	$\surd$	$\times$	$\surd$	$\times$	标准
文献[14]	$\tilde {\mathcal{O}}\left( {{k_0} \cdot {n^2}} \right)$	$\tilde {\mathcal{O}}\left( {{n^2}} \right)$	$\surd$	$\times$	$-$	$-$	$-$	标准
文献[15]	$\tilde {\mathcal{O}}\left( {{n^2}} \right)$	$\tilde {\mathcal{O}}\left( {{k_1} \cdot n} \right)$	$\surd$	$\surd$	$\surd$	$\surd$	$\times$	随机预言机
本文方案1	$\tilde {\mathcal{O}}\left( {{n^2}} \right)$	$\tilde {\mathcal{O}}\left( n \right)$	$\surd$	$\surd$	$\surd$	$\surd$	$\times$	随机预言机
本文方案2	$\tilde {\mathcal{O}}\left( {{n^2}} \right)$	$\tilde {\mathcal{O}}\left( n \right)$	$\surd$	$\surd$	$\surd$	$\surd$	$\surd$	随机预言机
注：${k_0}$表示同态计算的数据集尺寸，${k_1}$表示有向无环图的内部顶点数；$\times$表示不满足，$\surd$表示满足，$-$表示不考虑。

下载: 导出CSV 

| 显示表格

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

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

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

6.   结束语

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