多重签名^[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方案)，并在随机预言机模型中证明该方案的安全性.

1.   预备知识

1.1   符号说明

N表示一个正整数且为2的方幂，q表示一个素数；$\mathcal{R}$表示多项式环$\mathbb{Z} [x] /\left(x^{N}+1\right), \mathcal{R}_{q}$表示多项式环$\mathbb{Z} [x] /\left(x^{N}+1\right), \mathcal{R}_{q}$中环元素为N-1阶多项式且每一项系数属于$[-(q-1) / 2, (q-1) / 2], \mathcal{R}_{d}$表示$\mathcal{R}_{q}$的子集且每一项系数属于$[-d, d]$，其中$d \in \mathbb{N}_{+}$.文中所有向量均为列向量，$\boldsymbol{v}^{\mathrm{T}}$表示向量v的转置；$\|\boldsymbol{v}\|_{1}、 \|\boldsymbol{v}\|_{2}、 \|\boldsymbol{v}\|_{\infty}$分别表示向量v的1-范数、2-范数、无穷范数.对于正整数$\eta, \mathcal{S}_{\eta}$表示$\mathcal{R}$中无穷范数至多为η的多项式集合.假设A表示集合，$a \stackrel{\$}{\leftarrow} A$表示从A中均匀随机抽取元素a.参考文献[13]，D₃₂^N表示阶为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.2   困难问题及引理

问题1^[15]   (DCK_{q, 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-SIS_{m, 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]  选择参数N≥p≥1且为2的方幂，参数q为素数且满足$q = 2p + 1({\rm{mod}}\;4p)$，则多项式x^N+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存在逆元.

1.3   多重签名及其安全性

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

(1) MKeyGen：密钥生成算法，给定安全参数θ，该概率算法为每位签名者i生成签名私钥sk_i和验证公钥pk_i；

(2) MSign：多重签名生成算法，输入公钥集合PK={pk₁, pk₂, …, pk_l}和消息m，若签名成功, 则该概率算法返回多重签名σ，否则返回⊥；

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

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

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

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

step 2：伪造者自适应地发起消息m_i(1≤i≤q)的签名查询，挑战者执行签名生成算法产生签名σ_i并发送给伪造者；

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

1.4   广义分叉引理

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=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)$.

2.   TLMS方案

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等待接收其子节点j∈C_i发送的数据$\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为树结构Τ的根节点，则设置t₁=t_{i, 1}、t₂=t_{i, 2}以及apk=apk_i，查询c←H₂(t₁, t₂, apk, m)，并向其子节点发送数据(t₁, t₂, apk).否则，等待接收数据(t₁, t₂, apk)，查询c←H₂(t₁, t₂, apk, m)，并向其子节点发送数据(t₁, t₂, apk).

响应阶段：签名者i等待接收其子节点j∈C_i发送的数据$\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.

3.   方案分析

3.1   正确性分析

若每位签名者均诚实地执行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)$，从而

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

3.2   安全性分析

定理1  在随机预言机模型下，若存在1个概率多项式时间的伪造者$\mathcal{F}$，在至多进行q_H次随机预言机查询、q_S次签名查询且至多涉及l_max个公钥的前提下，成功伪造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，哈希函数H₁的响应$\lambda_{1, 1}, \lambda_{1, 2}$，$\cdots, \lambda_{1, q_{H}}$，哈希函数H₂的响应$\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}$的响应值，L₃通过$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^*放在表L₃首位.同时，算法$\mathcal{A}$维护2个初始化为0的计数器ctr₁和ctr₂，分别记录随机预言机H₁和H₂的查询次数.假设攻击者$\mathcal{F}$没有发起重复查询.

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

(ii) 随机预言机H₁(PK, pk_i)查询.算法$\mathcal{A}$查询表L₁(PK, pk_i)，若其已定义则直接返回L₁(PK, pk_i).否则，算法$\mathcal{A}$查询表L₃pk_i，若其未定义，则将公钥pk_i存储于表L₃.然后，算法$\mathcal{A}$解析公钥集合PK={pk₁, pk₂, …, pk_l}, 并检查每个公钥pk_j∈PK是否已存储于表L₃.在保证每个公钥pk_j∈PK均存储于表L₃后，再依据以下3种情况一次性赋值H₁(PK, pk_j)满足1≤j≤l：

