Loading [MathJax]/jax/element/mml/optable/GeneralPunctuation.js

线性磁场下高阶反铁磁链的孤子研究

杨宇萍, 陈浩, 王瑞强

杨宇萍, 陈浩, 王瑞强. 线性磁场下高阶反铁磁链的孤子研究[J]. 华南师范大学学报(自然科学版), 2018, 50(3): 8-13. DOI: 10.6054/j.jscnun.2017020
引用本文: 杨宇萍, 陈浩, 王瑞强. 线性磁场下高阶反铁磁链的孤子研究[J]. 华南师范大学学报(自然科学版), 2018, 50(3): 8-13. DOI: 10.6054/j.jscnun.2017020
YANG Y P, CHEN H, WANG R Q. Solition in the high-order anti-ferromagnetic chain under the influnce of linear magnetic field[J]. Journal of South China Normal University (Natural Science Edition), 2018, 50(3): 8-13. DOI: 10.6054/j.jscnun.2017020
Citation: YANG Y P, CHEN H, WANG R Q. Solition in the high-order anti-ferromagnetic chain under the influnce of linear magnetic field[J]. Journal of South China Normal University (Natural Science Edition), 2018, 50(3): 8-13. DOI: 10.6054/j.jscnun.2017020

线性磁场下高阶反铁磁链的孤子研究

基金项目: 

国家自然科学基金项目(11474106)

详细信息
    作者简介:

    陈浩,教授,Email: chenhao@scnu.edu.cn.

    通讯作者:

    陈浩,教授,Email: chenhao@scnu.edu.cn.

  • 中图分类号: O482.51;O175.14

Solition in the high-order anti-ferromagnetic chain under the influnce of linear magnetic field

Funds: 