① $\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}$增加计数器ctr₁并设置L₁(PK, pk_j)=λ_{1, ctr1}；对于情况②、③，算法$\mathcal{A}$从D₃₂^N随机抽取元素并存储于表L₁(PK, pk_j).在分配所有L₁(PK, pk_j)后，算法$\mathcal{A}$计算聚合公钥apk.若伪造者$\mathcal{F}$已查询哈希函数H₂(·, ·, apk, m)或已进行涉及apk的签名查询，则此时事件E₁发生，算法$\mathcal{A}$放弃签名协议并返回⊥.否则，算法$\mathcal{A}$返回L₁(PK, pk_i).

(iii) 随机预言机H₂(t₁, t₂, apk, m)查询.算法$\mathcal{A}$首先查询表L₂(t₁, t₂, apk, m), 若其已定义则直接返回L₂(t₁, t₂, apk, m).否则，算法$\mathcal{A}$进行内部查询H₀(m)并存储相关数据.然后，算法$\mathcal{A}$增加计数器ctr₂并设置L₂(t₁, t₂, apk, m)=λ_{2, ctr2}，返回L₂(t₁, t₂, apk, m).

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

在签名协议的第1轮交互中，算法$\mathcal{A}$首先判断其公钥pk^*是否属于公钥集合PK.若不存在，则算法$\mathcal{A}$终止签名协议并输出⊥，否则解析公钥集合PK={pk₁, pk₂, …, pk^*=pk_i, …, pk_l}.然后，算法$\mathcal{A}$分别进行查询H₀(m)和H₁(PK, pk_j)，并计算聚合公钥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$, 并向其父节点发送数据(t_{i, 1}, t_{i, 2}, apk_i).

在签名协议的第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发送的数据(z_j, g_j)后，计算$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)=c$和$H_{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$以及t₂= $\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次随机预言机H₁查询，$H_{2}\left(t_{1}, t_{2}, \mathrm{apk}, m\right)=\lambda_{2, J}$表示第J次随机预言机H₂查询.若伪造签名$\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.在事件E₁和事件E₂(即：伪造者$\mathcal{F}$找到2组不同公钥集合PK和PK′，且使用这2组不同公钥集合可产生相同聚合公钥apk)不发生的情况下，算法$\mathcal{A}$模拟的多重签名环境与真实签名环境不可区分.因此，

接着，可构造多项式时间算法$\mathcal{B}$，其执行分叉算法GF $_{\mathcal{A}}$可得有关聚合公钥apk的等式.算法$\mathcal{B}$输入参数x，随机预言机H₁的响应值$\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次随机预言机查询H₂(t₁, t₂, apk, m).这表明在此分叉点前，算法$\mathcal{A}$模拟的2次签名协议执行环境完全一致.因此，随机预言机查询H₂(t₁, t₂, apk, m)的参数是相同的，即t₁=t₁^*，t₂=t₂^*，apk=apk^*，m=m^*.随机预言机查询H₀(m)发生在分叉点H₂(t₁, t₂, apk, m)之前，因此，算法$\mathcal{A}$的2次执行中，随机预言机查询H₀(m)的结果相同.同理，随机预言机查询H₁(PK, pk_j)亦发生在分叉点之前，即有PK=PK^*，u_j=u_j^*且$1 \le j \le l$.另外，算法$\mathcal{A}$的2次执行均产生有效签名，因此，如下2个验证等式必定成立：

依据t₁=t₁^*，合并式(1)、(2)，可得：

此时，算法$\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, 可得：

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

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

随后，仍需构造一个可攻击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次随机预言机查询H₁(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)可得:

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

由于$\|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)$，因此

接下来需要证明

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

则存在另一个sk″，使得

在模拟签名协议中，签名生成过程未使用算法$\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}$的接受概率为

3.3   参数分析

TLMS方案的安全性是由DCK_{q, N}问题的困难性、环上最小整数解(Ring-SIS)问题的困难性以及找到哈希函数原像的困难性所共同决定的.哈希函数H₁、H₂的值域为D₃₂^N，可知H₁和H₂的安全强度是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为例，介绍如何计算签名私钥长度、验证公钥长度、多重签名长度以及根式埃尔米特因子ξ.签名私钥sk_i由2个从$\mathcal{R}$ ₁中随机抽取的多项式s_i和v_i组成，因此，签名私钥长度可表示为$\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.005$7.同理可知:TLMS方案选取表 1中参数集合II时，私钥长度、公钥长度及多重签名长度分别为3 246、32 768、215 698比特，根式埃尔米特因子为1.005 5.

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

4.   结论

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

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