国家自然科学基金项目(11474106)

  • 摘要: 基于一维反铁磁链的双格子模型,采用相干态方法,分析了在线性外磁场作用下,将反铁磁的哈密顿量的准至算符扩展到6次项时对一维反铁磁链的孤子所产生的影响. 推导出非线性方程,采用扩展行波法,得到非线性方程的解和孤子的相关特性. 结果表明:外磁场的引入会影响孤子的运动状态,改变其能量,而将哈密顿量准至算符扩展到6次项则会对孤子的稳定性、宽度、峰值产生显著的影响.
    Abstract: On the basis of the double-subattice model of the one-dimensional anti-ferromagnetic chain, this study uses the coherent state ansatz to analyze the influence of the linear magnetic field on the solition in one-dimensional antiferromagnetic chain when its Hamiltonian boson operator is expanded to six items. A nonlinear equation is derived, and with the travelling wave solution method the analytical solution of the equation as well as the related properties of solition is obtained. The results indicate that the introduction of the linear magnetic field can affect the motion state of the solition and change its energy. Additionally, the expansion of the Hamiltonian boson operator to six items can affect the stability, width and peak of the solition.
  • 多重签名[1]允许一组签名者联合对同一消息进行签名,生成一个压缩的多重签名且验证者只需验证最终签名便可确认多个签名者对同一消息进行了签名[2].自1983年ITAKURA和NAKAMURA[1]提出多重签名的概念以来,多重签名的方案设计得到了充分研究,这些方案的安全性可归约于大整数分解问题[3-4]、离散对数问题[5-7]及格上困难问题[8].多重签名应用广泛,适用于电子合同、文件签署、电子商务和电子政务等众多领域[9].

    2008年,BAGHERZANDI等[6]提出了基于离散对数的两轮多重签名BCJ方案,并在公钥验证模型下证明方案的安全性;2010年,MA等[7]提出了可在普通公钥模型下证明安全的两轮多重签名MWLD方案,其安全性可归约为求解离散对数问题;2016年,SYTA等[10]提出了具有较好扩展性的两轮多重签名CoSi方案,并认为该方案的安全性可归约为求解离散对数的困难性,但未给出方案的形式化安全证明;2018年,MAXWELL等[11]提出了第一个支持公钥聚合功能的两轮多重签名MuSig方案,并在普通公钥模型下证明方案的安全性.

    然而,DRIJVERS等[12]指出BCJ方案[6]、MWLD方案[7]、CoSi方案[10]以及MuSig方案[11]存在的安全缺陷,并依次针对这4个方案的安全漏洞进行了亚指数时间攻击;同时,基于BCJ方案,提出了首个可形式化证明安全且只需2轮通信的mBCJ方案,其安全性可归约于求解离散对数的困难性. mBCJ方案采用了具有二义性的同态承诺,其中同态承诺可实现MS-BN方案[5]中前2轮通信的效果,进一步降低多重签名方案的通信代价;二义性的同态承诺能够有效避免伪造者从归约中抽取签名私钥,从而求解离散对数问题的具体实例,保证了mBCJ方案的安全性.然而,基于离散对数问题构造的方案不能抵抗量子攻击,因此,mBCJ方案不适用于量子时代多方合作签名场景.

    基于格上困难问题构造的方案能够抵抗量子攻击,满足了人们对方案安全性的最新需求.在构造格上两轮多重签名方案时,本可沿用与mBCJ方案相似的构造思路——以普通Schnorr签名为基础,结合二义性同态承诺实现格上两轮多重签名,然而,通过分析格上困难问题与离散对数问题的不同之处,发现构造格上多重签名方案时,直接选用同态承诺可节省方案的通信量和计算量.

    因此,本文以GLP签名[13]为基础,结合格上高效同态承诺[14],在多项式环上设计了一个支持公钥聚合[11]功能的两轮多重签名方案(TLMS方案),并在随机预言机模型中证明该方案的安全性.

    N表示一个正整数且为2的方幂,q表示一个素数;R表示多项式环Z[x]/(xN+1),Rq表示多项式环Z[x]/(xN+1),Rq中环元素为N-1阶多项式且每一项系数属于[(q1)/2,(q1)/2],Rd表示Rq的子集且每一项系数属于[d,d],其中dN+.文中所有向量均为列向量,vT表示向量v的转置;分别表示向量v的1-范数、2-范数、无穷范数.对于正整数\eta, \mathcal{S}_{\eta} 表示\mathcal{R} 中无穷范数至多为η的多项式集合.假设A表示集合,a \stackrel{\$}{\leftarrow} A 表示从A中均匀随机抽取元素a.参考文献[13],D32N表示阶为N-1且32项系数为±1、其余项系数为0的多项式集合.参考文献[14],以特殊方式选择参数q,使得\mathcal{R}_{q} 中范数小的元素可逆;挑战空间为\mathcal{C}=\$\left\{c \in \mathcal{R}_{q} \mid\left\|_{c}\right\|_{\infty}=1, \|c\|_{1}=\kappa, \kappa \in \mathbb{N}_{+}\right\} ,差集为\overline{\mathcal{C}}=\left\{c-c^{\prime} \mid c \neq\right.\$\left.c^{\prime} \in \mathcal{C}\right\} .

    问题1[15]   (DCKq, N问题)给定a \stackrel{\$}{\leftarrow} \mathcal{R}_{q}, s_{i} \stackrel{\$}{\leftarrow}\mathcal{R}_{1} ,要求区分\mathcal{R}_{q} \times \mathcal{R}_{q}上的均匀分布和\left(a, a \cdot s_{1}+s_{2}\right) 分布.

    问题2[16]   (Ring-SISm, q, β问题)给定m个多项式组成的向量\boldsymbol{a}=\left(a_{1}, a_{2}, \cdots, a_{m}\right)^{\mathrm{T}} \in \mathcal{R}_{q}^{m} ,要求找到一个非零向量\boldsymbol{x}=\left(x_{1}, x_{2}, \cdots, x_{m}\right) \in \mathcal{R}^{m} ,使其满足\boldsymbol{a}^{\mathrm{T}} \boldsymbol{x}= \sum\limits_{i = 1}^m {{a_i}} \cdot x_{i} \bmod q=0 \text { 且 } 0<\| \mathit{\boldsymbol{x}}\|<\beta .

    引理1[17]  选择参数Np≥1且为2的方幂,参数q为素数且满足 q = 2p + 1({\rm{mod}}\;4p),则多项式xN+1可分解为环 \mathcal{R} p个不可约多项式x^{\frac{N}{p}}-r_{j} 的乘积,且对于多项式环 \mathcal{R}_{q}中任意非零环元素y,若y的范数满足0 \leqslant\|y\|_{\infty}<q^{\frac{1}{p}} / \sqrt{p} 或者0 \leqslant\left\|y\right\|_{2}<q^{\frac{1}{p}} ,则y存在逆元.

    假设一组签名者L={1, 2, …, l}将对消息m进行多重签名.一般地,多重签名方案MS=(MKeyGen, MSign, MVerify)由以下3个算法组成:

    (1) MKeyGen:密钥生成算法,给定安全参数θ,该概率算法为每位签名者i生成签名私钥ski和验证公钥pki

    (2) MSign:多重签名生成算法,输入公钥集合PK={pk1, pk2, …, pkl}和消息m,若签名成功, 则该概率算法返回多重签名σ,否则返回⊥;

    (3) MVerify:多重签名验证算法,输入待验证签名σ、消息m和公钥集合PK={pk1, pk2, …, pkl},若待验证签名有效, 则该确定性算法返回1,否则返回0.

    参照文献[18],下面给出多重签名方案的安全定义.

    定义1   (安全定义)多重签名方案MS=(MKeyGen, MSign, MVerify)是EUF-CMA安全的,若任意概率多项式时间的伪造者在以下游戏中获胜的概率可忽略不计:

    step 1:挑战者输入安全参数θ并执行密钥生成算法,产生签名密钥对(sk, pk),且向伪造者发送验证公钥pk;

    step 2:伪造者自适应地发起消息mi(1≤iq)的签名查询,挑战者执行签名生成算法产生签名σi并发送给伪造者;

    step 3:伪造者利用签名σi(1≤iq),伪造一个新消息m*的签名σ*,若签名σ*有效,则伪造者在游戏中获胜.

    2006年,BELLARE和NEVEN[5]提出了分析数字签名安全性的重要工具:

    引理2[5] (广义分叉引理)假设q>1,集合H至少含有2个元素.算法 \mathcal{Q} 是一个随机算法,输入(x, {h_1}, {h_2}, \ldots , {h_q}) ,可得输出(J, \delta ) ,其中0 \le J \le q . IG是一个随机算法, 称为输入发生器.算法 \mathcal{Q} 的接受率acc为以下实验中 J \geqslant 1的概率:随机选取 x \stackrel{\$}{\leftarrow} IG和h_{1}, h_{2}, \cdots, h_{q} \stackrel{\$}{\leftarrow} H ;(J, \delta) \stackrel{\$}{\leftarrow} \mathcal{Q}\left(x, h_{1}, h_{2}, \cdots, h_{q}\right) .基于算法\mathcal{Q} 的分叉算法GF _ \mathcal{Q} 同样为随机算法,其输入为x,具体执行过程如下:

    随机选取算法 \mathcal{Q}的抛币ρ

    随机选取 h_{1}, h_{2}, \cdots, h_{q} \stackrel{\$}{\leftarrow} H

    (I, \delta) \stackrel{\$}{\leftarrow} \mathcal{Q}\left(x, h_{1}, \cdots, h_{q}\right);如果I=0,则返回(0, ε, ε);

    随机选取 h_{I}^{\prime}, \cdots, h_{q}^{\prime} \stackrel{\$}{\leftarrow} H

    ({I^\prime },{\delta ^\prime })\mathop \leftarrow \limits^\$ \mathcal{Q}(x,{h_1}, \cdots ,{h_{I - 1}},h_I^\prime , \cdots ,h_q^\prime );

    如果I=I′且 h_{I} \neq h_{I}^{\prime}, 则返回\left(1, \delta, \delta^{\prime}\right),否则返回(0, \varepsilon, \varepsilon) .

    假设frk= Pr[ =1: x \stackrel{\$}{\leftarrow} \mathrm{IG} ; \left., \delta, \delta^{\prime}\right) \stackrel{\$}{\leftarrow} \mathrm{GF}_{\mathcal{Q}}(x)],则\mathrm{frk} \geqslant \operatorname{acc}\left(\frac{\mathrm{acc}}{q}-\frac{1}{|H|}\right).

    2018年,BAUM等[14]提出了一个基于格的高效同态承诺方案:

    (1) KeyGen算法:构造矩阵 \mathit{\boldsymbol{A}}_{1} \in \mathcal{R}_{q}^{n \times k} \mathit{\boldsymbol{A}}_{2} \in \mathcal{R}_{q}^{\ell \times k} ,满足 \mathit{\boldsymbol{A}}_{1}=\left[\boldsymbol{I}_{n} \boldsymbol{A}_{1}^{\prime}\right],其中\boldsymbol{I}_{n} n阶单位矩阵,且\boldsymbol{A}_{1}^{\prime} \stackrel{\$}{\leftarrow} \mathcal{R}_{q}^{n \times(k-n)} ; \boldsymbol{A}_{2}=\left[\boldsymbol{0}^{\ell \times n} \boldsymbol{I}_{\ell} \boldsymbol{A}_{2}^{\prime}\right] ,并输出矩阵{\mathit{\boldsymbol{A}}_1} {\mathit{\boldsymbol{A}}_2} .

    (2) Commit算法:为了承诺 \boldsymbol{x} \in \mathcal{R}_{q}^{\ell},随机抽取多项式向量\mathit{\boldsymbol{r}} \stackrel{\$}{\leftarrow} \mathcal{S}_{\eta}^{k} ,计算承诺值 \operatorname{Com}(\boldsymbol{x} ; \boldsymbol{r}):=\left[\begin{array}{l} \mathit{\boldsymbol{c}}_{1} \\ \mathit{\boldsymbol{c}}_{2} \end{array}\right]=\left[\begin{array}{c} \mathit{\boldsymbol{A}}_{1} \\ \mathit{\boldsymbol{A}}_{2} \end{array}\right] \cdot r+\left[\begin{array}{l} \mathit{\pmb{0}}^{n} \\ \mathit{\boldsymbol{x}} \end{array}\right] 并输出.

    (3) Open算法:承诺值\left[\begin{array}{l} \mathit{\boldsymbol{c}}_{1} \\ \mathit{\boldsymbol{c}}_{2} \end{array}\right] 的有效打开是一个三元组 \left(\boldsymbol{x}, \boldsymbol{r}, f_{1}\right),其中, \boldsymbol{x} \in \mathcal{R}_{q}^{\ell}, \boldsymbol{r}=\left[\begin{array}{c} r_{1} \\ \vdots \\ r_{k} \end{array}\right] \in \mathcal{R}_{q}^{k}, f_{1} \in \overline{\mathcal{C}} .验证者检验 f_{1} \cdot\left[\begin{array}{l} \mathit{\boldsymbol{c}}_{1} \\ \mathit{\boldsymbol{c}}_{2} \end{array}\right]=\left[\begin{array}{c} \mathit{\boldsymbol{A}}_{1} \\ \mathit{\boldsymbol{A}}_{2} \end{array}\right] \cdot r+f_{1} \cdot\left[\begin{array}{c} \mathit{\pmb{0}}^{n} \\ \mathit{\boldsymbol{x}} \end{array}\right] \text { 及 }\left\|\mathit{\boldsymbol{r}}_{i}\right\|_{2} \leqslant 4 \tau \sqrt{N},其中, 1 \leqslant i \leqslant k, \tau=11 \kappa \cdot \eta \cdot \sqrt{k \cdot N}.

    结合格上高效同态承诺方案,本文给出了TLMS方案,该方案包括MKeyGen算法、MSign协议和MVerify算法,各算法的执行过程如下:

    (1) MKeyGen算法:所有签名者L={1, 2, …, l}共享一个随机多项式 a \stackrel{\$}{\leftarrow} \mathcal{R}_{q}.每位签名者i随机选择2个多项式s_{i}, v_{i} \in \mathcal{R}_{1} , 并将 \mathrm{sk}_{i}=\left(s_{i}, v_{i}\right)作为签名私钥,其验证公钥为 \mathrm{pk}_{i}=\left(\begin{array}{cc} a & 1 \end{array}\right) \cdot\left(\begin{array}{c} s_{i} \\ v_{i} \end{array}\right)=a \cdot s_{i}+v_{i} \bmod q.

    (2) MSign协议:假设所有签名者的公钥集合为\mathrm{PK}=\left\{\mathrm{pk}_{1}, \mathrm{pk}_{2}, \cdots, \mathrm{pk}_{l}\right\} ; H_{0}:\{0, 1\}^{*} \rightarrow \mathcal{R}_{q}^{3}, H_{1}:\{0, 1\}^{*} \rightarrow\$D_{32}^{N} H_{2}:\{0, 1\}^{*} \rightarrow D_{32}^{N}为3个密码学哈希函数,其值域分别为D_{H_{0}}=\left\{\mathcal{R}_{q}^{3}\right\}, D_{H_{1}}=\left\{\mathcal{G}: \mathcal{G} \in\{-1,0,1\}^{\mathcal{K}},\|\mathcal{G}\| \leqslant \mathcal{K}\right., \left.\mathcal{K} \in \mathbb{N}_{+}\right\} \text {和 } D_{H_{2}}=\left\{\mathcal{G}: \mathcal{G} \in\{-1,0,1\}^{\mathcal{K}},\|\mathcal{G}\| \leqslant \mathcal{K}, \mathcal{K} \in \mathbb{N}_{+}\right\}.具体地,签名者i输入 \left(\mathrm{PK}, \mathrm{pk}_{i}, \mathrm{sk}_{i}, m, T\right),其中Τ为所有签名者形成的二叉树,执行多重签名协议如下:

    (i) 第1轮交互.

    公布阶段:若签名者i为树结构Τ的根节点,则向子节点发送唯一的会话标识符ssid及消息m;否则等待接收ssid、m并将其发送至子节点.

    承诺阶段:签名者i等待接收其子节点jCi发送的数据 \left(t_{j, 1}, t_{j, 2}, \mathrm{apk}_{j}\right).签名者i查询(b, e, f) \leftarrow {H_{\rm{0}}}{\rm{(}}m{\rm{)}} ,分别抽取\alpha_{i} \stackrel{\$}{\leftarrow} \mathcal{R}_{d}^{2} r_{i} \stackrel{\$}{\leftarrow} S_{1}^{3} ,并计算承诺值t_{i, 1}^{\prime} \leftarrow(1 \;b \;e) \cdot\left(\begin{array}{c} r_{i, 1} \\ r_{i, 2} \\ r_{i, 3} \end{array}\right) \bmod q, t_{i, 1}=t_{i, 1}^{\prime}+\sum\limits_{j \in {C_i}} {{t_{j,1}}} \bmod q 和承诺值 t_{i, 2}^\prime \leftarrow (0\;1\;f) \cdot \left( {\begin{array}{*{20}{c}} {{r_{i, 1}}}\\ {{r_{i, 2}}}\\ {{r_{i, 3}}} \end{array}} \right) + (a\quad 1) \cdot \left( {\begin{array}{*{20}{c}} {{\alpha _{i, 1}}}\\ {{\alpha _{i, 2}}} \end{array}} \right)\, \bmod \, q, t_{i, 2}=t_{i, 2}^{\prime}+\sum\limits_{j \in {C_i}} {{t_{j,2}}} \bmod q.签名者i查询 u_{i}=H_{1}\left(\mathrm{PK}, \mathrm{pk}_{i}\right)并计算部分聚合公钥apk_{i}=u_{i} \cdot \mathrm{pk}_{i}+\sum\limits_{j \in {C_i}} \; apk _{j} \bmod q .若签名者i不是树结构Τ的根节点,则向其父节点发送数据\left(t_{i, 1}, t_{i, 2}, \operatorname{apk}_{i}\right) ,否则进入下一阶段.

    (ii) 第2轮交互.

    挑战阶段:若签名者i为树结构Τ的根节点,则设置t1=ti, 1t2=ti, 2以及apk=apki,查询cH2(t1, t2, apk, m),并向其子节点发送数据(t1, t2, apk).否则,等待接收数据(t1, t2, apk),查询cH2(t1, t2, apk, m),并向其子节点发送数据(t1, t2, apk).

    响应阶段:签名者i等待接收其子节点jCi发送的数据 \left(z_{j}, g_{j}\right).签名者i计算 z_{i}^{\prime} \leftarrow \alpha_{i}+c \cdot u_{i} \cdot \mathrm{sk}_{i}.若z_{i}^{\prime} \in \mathcal{R}_{d-1\;024} \times \mathcal{R}_{d-1\;024} ,则设置 z_{i} \leftarrow z_{i}^{\prime}+\sum\limits_{j \in {C_i}} {{z_j}} ,{g_i} \leftarrow r_{i}+\sum\limits_{j \in {C_i}} {{g_j}} \bmod q,并向其父节点发送数据\left(z_{i}, g_{i}\right) ;否则重启签名协议.若签名者i为树结构Τ的根节点,则设置 z \leftarrow z_{i}g \leftarrow g_{i} ,并输出签名\sigma \leftarrow\left(t_{1}, t_{2}, z, g\right) .

    (3) MVerify算法:给定一组签名者的聚合公钥apk、消息m和待验证多重签名\sigma=\left(t_{1}, t_{2}, z, g\right) ,验证者查询 (b, e, f) \leftarrow H_{0}(m)c \leftarrow H_{2}\left(t_{1}, t_{2}, \text { apk }, m\right) .若z \in \mathcal{R}_{l \cdot(d-1\;024)} \times \mathcal{R}_{l \cdot(d-1\;024)}, t_{1}=(1\; b \;e) \cdot\left(\begin{array}{l} g_{1} \\ g_{2} \\ g_{3} \end{array}\right) {mod } q t_{2}=(0 \quad 1\; f) \cdot\left(\begin{array}{l} g_{1} \\ g_{2} \\ g_{3} \end{array}\right)+\left(\begin{array}{ll} a & 1 \end{array}\right) \cdot\left(\begin{array}{l} z_{1} \\ z_{2} \end{array}\right)-c \cdot \text { apk mod } q, 则判定签名有效并返回1,否则返回0.

    若每位签名者均诚实地执行TLMS方案并生成各自的部分签名,则 z=\sum\limits_{i = 1}^l {z_i^\prime } , t_{1}=\sum\limits_{i = 1}^l {t_{i,1}^\prime } \,\bmod \,q,{t_2} = \sum\limits_{i = 1}^l {t_{i,2}^\prime } \,\bmod \,q(b, e, f) \leftarrow H_{0}(m), c \leftarrow H_{2}\left(t_{1}, t_{2}, \right. \text { apk } m) ,从而

    \begin{array}{l} {t_1} = \left( {\begin{array}{*{20}{l}} 1&b&e \end{array}} \right) \cdot \left( {\begin{array}{*{20}{l}} {{g_1}}\\ {{g_2}}\\ {{g_3}} \end{array}} \right){\kern 1pt} {\kern 1pt} {\kern 1pt} \,{\rm{mod}}\,q = \left( {\begin{array}{*{20}{l}} 1&b&e \end{array}} \right) \cdot \left( {\begin{array}{*{20}{c}} {\sum\limits_{i = 1}^l {{r_{i,1}}} }\\ {\sum\limits_{i = 1}^l {{r_{i,2}}} }\\ {\sum\limits_{i = 1}^l {{r_{i,3}}} } \end{array}} \right){\rm{mod}}\,q = \\ {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} \sum\limits_{i = 1}^l {\left( {(1\quad b\quad e) \cdot \left( {\begin{array}{*{20}{l}} {{r_{i,1}}}\\ {{r_{i,2}}}\\ {{r_{i,3}}} \end{array}} \right)\,} \right)} {\kern 1pt} {\kern 1pt} {\kern 1pt} \bmod \,q = \sum\limits_{i = 1}^l {t_{i,1}^\prime } \,{\kern 1pt} \bmod \,q = \\ {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {t_1}\,\bmod \,q, \end{array}
    \begin{array}{l} {t_2} = (0\quad 1\quad f) \cdot \left( {\begin{array}{*{20}{l}} {{g_1}}\\ {{g_2}}\\ {{g_3}} \end{array}} \right) + \left( {\begin{array}{*{20}{l}} a&1 \end{array}} \right) \cdot \left( {\begin{array}{*{20}{l}} {{z_1}}\\ {{z_2}} \end{array}} \right) - c \cdot {\rm{ apk}}{\kern 1pt} {\kern 1pt} {\kern 1pt} {\rm{mod}}{\kern 1pt} {\kern 1pt} {\kern 1pt} q = \\ {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} (0\quad 1\quad f) \cdot \left( {\begin{array}{*{20}{c}} {\sum\limits_{i = 1}^l {{r_{i,1}}} }\\ {\sum\limits_{i = 1}^\sum {{r_{i,2}}} }\\ {\sum\limits_{i = 1}^l {{r_{i,3}}} } \end{array}} \right) + \left( {\begin{array}{*{20}{l}} a&1 \end{array}} \right) \cdot \left( {\begin{array}{*{20}{c}} {\sum\limits_{i = 1}^l {z_{i,1}^\prime } }\\ {\sum\limits_{i = 1}^l {z_{i,2}^\prime } } \end{array}} \right) - \\ {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} c\sum\limits_{i = 1}^l {{u_i}} \cdot {\rm{p}}{{\rm{k}}_i}{\kern 1pt} {\kern 1pt} \bmod {\kern 1pt} {\kern 1pt} q = \sum\limits_{i = 1}^l {\left( {(0\quad 1\quad f) \cdot \left( {\begin{array}{*{20}{l}} {{r_{i,1}}}\\ {{r_{i,2}}}\\ {{r_{i,3}}} \end{array}} \right)} \right)} + \\ {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} \left( {\begin{array}{*{20}{l}} a&1 \end{array}} \right) \cdot \left( {\begin{array}{*{20}{c}} {\sum\limits_{i = 1}^l {{\alpha _{i,1}}} + c \cdot {u_i} \cdot {s_i}}\\ {\sum\limits_{i = 1}^l {{\alpha _{i,2}}} + c \cdot {u_i} \cdot {v_i}} \end{array}} \right) - \\ \,{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} c\sum\limits_{i = 1}^l {{u_i}} \cdot \left( {\begin{array}{*{20}{l}} a&1 \end{array}} \right) \cdot \left( {\begin{array}{*{20}{l}} {{s_i}}\\ {{v_i}} \end{array}} \right){\kern 1pt} {\kern 1pt} {\kern 1pt} \bmod \,q = \sum\limits_{i = 1}^l {\left( {(0\quad 1\quad f) \cdot \left( {\begin{array}{*{20}{l}} {{r_{i,1}}}\\ {{r_{i,2}}}\\ {{r_{i,3}}} \end{array}} \right)} \right)} + \\ {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} (a\quad 1) \cdot \left( {\begin{array}{*{20}{c}} {\sum\limits_{i = 1}^l {{\alpha _{i,1}}} }\\ {\sum\limits_{i = 1}^l {{\alpha _{i,2}}} } \end{array}} \right)\,\bmod \,q = \\ {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} \sum\limits_{i = 1}^l {\left( {\left( {\begin{array}{*{20}{l}} 0&1&f \end{array}} \right) \cdot \left( {\begin{array}{*{20}{l}} {{r_{i,1}}}\\ {{r_{i,2}}}\\ {{r_{i,3}}} \end{array}} \right) + \left( {\begin{array}{*{20}{l}} a&1 \end{array}} \right) \cdot \left( {\begin{array}{*{20}{l}} {{\alpha _{i,1}}}\\ {{\alpha _{i,2}}} \end{array}} \right){\kern 1pt} {\kern 1pt} } \right)} {\kern 1pt} \,\bmod \,q = \\ {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} \sum\limits_{i = 1}^l {t_{i,2}^\prime } \,\bmod \,q = {t_2}\,\bmod \,q. \end{array}

    由此可知,TLMS方案是正确的.

    定理1  在随机预言机模型下,若存在1个概率多项式时间的伪造者\mathcal{F} ,在至多进行qH次随机预言机查询、qS次签名查询且至多涉及lmax个公钥的前提下,成功伪造TLMS多重签名\sigma = ({t_1}, {t_2}, z, g )的概率为δ,其中承诺值t_{1}, t_{2} \in \mathcal{R}_{q} ,聚合后的签名z=\sum\limits_{i = 1}^l {z_i^\prime } \in \mathcal{R}_{l \cdot(d-1\;024)} \times \mathcal{R}_{l \cdot(d-1\;024)} (l为签名者人数,部分签名\left.z_{i}^{\prime} \in \mathcal{R}_{d-1\;024} \times \mathcal{R}_{d-1\;024}, d>1\;024\right) ,随机向量\boldsymbol{g} \in \mathcal{R}_{q}^{3} ,则存在1个同样时间复杂度的算法 \mathcal{D},给定A(a \quad 1) \stackrel{\$}{\leftarrow} \mathcal{R}_{q} \times\{1\} ,能够找到2个非零向量 \boldsymbol{o}_{1}, \boldsymbol{o}_{2} \in\mathcal{R}_{q} ,使得 a \cdot \boldsymbol{o}_{1}+\boldsymbol{o}_{2}=0\left\|\boldsymbol{o}_{i}\right\|_{\infty} \leqslant 256 l_{\max } \cdot(d-1\;024) 的概率至少为\left(\frac{1}{2}-2^{-100}\right)\left(\frac{q_{A}^{2}}{q_{H}+q_{S}}-\frac{q_{A}}{\left|D_{H_{2}}\right|}\right) \times \left(\frac{q_{A}^{2} / q_{H}+q_{S}-q_{A} /\left|D_{H_{2}}\right|}{q_{H}+q_{S}}-\frac{1}{\left|D_{H_{1}}\right|}\right) ,其中, q_{A}=\delta-2\left(q_{H}+\right.\left.l_{\max } \cdot q_{S}\right)^{2} / q^{n}, D_{H_{1}} 、 D_{H_{2}} 分别表示哈希函数 H_{1} 、H_{2} 的值域.

    证明  假设参数 x=\left(\mathcal{R}_{q}, \boldsymbol{A}, d\right),其中\boldsymbol{A}= (a\; 1) ,多项式a服从 \mathcal{R}_{q}中的均匀分布.给定攻击TLMS方案的伪造者 \mathcal{F},可构造1个模拟真实签名环境的算法 \mathcal{A},具体构造如下:

    (1) 输入:参数x,哈希函数H1的响应 \lambda_{1, 1}, \lambda_{1, 2} \cdots, \lambda_{1, q_{H}},哈希函数H2的响应\lambda_{2, 1}, \lambda_{2, 2}, \cdots, \lambda_{2, q_{H}} ,随机抛币\rho_{\mathcal{A}} .

    算法\mathcal{A} \mathcal{R}_{1} 中随机抽取2个多项式s^{*} 、{v}^{*} ,设置其私钥sk ^{*}=\left(s^{*}, v^{*}\right) ,并计算其公钥\mathrm{pk}^{*}=A \cdot \mathrm{sk}^{*}= (a \quad 1) \cdot\left(\begin{array}{c}s^{*} \\ v^{*}\end{array}\right) \bmod q .算法\mathit{A} 向伪造者\mathit{F} 发送参数x和验证公钥pk*,并与伪造者\mathcal{F} 在交互时根据如下步骤响应随机预言机查询(在随机预言机模型中,哈希函数被形式化为随机预言机)和签名查询.

    (2) 随机预言机查询.为模拟随机预言机查询,算法\mathcal{A} 初始化4张表L_{0}, L_{1}, L_{2}, L_{3} ,其中 L_{0}, L_{1}, L_{2}分别存储随机预言机 H_{0}, H_{1}, H_{2}的响应值,L3通过 i\left(0 \leqslant i \leqslant\left(q_{H}+q_{S}\right) \cdot l_{\max }\right)区分所存储的不同公钥.假设L_{3}\left[\mathrm{pk}^{*}\right] \leftarrow 0 ,将诚实签名者的公钥pk*放在表L3首位.同时,算法 \mathcal{A} 维护2个初始化为0的计数器ctr1和ctr2,分别记录随机预言机H1H2的查询次数.假设攻击者 \mathcal{F}没有发起重复查询.

    (i) 随机预言机H0(m)查询.算法\mathcal{A} 查询表L0(m),若其已定义则直接返回(b, e, f).否则,算法 \mathcal{A}\mathcal{R}_q 中随机抽取多项式并存储于表L0(m),随后返回L0(m).

    (ii) 随机预言机H1(PK, pki)查询.算法\mathcal{A} 查询表L1(PK, pki),若其已定义则直接返回L1(PK, pki).否则,算法\mathcal{A} 查询表L3pki,若其未定义,则将公钥pki存储于表L3.然后,算法\mathcal{A} 解析公钥集合PK={pk1, pk2, …, pkl}, 并检查每个公钥pkj∈PK是否已存储于表L3.在保证每个公钥pkj∈PK均存储于表L3后,再依据以下3种情况一次性赋值H1(PK, pkj)满足1≤jl

    \mathrm{pk}_{j}=\mathrm{pk}^{*} \text { 且 } \mathrm{pk}^{*} \in \mathrm{PK}

    \mathrm{pk}_{j} \neq \mathrm{pk}^{*} \text { 且 } \mathrm{pk}^{*} \in \mathrm{PK}

    \mathrm{pk}^{*} \notin \mathrm{PK}.

    对于情况①,算法\mathcal{A} 增加计数器ctr1并设置L1(PK, pkj)=λ1, ctr1;对于情况②、③,算法\mathcal{A} D32N随机抽取元素并存储于表L1(PK, pkj).在分配所有L1(PK, pkj)后,算法\mathcal{A} 计算聚合公钥apk.若伪造者\mathcal{F} 已查询哈希函数H2(·, ·, apk, m)或已进行涉及apk的签名查询,则此时事件E1发生,算法\mathcal{A} 放弃签名协议并返回⊥.否则,算法\mathcal{A} 返回L1(PK, pki).

    (iii) 随机预言机H2(t1, t2, apk, m)查询.算法\mathcal{A} 首先查询表L2(t1, t2, apk, m), 若其已定义则直接返回L2(t1, t2, apk, m).否则,算法\mathcal{A} 进行内部查询H0(m)并存储相关数据.然后,算法\mathcal{A} 增加计数器ctr2并设置L2(t1, t2, apk, m)=λ2, ctr2,返回L2(t1, t2, apk, m).

    (3) 签名查询.在模拟签名查询过程中,伪造者\mathcal{F} 向算法\mathcal{A} 请求消息m、公钥集合PK的多重签名,算法\mathcal{A} 响应如下:

    在签名协议的第1轮交互中,算法\mathcal{A} 首先判断其公钥pk*是否属于公钥集合PK.若不存在,则算法\mathcal{A} 终止签名协议并输出⊥,否则解析公钥集合PK={pk1, pk2, …, pk*=pki, …, pkl}.然后,算法\mathcal{A} 分别进行查询H0(m)和H1(PK, pkj),并计算聚合公钥apk =\sum\limits_{i = 1}^l {{u_i}} \cdot {\rm{p}}{{\rm{k}}_i}\,\bmod \,q.算法\mathcal{A} 接收其子节点发送的数据\left(t_{j, 1}, t_{j, 2}, \mathrm{apk}_{j}\right) 后,随机抽取z_{i}^{\prime} \stackrel{\$}{\leftarrow} \mathcal{R}_{d-1\;024}^{q} \times \mathcal{R}_{d-1\;024}^{q} c=\lambda_{2, \mathrm{ctr}_{2}+1},计算 w=\left(\begin{array}{cc} a & 1 \end{array}\right) \cdot\left(\begin{array}{c} z_{i, 1}^{\prime} \\ z_{i, 2}^{\prime} \end{array}\right)-c \cdot u_{i} \cdot \mathrm{pk}^{*} \bmod q.算法\mathcal{A} 随机抽取 r_{i} \stackrel{\$}{\leftarrow} S_{1} \times S_{1} \times S_{1},并计算 t_{i, 1}^\prime = (1\;b\;e) \cdot \left(\begin{array}{l} r_{i, 1} \\ r_{i, 2} \\ r_{i, 3} \end{array}\right) \bmod q t_{i, 2}^{\prime}=\left(\begin{array}{lll} 0 & 1 & f \end{array}\right) \cdot\left(\begin{array}{l} r_{i, 1} \\ r_{i, 2} \\ r_{i, 3} \end{array}\right)+w \bmod q.算法\mathcal{A} 计算 t_{i, 1}=t_{i, 1}^{\prime}+\sum\limits_{j \in {C_i}} {{t_{j,1}}} \bmod q 、 t_{i, 2}=t_{i, 2}^{\prime}+\sum\limits_{j \in {C_i}} {{t_{j,2}}} \,\bmod \,{q}、{\rm{ apk}}{{\rm{ }}_i} = u_{i} \cdot p \mathrm{k}^{*}+\sum\limits_{j \in {C_j}} {{\rm{ apk}}{{\rm{ }}_j}} \,\bmod \,q , 并向其父节点发送数据(ti, 1, ti, 2, apki).

    在签名协议的第2轮交互中,算法\mathcal{A} 接收其子节点发送的数据 ({t_1}, {t_2}, {\rm{apk}})后,查询{H_2}({t_1}, {t_2}, {\rm{apk}}, m) = c = {\lambda _{2, {\rm{ct}}{{\rm{r}}_2} + 1}} ,并设置 {L_2}({t_1}, {t_2}, {\rm{apk}}, m) = c = {\lambda _{2, {\rm{ct}}{{\rm{r}}_2} + 1}},向其子节点发送数据 ({t_1}, {t_2}, {\rm{apk}}).算法\mathcal{A} 接收其子节点j发送的数据(zj, gj)后,计算z_{i}=z_{i}^{\prime}+\sum\limits_{j \in {C_i}} {{z_j}} , g_{i}=r_{i}+\sum\limits_{j \in {C_i}} {{g_j}} \bmod q ,并向其父节点发送数据 \left(z_{i}, g_{i}\right).

    若伪造者\mathcal{F} 返回⊥,则算法\mathcal{A} 也返回⊥.否则,伪造者\mathcal{F} 输出一个基于消息m、公钥集合PK的伪造签名 \sigma=\left\{t_{1}, t_{2}, z, g\right\}.算法\mathcal{A} 解析公钥集合PK \left\{\mathrm{pk}_{1}, \mathrm{pk}_{2}, \cdots, \mathrm{pk}^{*}=\mathrm{pk}_{i}, \cdots, \mathrm{pk}_{l}\right\} ,查询 H_{1}\left(\mathrm{PK}, \mathrm{pk}_{j}\right)= u_{j}并计算聚合公钥 \mathrm{apk}=\sum\limits_{j = 1}^l {{u_j}} \cdot {\rm{p}}{{\rm{k}}_j}\,\bmod \,q ,查询 H_{2}\left(t_{1}, \right.t_{2} , apk, \left., m\right)=cH_{0}(m)=(b, e, f) 并验证\|z\|_{\infty} \leqslant l \cdot(d-1\;024), t_{1}=\left(\begin{array}{lll} 1 & b & e \end{array}\right) \cdot\left(\begin{array}{l} g_{1} \\ g_{2} \\ g_{3} \end{array}\right) \bmod q 以及t2= \left(\begin{array}{lll} 0 & 1 & f \end{array}\right) \cdot\left(\begin{array}{l} g_{1} \\ g_{2} \\ g_{3} \end{array}\right)+\left(\begin{array}{ll} a & 1 \end{array}\right) \cdot\left(\begin{array}{l} z_{1} \\ z_{2} \end{array}\right)-c \cdot \text { apk } \bmod q .假设 H_{1}\left(\mathrm{PK}, \mathrm{pk}_{j}\right)=\lambda_{1, I}表示第I次随机预言机H1查询,H_{2}\left(t_{1}, t_{2}, \mathrm{apk}, m\right)=\lambda_{2, J} 表示第J次随机预言机H2查询.若伪造签名\sigma=\left\{t_{1}, t_{2}, z, g\right\} 为有效签名,则算法\mathcal{A} 返回 \left(J, \left(I, t_{1}, t_{2}, z, g, c, \text { apk }, \mathrm{PK}, u_{1}, \cdots, u_{l}\right)\right),否则返回(0, ε).

    下面根据广义分叉引理考虑算法\mathcal{A} 的接受概率acc.在事件E1和事件E2(即:伪造者\mathcal{F} 找到2组不同公钥集合PK和PK′,且使用这2组不同公钥集合可产生相同聚合公钥apk)不发生的情况下,算法\mathcal{A} 模拟的多重签名环境与真实签名环境不可区分.因此,

    \begin{array}{l} {\rm{ac}}{{\rm{c}}_\mathcal{A}} = {\rm{Pr}}[{\rm{ 伪造签名有效 }}] - {\rm{Pr}} [{E_1}] - {\rm{Pr}} [{E_2}] = \\ {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} \begin{array}{*{20}{l}} {\delta - {{({q_H} + {l_{\max }} \cdot {q_S})}^2}/{q^n} - {{({q_H} + {l_{\max }} \cdot {q_S})}^2}/{q^n} = }\\ {\delta - 2{{({q_H} + {l_{\max }} \cdot {q_S})}^2}/{q^n}.} \end{array} \end{array}

    接着,可构造多项式时间算法 \mathcal{B},其执行分叉算法GF _{\mathcal{A}}可得有关聚合公钥apk的等式.算法 \mathcal{B}输入参数x,随机预言机H1的响应值\lambda_{1, 1}, \lambda_{1, 2}, \cdots, \lambda_{1, q_{H}} 及随机抛币\rho_{\mathcal{B}} ,运行广义分叉算法GF _{\mathcal{A}}并输出: (J, (I, \left.t_{1}, t_{2}, z, g, c, \mathrm{apk}, \mathrm{PK}, u_{1}, \cdots, u_{l}\right) ; J^{*}, \left(I^{*}, t_{1}^{*}, t_{2}^{*}, z^{*}, g^{*}\right. \left.\left.c^{*}, \mathrm{apk}^{*}, \mathrm{PK}^{*}, u_{1}^{*}, \cdots, u_{l}^{*}\right)\right),其中J=J^{*} .在算法\mathcal{A} 的2次执行过程中,分叉点位于第J次随机预言机查询H2(t1, t2, apk, m).这表明在此分叉点前,算法\mathcal{A} 模拟的2次签名协议执行环境完全一致.因此,随机预言机查询H2(t1, t2, apk, m)的参数是相同的,即t1=t1*t2=t2*,apk=apk*m=m*.随机预言机查询H0(m)发生在分叉点H2(t1, t2, apk, m)之前,因此,算法 \mathcal{A}的2次执行中,随机预言机查询H0(m)的结果相同.同理,随机预言机查询H1(PK, pkj)亦发生在分叉点之前,即有PK=PK*uj=uj* 1 \le j \le l.另外,算法\mathcal{A} 的2次执行均产生有效签名,因此,如下2个验证等式必定成立:

    {t_1} = \left( {\begin{array}{*{20}{l}} 1&b&e \end{array}} \right) \cdot \left( {\begin{array}{*{20}{l}} {{g_1}}\\ {{g_2}}\\ {{g_3}} \end{array}} \right), (1)
    t_1^* = \left( {\begin{array}{*{20}{l}} 1&b&e \end{array}} \right) \cdot \left( {\begin{array}{*{20}{l}} {g_1^*}\\ {g_2^*}\\ {g_3^*} \end{array}} \right). (2)

    依据t1=t1*,合并式(1)、(2),可得:

    \left( {\begin{array}{*{20}{l}} 1&b&e \end{array}} \right) \cdot \left( {\begin{array}{*{20}{l}} {{g_1} - g_1^*}\\ {{g_2} - g_2^*}\\ {{g_3} - g_3^*} \end{array}} \right) = 0. (3)

    此时,算法 \mathcal{B}可计算判断 (0\;1\; f) \cdot\left(\begin{array}{l} g_{1} \\ g_{2} \\ g_{3} \end{array}\right)与(0  1  f \left( {\begin{array}{*{20}{l}} {g_1^*}\\ {g_2^*}\\ {g_3^*} \end{array}} \right)是否相等,并依据结果分情况讨论:

    (i) 若(0\;\;1\;\;f) \cdot \left( {\begin{array}{*{20}{l}} {{g_1}}\\ {{g_2}}\\ {{g_3}} \end{array}} \right)\; (0\;\;1\;\;f) \cdot \;\left( {\begin{array}{*{20}{l}} {g_1^*}\\ {g_2^*}\\ {g_3^*} \end{array}} \right) ,算法 \mathcal{B}不能找到2个非零向量\boldsymbol{o}_{1}, \boldsymbol{o}_{2} \in \mathcal{R}_{q} ,使得a \cdot \boldsymbol{o}_{1}+\boldsymbol{o}_{2}=0 ,即算法\mathcal{B}无法求解Ring-SIS问题.因此,TLMS方案是安全的.

    (ii) 若(0 \quad 1 \quad f) \cdot\left(\begin{array}{l}g_{1} \\ g_{2} \\ g_{3}\end{array}\right)=\left(\begin{array}{lll}0 & 1 & f\end{array}\right) \cdot\left(\begin{array}{l}g_{1}^{*} \\ g_{2}^{*} \\ g_{3}^{*}\end{array}\right) .利用 t_{2}=\$t_{2}^{*}及验证等式t_{2}=\left(\begin{array}{cc}0 & 1 & f\end{array}\right) \cdot\left(\begin{array}{l}g_{1} \\ g_{2} \\ g_{3}\end{array}\right)+\left(\begin{array}{ll}a & 1\end{array}\right) \cdot\left(\begin{array}{l}z_{1} \\ z_{2}\end{array}\right)- c \cdot apk mod q, 可得:

    \mathit{\boldsymbol{A}}(z - {z^*}) + ({c^*} - c){\rm{ apk }} = 0, (4)

    则算法 \mathcal{B}输出(I, (z, {z^*}, c, {c^*}, {\rm{apk}}, PK, {u_1}, \ldots , {u_l})) .

    算法 \mathcal{B}的接受概率均为

    {\rm{ acc}}{ _\mathcal{B}} \ge {\rm{acc}}{ _\mathcal{A}} \cdot \left( {\frac{{ac{c_\mathcal{A}}}}{{{q_H} + {q_S}}} - \frac{1}{{|{D_{{H_2}}}|}}} \right).

    随后,仍需构造一个可攻击Ring-SIS问题算法 \mathcal{D},具体构造过程如下:

    输入参数x,运行分叉算法\mathrm{GF}_{\mathcal{B}} ,得到\left(I, \left(z, z^{*}, \right.\right. \mathcal{B} c, c^{*}, apk \left., \mathrm{PK}, u_{1}, \cdots, u_{l}\right) ; I^{\prime}, \left(z^{\prime}, z^{*^{\prime}}, c^{\prime}, c^{*^{\prime}}, \right.apk ^{\prime}, \left.\left.\mathrm{PK}^{\prime}, u_{1}^{\prime}, \cdots, u_{l}^{\prime}\right)\right),其中,I=I′.在分叉算法 \mathrm{GF}_{\mathcal{B}}执行过程中,分叉点位于第I次随机预言机查询H_{1} ( \mathrm{PK} , pk ^{*}) .在分叉点之前,算法 \mathcal{B}模拟的2次执行环境是相同的,因此可知2次随机预言机查询H1(PK, pk*)的参数相同,即PK=PK′,pk*=pk*′.此外,根据算法\mathcal{A} 对随机预言机H_{1}\left(\mathrm{PK}, \mathrm{pk}^{*}\right) 的响应可知:当{\rm{p}}{{\rm{k}}_j} \ne \mathrm{pk}^{*}时,u_{j}=u_{j}^{\prime} ;当 \mathrm{pk}_{j}=\mathrm{pk}^{*}时, u_{j} \neq u_{j}^{\prime}.从而可得apk≠apk′.依据分叉算法\mathrm{GF}_{\mathcal{B}} 的输出,可得2个聚合公钥等式: \mathrm{apk}=\sum\limits_{i = 1}^l {{u_i}} \cdot {\rm{p}}{{\rm{k}}_i} \bmod q \text { 及apk }^{\prime}=\sum\limits_{i = 1}^l {u_i^\prime } \cdot \mathrm{pk}_{i}^{\prime} \bmod q .假设公钥集合中包含l*个pk*,结合式(4)可得:

    {\mathit{\boldsymbol{A}}[(z - {z^*}) + ({c^*} - c)\sum\limits_{i = 1}^l {{u_i}} \cdot {\rm{s}}{{\rm{k}}_i}] = 0,} (5)
    {\mathit{\boldsymbol{A}}[({z^*} - {z^{{*^\prime }}}) + ({c^{{*^\prime }}} - {c^\prime })\sum\limits_{i = 1}^l {u_i^\prime } \cdot {\rm{s}}{{\rm{k}}_i}] = 0.} (6)

    由式(5)、(6),可得

    \begin{array}{l} A[(z - {z^*})({c^{{*^\prime }}} - {c^\prime }) - ({z^*} - {z^{{*^\prime }}})({c^*} - c) + \\ {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} |{l^*}| \cdot {\rm{s}}{{\rm{k}}^*}({c^*} - c)({c^{{*^\prime }}} - {c^\prime })({u_i} - u_i^\prime )] = 0. \end{array} (7)

    由于\|z\|_{\infty}, \left\|z^{*}\right\|_{\infty}, \left\|z^{\prime}\right\|_{\infty}, \left\|z^{*^{\prime}}\right\|_{\infty} \leqslant l \cdot(d-1\;024) ,则 \left\|z-z^{*}\right\|_{\infty}, \left\|z^{\prime}-z^{*^{\prime}}\right\|_{\infty} \leqslant 2 l \cdot(d-1\;024),因此

    \begin{array}{l} \left\| {(z - {z^*})({c^{{*^\prime }}} - {c^\prime }) - ({z^*} - {z^{{*^\prime }}})({c^*} - c) + } \right.\\ {\left. {{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} |{l^*}| \cdot s{k^*}({c^*} - c)({c^{{*^\prime }}} - {c^\prime })({u_i} - u_i^\prime )} \right\|_\infty } \le \\ {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} 256l \cdot (d - 1{\kern 1pt} {\kern 1pt} {\kern 1pt} 024) + |{l^*}| \cdot {64^3}. \end{array}

    接下来需要证明

    \begin{array}{*{20}{l}} {(z - {z^*})({c^{{*^\prime }}} - {c^\prime }) - ({z^*} - {z^{{*^\prime }}})({c^*} - c) + }\\ {\quad |{l^*}| \cdot {\rm{sk}}{ ^*}({c^*} - c)({c^{{*^\prime }}} - {c^\prime })({u_i} - u_i^\prime ) \ne 0.} \end{array} (8)

    依据文献[19]的思路,可在证明过程中选择系数稍大的多项式sk′(存在另一个多项式sk″,满足A·sk′=A·sk″).若

    \begin{array}{*{20}{l}} {(z - {z^*})({c^{{*^\prime }}} - {c^\prime }) - ({z^*} - {z^{{*^\prime }}})({c^*} - c) + }\\ {\quad |{l^*}| \cdot {\rm{sk}}{ ^\prime }({c^*} - c)({c^{{*^\prime }}} - {c^\prime })({u_i} - u_i^\prime ) = 0,} \end{array} (9)

    则存在另一个sk″,使得

    \begin{array}{*{20}{l}} {(z - {z^*})({c^{{*^\prime }}} - {c^\prime }) - ({z^*} - {z^{{*^\prime }}})({c^*} - c) + }\\ {\quad |{l^*}| \cdot {\rm{sk}}{ ^{\prime \prime }}({c^*} - c)({c^{{*^\prime }}} - {c^\prime })({u_i} - u_i^\prime ) \ne 0.} \end{array} (10)

    在模拟签名协议中,签名生成过程未使用算法\mathcal{A} 的私钥,所以,伪造者\mathcal{F} 不知算法\mathcal{A} 的私钥是sk′还是sk″.每一个私钥被算法\mathcal{A} 选中的概率为1/2,则得到非零回答的概率至少为1/2.因此,算法\mathcal{D} 可解决困难问题: \mathrm{Ring}-\mathrm{SIS}_{2 n, q, \beta}满足\beta \leqslant 256 l \cdot(d-1\;024)+ \left|l^{*}\right| \cdot 64^{3} .此时,算法\mathcal{D} 的接受概率为

    {\rm{ac}}{{\rm{c}}_\mathcal{D}} \ge {\rm{ac}}{{\rm{c}}_\mathcal{B}} \cdot \left( {\frac{{{\rm{ac}}{{\rm{c}}_\mathcal{B}}}}{{{q_H} + {q_S}}} - \frac{1}{{|{D_{{H_1}}}|}}} \right).

    TLMS方案的安全性是由DCKq, N问题的困难性、环上最小整数解(Ring-SIS)问题的困难性以及找到哈希函数原像的困难性所共同决定的.哈希函数H1H2的值域为D32N,可知H1H2的安全强度是160比特.在考虑格上困难问题的安全性时,本文参照LLL、DEEP、BKZ实验[20-21]计算判定方案安全强度的根式埃尔米特因子ξ.

    下面将介绍TLMS方案参数:(1)格维数N为正整数且为2的方幂. (2)q为素数且与参数p的关系需满足引理1. (3)人数l为整数,且签名人数较少时本方案具有较好性能. (4)随机多项式αi的系数范围d是一个重要参数,且与方案安全性、签名长度以及签名协议的重复次数相关.若选择较小参数d,则签名 z_{i}^{\prime}属于\mathcal{R}_{d-1\;024} 的概率较小;反之,若选择较大参数d,公钥长度和签名长度也随之增大. (5)在考虑签名协议重复次数时,计算公式[12]为: E=\frac{1}{\operatorname{Prob}[\text { success }]}=\frac{1}{\left(1-\frac{2\;048}{2 d+1}\right)^{2 N l}} ,其中Prob[success]表示签名 z \in \mathcal{R}_{l \cdot(d-1\;024)} \times \mathcal{R}_{l \cdot(d-1\;024)}的概率.

    在实际选择TLMS方案参数时,综合考虑签名协议重复次数、多重签名长度和安全强度等因素,给出2组方案性能较优的参数集(表 1).

    表  1  方案参数集
    Table  1.  The sets of scheme parameters
    参数 集合Ⅰ 集合Ⅱ
    维数N 1 024 1 024
    q 2 147 483 659 4 294 967 371
    参数p 2 2
    人数l 5 5
    范围d 4 194 304 4 194 304
    重复次数E 12.19 12.19
    下载: 导出CSV 
    | 显示表格

    表 1中参数集合I为例,介绍如何计算签名私钥长度、验证公钥长度、多重签名长度以及根式埃尔米特因子ξ.签名私钥ski由2个从 \mathcal{R} 1中随机抽取的多项式sivi组成,因此,签名私钥长度可表示为\left\|\mathrm{sk}_{i}\right\|=2 N\left\lceil\log _{2} 3\right\rceil=3\;246 比特.验证公钥pk_{i} \in \mathcal{R}_{q} , 则验证公钥长度为\left\|\mathrm{pk}_{i}\right\|=2 N\left\lceil\log _{2} q\right\rceil=31744 比特.多重签名σ由4个多项式组成,其中, t_{1}, t_{2} \in \mathcal{R}_{q}, z \in \mathcal{R}_{l \cdot(d-1\;024)} \times \mathcal{R}_{l \cdot(d-1\;024)}, g \in \mathcal{R}_{q}^{3} ,因此,多重签名长度为 \|\sigma\|=2 N\left\lceil\log _{2} q\right\rceil+2 N\left\lceil\log _{2}(2 l \cdot(d-1\;024)+1)\right\rceil+ 3 N\left\lceil\log _{2} q\right\rceil=210578比特.此时,可得到TLMS方案的根式埃尔米特因子 \xi=(\beta / \sqrt{q})^{1 /(2 N)}=1.0057.同理可知:TLMS方案选取表 1中参数集合II时,私钥长度、公钥长度及多重签名长度分别为3 246、32 768、215 698比特,根式埃尔米特因子为1.005 5.

    表 1可知TLMS方案所需参数较大,从而产生较长的公钥和签名.但TLMS方案可支持公钥聚合功能,降低签名验证代价;且通过结合同态承诺方案减少签名者之间的通信次数,降低签名消耗的通信代价.因此,TLMS方案是降低多重签名通信研究的一次有意义的尝试.

    多重签名是一种特殊的数字签名,其允许一组签名者合作对消息产生压缩的签名,可应用于合同签署、可信路由以及区块链等场景.本文构造了一个基于格上困难问题并支持公钥聚合功能的两轮多重签名方案,在随机预言机模型中证明了该方案的安全性.本方案具有较低的通信量和计算量,并能够抵抗量子攻击,可满足未来量子时代最新的安全需求.

    然而,在随机预言机模型下证明安全的方案在现实应用中可能难以保证安全性.因此,如何在标准模型下构造可抵抗量子攻击的有效多重签名方案可作为进一步的研究方向.

  • 期刊类型引用(8)

    1. 韦彩飞. 园林植物马缨丹引种过程中生物入侵机制与防治对策. 现代园艺. 2025(01): 110-113 . 百度学术
    2. 陈馨,谭晶华. 恶性入侵植物马缨丹研究现状计量分析. 内江师范学院学报. 2024(10): 58-68 . 百度学术
    3. 杨海君,郭佳源,谭菊,谭璐,朱姝,吴亮,张皓,牛鸿宇,王凡. 镉胁迫对2种酸性土壤地肤生长及其修复镉能力的影响. 中国环境科学. 2023(05): 2423-2433 . 百度学术
    4. 刘睿,聂庆娟,王晗. 木本园林植物对土壤重金属的富集及修复效应研究进展. 北方园艺. 2021(08): 117-124 . 百度学术
    5. 王建乐,谢仕斌,王冠,涂国权,方战强. 不同提取剂提取土壤中重金属能力的对比研究. 华南师范大学学报(自然科学版). 2020(01): 55-62 . 百度学术
    6. 张金兰,黄程亮,黄秋鑫,陈克海. 山地水田土壤环境质量评价及重金属来源解析. 华南师范大学学报(自然科学版). 2020(03): 54-61 . 百度学术
    7. 李玉霞,尚春琼,朱珣之. 入侵植物马缨丹研究进展. 生物安全学报. 2019(02): 103-110 . 百度学术
    8. 卓逢,张小凤,颜廷秀,胡尊河,黄丹,靖元孝. 变形球囊霉(Glomus versiforme)和钢渣复合处理对玉米生长和积累镉/铅的影响. 华南师范大学学报(自然科学版). 2019(05): 75-83 . 百度学术

    其他类型引用(3)

计量
  • 文章访问数:  1401
  • HTML全文浏览量:  177
  • PDF下载量:  80
  • 被引次数: 11
出版历程
  • 刊出日期:  2018-06-24

目录

/

返回文章
返回