-
摘要:
物联网和区块链等技术的兴起和发展,使得多方协同签名协议重新受到了关注. 多方协同签名是一种特殊的数字签名,要求多个用户进行交互后共同对一个消息产生合法的签名,以达到认证的目的. 优点在于相比起每个用户分别进行签名可以缩短尺寸,同时使用分布式的方法,任何一方都无法独自进行签名,防范了因为单个用户的密钥丢失或被劫持而导致被冒充身份的隐患. 另一方面,量子计算机的进展对传统的公钥密码方案构成了潜在的威胁,美国国家标准与技术研究院(National Institute of Standards and Technology,NIST)在2016年启动抗量子密码(post-quantum cryptography,PQC)的国际标准征集项目,并于2022年7月确定了被选为标准的算法. 同时,基于其入选的数字签名方案(例如CRYSTALS-Dilithium)的协同签名方案也已经陆续出现. 2019 年,中国密码学会举办了全国密码算法设计竞赛,其中公钥组获得一等奖的Aigis-sig签名方案采用了与Dilithium类似的结构. 基于Aigis-sig数字签名方案设计了一种两方协同签名方案,称之为Aitps,并根据其提供的参数进行了实例化和对比,得到了相比已有的所有基于Dilithium的两方协同签名方案更优的密钥和签名大小,例如在同等的安全强度下签名尺寸可缩减 20% 以上. 此外,该方案也可以扩展为多方协同签名.
Abstract:Recent years, with the advancement of the IoT and blockchain, multi-party signature protocols have received renewed attention. Multi-party signature is a special digital signature that requires users to interact with each other to jointly generate a signature for a message and achieve the authentication. Compared with each user signing respectively, the advantage is that the key size can be greatly decreased, and every party cannot get a legal signature only by itself, which can be used to prevent the danger of being impersonated when user’s key is lost or hijacked. On the other hand, the progress of quantum computers poses a potential threat to the traditional public key cryptography scheme, the PQC(post-quantum cryptography) project was organized by the NIST(National Institute of Standards and Technology) in the US since 2016, and it determined the algorithm that was standardized in July 2022. At the same time, the multi-party signature based on its candidate digital signature schemes (such as CRYSTALS-Dilithium) also appeared. Chinese Association for Cryptologic Research(CACR) also held a national cryptographic algorithm design competition in 2019, Aigis-sig, which is the first prize signature algorithm, adopts the similar structure with Dilithium. In this paper, Aitps is proposed, which is a two-party signature based on Aigis-sig. Compared with the existing Dilithium-based two-party signatures, Aitps has better key sizes and signature sizes. For example, the signature sizes can be reduced by more than 20% at the same security level. Lastly, Aitps can also be extended to multi-party signature.
-
随着互联网的飞速发展,手机等移动设备的适用范围不断扩大. 根据中国互联网络信息中心发布的第49次中国互联网报告[1],截至2021年12月,我国网民规模已达10.32亿人次,其中即时通信用户规模达10.07亿人次,网络支付用户规模达9.04亿人次,网络购物用户规模达8.42亿人次,在线办公用户规模达4.69亿人次. 移动设备日渐丰富的功能也带来了更严重的隐私信息泄露问题. 作为传统签名的替代,数字签名伴随着网络安全的需求出现,为用户提供身份认证和数据完整性认证等,在移动设备的各个功能中发挥重要作用.
然而,数字签名的安全性建立在签名密钥安全的基础上,如果密钥不慎泄露,或者被恶意的网站和应用程序等窃取,可能会出现恶意者冒充等情况,导致隐私信息被滥用、财产损失甚至威胁到国家安全. 目前用来保护签名密钥安全的方法主要分为2种[2]:借助硬件设备令牌保护密钥和使用多方协同签名的思想保护密钥. 受限于便利性和成本,前者难以大规模部署到移动设备或物联网设备中;而后者则是由2个及以上的设备分别存储密钥的一部分,签名时需要多个设备交互完成,任何一方都无法独立地进行签名,分布式的处理能较好地保护密钥安全.
多方协同签名是一种特殊的门限签名,参与签名的用户Pi首先运行密钥生成算法获得私钥ski,然后通过与其余用户的交互生成公钥pk. 签名过程也需要交互,对于给定的消息μ,如果所有的用户都同意对μ进行签名并诚实参与交互,则交互后得到一个能用pk验证的合法消息签名对(μ,σ).
尽管多方协同签名协议已经被研究了很长时间,然而现有的大多数工作都集中在多方协同RSA签名[3-4]、多方协同ECDSA签名[5-7]、多方协同Schnorr签名[8-10]以及多方协同SM2签名[2]等, 这些方案都基于整数分解或者离散对数困难假设,Shor[11]已经证明了这些困难假设无法抵抗量子计算机的攻击.
相比之下,基于格上的困难假设构造的密码学方案,目前被认为是抗量子的,同时具有运算快、平均情况和最坏情况困难性等价等优点[12], 受到了研究者们的广泛关注. 美国国家标准技术研究院 (National Institute of Standards and Technology, NIST)举办的抗量子密码(post-quantum cryptography,PQC)征集项目的抗量子密钥封装和数字签名方案,就有相当一部分是基于格的方案,例如CRYSTALS-Dilithium[13],CRYSTALS-Kyber[14],Falcon[15]等. 中国密码学会在2019年举办的全国密码算法设计竞赛中的获奖算法大部分也是基于格困难问题构造的,例如Aigis-enc/sig[16]和 LAC.PKE[17]等. 其中Aigis设计团队观察到Dilithium签名方案实际上可以非对称地选择参数,在保证总的重复次数相当的情况下,通过改变前后2个拒绝抽样的条件及其决定的重复次数,能取得更佳的效果. 因而,该团队使用了参数选取更加灵活的非对称模格问题AMLWE/AMSIS(asymmetry module learning with errors/short integer solutions)来代替Dilithium中的模格问题MLWE/MSIS(module learning with errors/short integer solutions),设计出Aigis-sig签名方案,在安全性不变或略强的前提下达到更好的综合效果,特别是拥有更短的公钥、私钥和签名长度,具体参见1.5节. 值得一提的是,基于AMLWE/AMSIS的Aigis方案不仅性能优秀,它还是我国学者自主设计的抗量子密码方案,也已经出现在不同平台上对其实现进行优化的相关工作[18-19]. 除了提升算法本身和优化实现之外,基于其设计特殊类型签名,例如能更好地保护密钥安全的多方协同签名,对研究国产抗量子密码算法、维护网络安全和国家安全也具有重要的意义.
2019年,Cozzo等人[20]对NIST征集的抗量子数字签名方案中所有进入第2轮的算法转换成多方协同签名(分布式签名)进行了评估,得出的结论是:如果直接使用已有的安全多方计算的通用技术,基于格的方案将需要用到线性秘密共享和混淆电路等,以及它们之间的互相转换,会带来较大的计算开销,需要较长的时间.
2022年,Damgard等人[21]利用Lyubashevsky[22]提出的构造基于格的数字签名的“FSwA(Fiat-Shamir with aborts)”范式,得到了2个交互轮数较小的基于格的多方协同签名协议(使用加法同态承诺方案需要交互3轮,使用陷门加法同态承诺方案仅需要交互2轮),文中的秘密向量是从离散高斯分布中选取的,承诺方案则来自于文献[23]及其扩展方案,该协同签名方案可以看作Dilithium签名方案的分布式版本,文献[23]中给出了完整的安全性证明,其安全性基于MSIS问题和MLWE问题.
Vakarjuk等人[24]也给出了一个3轮的两方协同签名方案——Dilizium,与文献[21]中方案的不同之处在于Dilizium使用SWIFFT同态Hash函数[25]替换加法同态承诺方案,虽然得到了更小的密钥和签名尺寸,但是其缺点在于依赖Rejected MLWE困难假设,是一种启发式的困难假设[26],同时SWIFFT同态Hash函数并不是对所有输入都是加法同态的. 现在也已经出现了对具备同态性的Hash函数的量子攻击方法[27],这可能会威胁到安全性,尽管如此,我们仍将该方案纳入对比.
此外,文献[21, 24]中基于Dilithium设计的两方协同签名方案均未考虑Dilithium中用到的签名尺寸压缩技巧[28],而最新方案Dilizium 2.0[29]采用了类似压缩技术,使其更接近于NIST标准化的Dilithium算法,然而该工作并没有评估实际的效率(重复次数)、密钥和签名尺寸等,也未进行参数选取和实例化.
本文的主要贡献包括3个方面:
1) 采用AMSIS/AMLWE问题对基于MSIS/MLWE问题的Dilizium 2.0两方协同签名方案进行了修改和推广,得到新方案Aitps. 充分利用AMSIS/AMLWE的非对称特性能够更灵活地选择参数,从而在安全性、计算效率、密钥和签名长度这3个方面达到更好的权衡,得到更优的综合性能. 值得注意的是,Aitps方案可以被看作是Dilizium 2.0方案的一个扩展,在选取适当参数时,Aitps和Dilizium 2.0 本质上等价,即Dilizium 2.0可以看成Aitps的一个特例. 除此以外,Dilithium设计团队和Aigis设计团队对其方案的后续优化,也适用于本文提出的方案.
2) 使用“FSwA”范式构造基于格的多方签名在安全性上需要解决的一个关键问题是防止未通过拒绝抽样时的私钥信息泄露,我们使用同态承诺解决了这个问题(见第2节). 对于新设计的Aitps两方协同签名方案,我们提供了完整的安全性证明,结果表明其可以有效保护各方的签名密钥,具备两方协同签名在选择消息攻击下的存在性不可伪造性[5].
3) 为了对比效果,本文给出了Aitps方案的重复次数、密钥和签名大小的评估方法,该评估方法也适用于Dilizium 2.0方案. 我们使用Dilithium第2轮的参数[13]和Aigis-sig的参数[16]将Dilizium 2.0和Aitps全部进行了实例化,并将Dilizium[24](其密钥和签名尺寸优于文献[21])也进行计算并纳入对比,相比之下,本文方案的密钥以及签名尺寸优于现有的所有基于Dilithium的两方协同签名方案,例如在同等的安全强度下,签名尺寸可缩减20%以上. 据我们所知,该结果也是基于格的两方协同签名方案中最优的.
1. 预备知识
1.1 符号说明
本文用{{\boldsymbol{A}}^{\rm{T}}}表示矩阵{\boldsymbol{A}}的转置,{{\boldsymbol{I}}_k}表示k阶单位矩阵,\left\lceil {x} \right\rceil 表示大于等于实数x的最小整数,lb表示以2为底的对数.
R和{R_q}分别表示多项式环\mathbb{Z}[x]/({{x\,}^n} + 1)和{\mathbb{Z}_q}[x]/ ({{x\,}^n} + 1). 其中,n为正整数,n - 1即为环中的多项式的最高次数,实际方案中一般选取n为2的幂次(例如n = 256);q表示环{R_q}的模数,一般选取较大的素数,在选取时需要综合考虑方案的其他参数和工程实现的效率. 表1给出了一套具体参数的例子.
表 1 Dilithium 和Aigis-sig 的推荐参数Table 1. Recommended Parameters of Dilithium and Aigis-sig参数类型 Dilithium 安全级别 参数类型 Aigis-sig 安全级别 128 b 192 b 256 b 128 b 192 b 256 b 输入参数设置 多项式次数n 256 256 256 输入参数设置 多项式次数n 256 256 256 矩阵行数k 4 5 6 矩阵行数k 4 5 6 矩阵列数l 3 4 5 矩阵列数l 3 4 5 模数q 8380417 8380417 8380417 模数q 2021377 3870721 3870721 私钥sk1, sk2范围\eta 6 5 3 私钥sk1范围\eta 2 2 1 私钥sk2范围\eta' 3 5 5 c中\pm 1 个数\tau 60 60 60 c中\pm 1 个数\tau 60 60 60 签名截取参数\beta 325 275 175 签名截取参数\beta 120 120 60 签名截取参数\beta' 175 275 275 签名范围参数\gamma 523776 523776 523776 签名范围参数\gamma 131072 131072 131072 签名范围参数 \gamma' 261888 261888 261888 签名范围参数 \gamma' 168448 322560 322560 输出参数性能 公钥大小/ B 1184 1472 1760 输出参数性能 公钥大小/ B 1056 1312 1568 私钥大小/ B 2800 3504 3856 私钥大小/ B 2448 3376 3888 签名大小/ B 2044 2701 3366 签名大小/ B 1852 2445 3046 期望重复次数 5.90 6.60 4.30 期望重复次数 5.86 7.61 6.67 经典安全性 100 141 174 经典安全性 99 141 179 量子安全性 91 128 158 量子安全性 90 128 163 对于多项式w = {w_0} + {w_1}x + … + {w_{n - 1}}{x^{n - 1}} \in R ,其中{w_i} 为整数,用\Vert w{\Vert }_{\infty }={\mathrm{max}}_{i}\left|{w}_{i}\right| 表示其{\ell _\infty }范数,用\Vert w{\Vert }_{2}= \sqrt{{\displaystyle \sum _{i}|{w}_{i}{|}^{2}}}表示其{\ell _2}范数. 对于由多项式组成的向量{\boldsymbol{p}} = {({p_1},{p_2},…,{p_k})^{\rm{T}}} \in {R^k},其中 {p_i} 为环R中的多项式,用\Vert {\boldsymbol{p}}{\Vert }_{\infty }={\mathrm{max}}_{i}\left|\right|{p}_{i}|{|}_{\infty }表示其{\ell _\infty }范数,用\Vert {\boldsymbol{p}}{\Vert }_{2}=\sqrt{{{\displaystyle \sum _{i}\Vert {p}_{i}\Vert }}^{2}}表示其{\ell _2}范数. {R_q}中的定义类似.
对于\eta > 0,用{S_\eta }表示由所有的满足 \Vert w{\Vert }_{\infty }\le \eta 的多项式w \in R(或{R_q})组成的集合.
对于集合(或分布)D,用x{ \leftarrow _\$ }D表示从集合(或按照分布)D中均匀随机选取x.
1.2 格上的困难问题
本文直接采用正规型(A)MLWE/(A)MSIS问题及假设,定义如下.
定义1. MLWE问题[13, 30]. 参数为(q,k,l,\eta )的MLWE问题指的是对于给定的正整数q,k,l以及\eta > 0,定义分布{D_1}和{D_2}为:
1) {D_1}:{\boldsymbol{A}}{ \leftarrow _\$ }R_q^{k \times l},({{\boldsymbol{s}}_1},{{\boldsymbol{s}}_2}){ \leftarrow _\$ }S_\eta ^l \times S_\eta ^k,计算得到{\boldsymbol{t}} = {\boldsymbol{A}}{{\boldsymbol{s}}_1} + {{\boldsymbol{s}}_2} \in R_q^k.
2) {D_2}:{\boldsymbol{A}}{ \leftarrow _\$ }R_q^{k \times l},{\boldsymbol{t}}{ \leftarrow _\$ }R_q^k.
由{D_1}中的({\boldsymbol{A}},{\boldsymbol{t}})恢复({{\boldsymbol{s}}_1},{{\boldsymbol{s}}_2})称为计算性MLWE(computational MLWE)问题,区分2个分布{D_1}和 {D_2} 中的({\boldsymbol{A}},{\boldsymbol{t}})称为判定性MLWE(decisional MLWE)问题.
定义2. AMLWE问题[16]. 参数为(q,k,l,\eta ,\eta ')的AMLWE问题指的是对于给定的正整数q,k,l以及\eta ,\eta ' > 0,定义分布{D_3}和 {D_4} 为:
1){D_3}:{\boldsymbol{A}}{ \leftarrow _\$ }R_q^{k \times l},({{\boldsymbol{s}}_1},{{\boldsymbol{s}}_2}){ \leftarrow _\$ }S_\eta ^l \times S_{\eta '}^k, 计算得到{\boldsymbol{t}} = {\boldsymbol{A}}{{\boldsymbol{s}}_1} + {{\boldsymbol{s}}_2} \in R_q^k.
2) {D_4}:{\boldsymbol{A}}{ \leftarrow _\$ }R_q^{k \times l},{\boldsymbol{t}}{ \leftarrow _\$ }R_q^k.
由{D_3}中的({\boldsymbol{A}},{\boldsymbol{t}})恢复({{\boldsymbol{s}}_1},{{\boldsymbol{s}}_2})称为计算性AMLWE问题(computational AMLWE),区分2个分布{D_3}和{D_4}中的({\boldsymbol{A}},{\boldsymbol{t}})称为判定性AMLWE问题(decisional AMLWE).
Zhang等人[16]已经证明,对于目前已知最好的求解算法,有困难性关系:
{\text{MLW}}{{\text{E}}_{q,k,l,\min (\eta ,\eta ')}} \leqslant {\text{AMLW}}{{\text{E}}_{q,k,l,\eta ,\eta '}} \leqslant {\text{MLW}}{{\text{E}}_{q,k,l,\max (\eta ,\eta ')}}. 定义3. MSIS问题[13]. 参数为(q,k,l,\delta )的MSIS问题指的是对于正整数q,k,l以及\delta > 0和矩阵{\boldsymbol{A}} \in R_q^{k \times l},计算非零向量{\boldsymbol{x}} \in R_q^{k + l}使其满足[{\boldsymbol{A}}\Vert {{\boldsymbol{I}}}_{k}]{\boldsymbol{x}}= {\bf{ 0}}\;\mathrm{mod}\;q且\Vert {\boldsymbol{x}}{\Vert }_{\infty }\le \delta.
定义4. AMSIS问题[16]. 参数为(q,k,l,\delta ,\delta ')的AMSIS问题指的是对于正整数q,k,l以及\delta ,\delta ' > 0和矩阵{\boldsymbol{A}} \in R_q^{k \times l},计算非零向量{\boldsymbol{x}} = ({\boldsymbol{x}}_1^{\rm{T}},{\boldsymbol{x}}_2^{\rm{T}}) \in R_q^{k + l}使其满足[{\boldsymbol{A}}\Vert {{\boldsymbol{I}}}_{k}]{\boldsymbol{x}}= {\bf{0}}\;\mathrm{mod}\;q且\Vert {{\boldsymbol{x}}}_{1}{\Vert }_{\infty }\le \delta ,\Vert {{\boldsymbol{x}}}_{2}{\Vert }_{\infty }\le {\delta }^{' }.
Zhang等人[16]已经证明,对于目前已知最好的求解算法,有困难性关系:
{\text{MSI}}{{\text{S}}_{q,k,l,\max (\delta ,\delta ')}} \leqslant {\text{AMSI}}{{\text{S}}_{q,k,l,\delta ,\delta '}} \leqslant {\text{MSI}}{{\text{S}}_{q,k,l,\min (\delta ,\delta ')}}. 1.3 (同态)承诺方案
承诺方案最早由Chor等人[31]在研究可验证的秘密分享时提出,现在已经被用在各种特殊类型签名中,例如环签名[32-33]、群签名[34]等. 在承诺方案中,对于给定的消息{\boldsymbol{m}} \in {\mathcal{S}_{\boldsymbol{m}}},承诺者选择随机向量{\boldsymbol{r}} \in {\mathcal{S}_{\boldsymbol{r}}}用来计算{\boldsymbol{m}}的承诺值{\boldsymbol{com}} = Commi{t_{{\boldsymbol{ck}}}}({\boldsymbol{m}};{\boldsymbol{r}}),其中{\boldsymbol{ck}} \in {\mathcal{S}_{{\boldsymbol{ck}}}}是承诺密钥,并将承诺值{\boldsymbol{com}}发送给接收者. 在承诺打开阶段,承诺者将与承诺值相关的信息发送给接收者,接收者能利用承诺值以及相关信息计算得到一个打开值(opening),并验证其确实是最初承诺的消息值.
除了具备正确性之外,承诺方案还需要具备隐藏性和绑定性2个安全属性.
1) 隐藏性(hiding)指的是承诺值不会泄露被承诺值的任何信息,即通过{\boldsymbol{com}} = Commi{t_{{\boldsymbol{ck}}}}({\boldsymbol{m}};{\boldsymbol{r}})无法得到关于{\boldsymbol{m }}或{\boldsymbol{r}}的信息.
2) 绑定性(binding)指的是打开一个承诺不能得到2个不同的值,即打开{\boldsymbol{com}} = Commi{t_{{\boldsymbol{ck}}}}({\boldsymbol{m}};{\boldsymbol{r}})得到({\boldsymbol{m}}' ,{\boldsymbol{r}}' ),则({\boldsymbol{m}}' ,{\boldsymbol{r}}' )\not = ({\boldsymbol{m}},{\boldsymbol{r}})的概率是可忽略的.
根据敌手的能力和计算时间进行分类:若敌手拥有无限计算时间与资源则称为统计隐藏性(绑定性),若限制在多项式时间则称为计算隐藏性(绑定性).
本文使用Esgin等人[35]提出的基于格的承诺方案.先产生承诺密钥{\boldsymbol{ck}} = ({{\boldsymbol{A}}_1}\left|\right|{{\boldsymbol{A}}_2}),其中{{\boldsymbol{A}}_1} = [{{\boldsymbol{I}}_k}\left|\right|{\boldsymbol{A}}_1'],{\boldsymbol{A}}_1'{ \leftarrow _\$ }R_q^{n \times (k - n)},{{\boldsymbol{A}}_2}{ \leftarrow _\$ }R_q^{n \times l}都是均匀随机选取的. 在对消息{\boldsymbol{m}} \in R_q^l进行承诺时,选取随机向量{\boldsymbol{r}}{ \leftarrow _\$ }{\mathcal{S}_{\boldsymbol{r}}} = S_\alpha ^\kappa,得到承诺{\boldsymbol{com}} = {{\boldsymbol{A}}_1} \cdot {\boldsymbol{r}} + {{\boldsymbol{A}}_2} \cdot {\boldsymbol{m}}. 在承诺打开阶段,用消息{\boldsymbol{m}}、随机数{\boldsymbol{r}}以及承诺值{\boldsymbol{com}},验证{\boldsymbol{com}} = {{\boldsymbol{A}}_1} \cdot {\boldsymbol{r}} + {{\boldsymbol{A}}_2} \cdot {\boldsymbol{m}}且\Vert ({\boldsymbol{r}},{\boldsymbol{m}}){\Vert }_{2}不超过某个阈值,若均通过则输出1,否则输出0.
在满足正确性和安全性后,该承诺方案还具备3个性质[21]:
1) 密钥均匀性(uniform key). 产生承诺密钥的算法得到的承诺密钥{\boldsymbol{ck}} \in {\mathcal{S}_{{\boldsymbol{ck}}}}在{\mathcal{S}_{{\boldsymbol{ck}}}}上均匀分布.
2) \xi -bits最小熵.称一个承诺方案至少有\xi -bits最小熵,如果对于\forall {\boldsymbol{ck }}\in {\mathcal{S}_{{\boldsymbol{ck}}}}和\forall {\boldsymbol{m}} \in {\mathcal{S}_{\boldsymbol{m}}},均有
\xi \leqslant - {\rm{lb}}{\max _{{\boldsymbol{com}} \in {\mathcal{S}_{{\boldsymbol{com}}}}}}Pr[Commi{t_{{\boldsymbol{ck}}}}({\boldsymbol{m}};{\boldsymbol{r}}) = {\boldsymbol{com}}:{\boldsymbol{r}} \leftarrow {\mathcal{S}_{\boldsymbol{r}}}]. 3) 加法同态性. 对于任意的{{\boldsymbol{m}}_1},{{\boldsymbol{m}}_2} \in {\mathcal{S}_{\boldsymbol{m}}}以及随机数{{\boldsymbol{r}}_1},{{\boldsymbol{r}}_2} \in {\mathcal{S}_{\boldsymbol{r}}},计算得到{{\boldsymbol{com}}_1} = Commi{t_{{\boldsymbol{ck}}}}({{\boldsymbol{m}}_1};{{\boldsymbol{r}}_1})和{{\boldsymbol{com}}_2} = Commi{t_{{\boldsymbol{ck}}}}({{\boldsymbol{m}}_2};{{\boldsymbol{r}}_2}),满足加法同态性,即
Ope{n_{{\boldsymbol{ck}}}}({{\boldsymbol{m}}_1} + {{\boldsymbol{m}}_2},{{\boldsymbol{r}}_1} + {{\boldsymbol{r}}_2},{{\boldsymbol{com}}_1} + {{\boldsymbol{com}}_2}) = 1 1.4 CRYSTALS-Dilithium数字签名方案
2022年7月,NIST宣布了PQC项目第3轮的评审结果[36],确定了4种即将标准化的算法,其中最为推荐的是CRYSTALS-Kyber(密钥封装)和 CRYSTALS-Dilithium(数字签名),此外,另一个基于格的签名方案Falcon和基于Hash的签名方案SPHINCS+[37]也将标准化. 在数字签名方面,根据设计团队向NIST提交的材料以及官方评价显示, Falcon是利用“Hash-and-Sign”范式构造,虽然拥有更短的尺寸,但其签名算法内部逻辑较复杂,实现难度较大;SPHINCS+是一类基于Hash的无状态签名方案,其安全性依赖于底层Hash函数的安全性,提供可靠的安全保证,然而会导致性能上的巨大成本. 相对而言,Dilithium拥有很强的安全性和优秀的性能,能胜任绝大多数场景需求.
Dilithium是一类基于格上的困难问题构造的数字签名算法,算法的设计用到了“Fiat-Shamir with Aborts”范式,并使用了一些压缩技巧[28, 38],主要具备3个优点[13]:
1) 容易安全地实现. 此前的基于格的数字签名方案[39-40]等需要从离散高斯分布中抽样得到秘密值,效率较低,还容易遭到侧信道攻击而导致实现的不安全[41-42]. 与它们不同,Dilithium签名方案只需要进行均匀抽样,且除了抽样之外,其余的运算操作(例如多项式乘法和舍入)都可以在恒定时间内完成,这有利于增强实现上的安全性.
2) 公钥+签名尺寸优. 为了能长期使用,Dilithium团队提交给NIST的参数选取非常保守,即便如此,Dilithium方案的“公钥+签名”的尺寸也是现有的不使用离散高斯抽样的格签名方案中最小的.
3) 模块化切换. 只需在环上进行更多或更少的操作,或者修改其中所用的可扩展输出长度Hash函数(XOF,推荐使用SHAKE-128或SHAKE-256)就可以切换不同级别的安全性. 换句话说,一旦获得某个安全级别的更优化实现,就很容易获得其他安全级别的更优化的实现.
在介绍Dilithium签名方案之前,先描述其中需要使用的高低位比特分解算法[13]Decompos{e_q}(\theta ,\lambda ),该算法输入整数\theta \in {\mathbb{Z}_q}和一个小的正整数 \lambda ,满足\rho |(q - 1),按照3步操作将 \theta 分解得到 \theta = { \theta _{\rm{H}}} \cdot \lambda + { \theta _{\rm{L}}} ,其中0 \leqslant { \theta _{\rm{H}}} < \dfrac{{q - 1}}{ \lambda }且\Vert { \theta }_{{\rm{L}}}{\Vert }_{\infty }\le \dfrac{ \lambda }{2}. 并将{ \theta _{\rm{H}}} = HighBit{s_q} ( \theta , \lambda )称为 \theta 的高位比特,将{ \theta _{\rm{L}}} = LowBit{s_q}( \theta , \lambda )称为 \theta 的低位比特.
1) 将 \theta 取\,\bmod \,q落到区间0 \leqslant \theta < q中,得到 \theta : = \theta \,\bmod {\,^ + }q.
2) 将步骤1)得到的 \theta 取\,\bmod \lambda 落到区间- \dfrac{ \lambda }{2} < \theta \leqslant \dfrac{ \lambda }{2}(或- \dfrac{{ \lambda - 1}}{2} < r \leqslant \dfrac{{ \lambda - 1}}{2})中,得到{ \theta _{\rm{L}}}: = \theta \,\bmod {\,^ \pm } \lambda .
3) 如果 \theta - { \theta _{\rm{L}}} = q - 1则令{ \theta _{\rm{H}}}: = 0,{ \theta _{\rm{L}}}: = { \theta _{\rm{L}}} - 1,否则令{ \theta _{\rm{H}}}: = ( \theta - { \theta _{\rm{L}}})/ \lambda ,输出({ \theta _{\rm{H}}},{ \theta _{\rm{L}}}).
将Decompos{e_q}( \cdot )算法作用于多项式(例如环{R_q}中的元素)或由多项式组成的向量、矩阵时,表示对应操作被分别独立地作用到多项式的每个系数. 使用Decompos{e_q}( \cdot )算法,能对任意的由{R_q}中的多项式组成的向量{\boldsymbol{\varTheta}}和小范数向量{\boldsymbol{\varLambda}},在不保存 {\boldsymbol{\varTheta}} 的情况下恢复{\boldsymbol{\varTheta}} {\text{ + }} {\boldsymbol{\varLambda}}的高位比特,其正确性由引理1保证:
引理1[13]. {\boldsymbol{\varTheta}} , {\boldsymbol{\varLambda}}是由{R_q}中的多项式组成的向量, {\rho _1} 和 {\rho _2} 是正整数,如果\Vert {\boldsymbol{\varLambda}} {\Vert }_{\infty }\le {\rho }_{2}且\Vert LowBit{s}_{q}( {\boldsymbol{\varTheta}} ,{\rho }_{1}){\Vert }_{\infty } < \dfrac{{\rho }_{1}}{2}-{\rho }_{2},则等式HighBit{s_q}( {\boldsymbol{\varTheta}} ,{\rho _1}) \;=\; HighBit{s_q} ( {\boldsymbol{\varTheta}} + {\boldsymbol{\varLambda}} ,{\rho _1})成立.
Dilithium签名方案包括3个子算法:密钥生成算法、签名算法和验证算法,这里介绍不考虑压缩公钥{\boldsymbol{t}}的简化版本.
1)密钥生成算法. 首先使用种子生成矩阵{\boldsymbol{A}},然后均匀随机选取s{k_1}{\text{ = }}{{\boldsymbol{s}}_1}{ \leftarrow _\$ }S_\eta ^l,s{k_2}{\text{ = }}{{\boldsymbol{s}}_2}{ \leftarrow _\$ }S_\eta ^k并计算{\boldsymbol{t}} = {\boldsymbol{A}}{{\boldsymbol{s}}_1} + {{\boldsymbol{s}}_2},公钥pk = ({\boldsymbol{A}},{\boldsymbol{t}}),私钥sk = ({\boldsymbol{A}},{\boldsymbol{t}},{{\boldsymbol{s}}_1},{{\boldsymbol{s}}_2}).
2)签名算法. 对消息{{\mu}}进行签名时,首先均匀随机选取{\boldsymbol{y}}{ \leftarrow _\$ }S_{\gamma - 1}^l并计算{\boldsymbol{w}}: = {\boldsymbol{Ay}},使用Decompos{e_q}( \cdot )算法得到{\boldsymbol{w}}的高位比特{{\boldsymbol{w}}_{\rm{H}}}和低位比特{{\boldsymbol{w}}_{\rm{L}}}. 使用Hash函数{H_0}计算挑战值c \in \mathcal{C},从而得到{\boldsymbol{z}}: = {\boldsymbol{y}} + c{{\boldsymbol{s}}_1},在通过拒绝抽样后输出合法的签名\sigma = ({\boldsymbol{z}},c),其中\beta 满足\Vert c{{\boldsymbol{s}}}_{1}{\Vert }_{\infty }\le \beta ,\Vert c{{\boldsymbol{s}}}_{2}{\Vert }_{\infty }\le \beta.
算法1. Dilithium-签名算法.
输入:消息 \mu ,私钥sk = ({\boldsymbol{A}},{\boldsymbol{t}},{{\boldsymbol{s}}_1},{{\boldsymbol{s}}_2});
输出:签名\sigma = ({\boldsymbol{z}},c).
① 初始时设置{\boldsymbol{z}}: = \bot ;
② while {\boldsymbol{z}} = \bot do
③ {\boldsymbol{y}}{ \leftarrow _\$ }S_{\gamma - 1}^l;
④ {\boldsymbol{w}}: = {\boldsymbol{Ay}};
⑤ {{\boldsymbol{w}}_{\rm{H}}} = HighBit{s_q}({\boldsymbol{w}},2\gamma ' );
⑥ c: = {H_0}(\mu \left|\right|{{\boldsymbol{w}}_{\rm{H}}}) \in \mathcal{C};
⑦ {\boldsymbol{z}}: = {\boldsymbol{y}} + c{{\boldsymbol{s}}_1};
⑧ if \left\|{\boldsymbol{z}}\right\|_\infty \geqslant \gamma - \beta 或
\left\|LowBit{s_q}({\boldsymbol{Ay}} - c{{\boldsymbol{s}}_2},2\gamma' )\right\|_\infty \geqslant \gamma' - \beta then
⑨ {\boldsymbol{z}}: = \bot;
⑩ end if
⑪ end while
⑫ return \sigma = ({\boldsymbol{z}},c).
3)验证算法. 在得到 \mu 和\sigma = ({\boldsymbol{z}},c)后,首先利用Decompos{e_q}( \cdot )算法计算{\boldsymbol{Az}} - c{\boldsymbol{t}}的高位比特,然后根据{\boldsymbol{z}}的范围和挑战值c的正确性判断签名合法性.
算法2. Dilithium-验证算法.
输入:消息 \mu 以及对应的签名\sigma = ({\boldsymbol{z}},c),公钥pk = ({\boldsymbol{A}},{\boldsymbol{t}});
输出:1(接受签名)/ 0(拒绝签名).
① {\boldsymbol{w}}_{\rm{H}}' : = HighBit{s_q}({\boldsymbol{Az}} - c{\boldsymbol{t}},2\gamma');
② if \left\|{\boldsymbol{z}}\right\|_\infty < \gamma - \beta 且 c = {H_0}(\mu \left|\right|{\boldsymbol{w}}_{\rm{H}}' ) then
③ return 1;
④ else return 0;
⑤ end if
更详细的Dilithium签名方案的正确性以及安全性分析参见文献[13].
1.5 Aigis-sig数字签名方案
2020年1月,中国密码学会发布了全国密码算法设计竞赛的结果,Aigis-sig数字签名方案是公钥密码组获得一等奖的3个方案中唯一的签名方案,并且其对应的密钥封装方案Aigis-enc同样也获得了一等奖,在国内抗量子公钥密码设计中具有高度评价,经过进一步的改进后,将成为我国自主设计的重要抗量子密码方案.
Aigis-sig的主要设计思想与Dilithium类似,改进之处在于使用了更加灵活的非对称的格上困难问题——AMSIS问题和AMLWE问题,通过改变私钥{s_2}的选取范围以及拒绝抽样的条件,得到了更优的公钥尺寸或签名尺寸,以及更强的安全性. Aigis-sig签名方案包括3个子算法:密钥生成算法、签名算法和验证算法,这里介绍不考虑压缩公钥{\boldsymbol{t}}的简化版本.
1) 密钥生成算法. 首先使用种子生成矩阵{\boldsymbol{A}},然后均匀随机选取s{k_1} = {{\boldsymbol{s}}_1}{ \leftarrow _\$ }S_\eta ^l,s{k_2}= {{\boldsymbol{s}}_2}{ \leftarrow _\$ }S_{\eta ' }^k并计算{\boldsymbol{t}} = {\boldsymbol{A}}{{\boldsymbol{s}}_1} + {{\boldsymbol{s}}_2},公钥pk = ({\boldsymbol{A}},{\boldsymbol{t}}),私钥sk = ({\boldsymbol{A}},{\boldsymbol{t}},{{\boldsymbol{s}}_1},{{\boldsymbol{s}}_2}).
2) 签名算法. 对消息 \mu 进行签名,首先均匀随机选取{\boldsymbol{y}}{ \leftarrow _\$ }S_{\gamma - 1}^l并计算{\boldsymbol{w}}: = {\boldsymbol{Ay}},使用Decompos{e_q}( \cdot )算法得到{\boldsymbol{w}}的高位比特{{\boldsymbol{w}}_{{{\rm{H}}}}}和低位比特{{\boldsymbol{w}}_{{{\rm{L}}}}}. 使用Hash函数{H_0}计算挑战值c \in \mathcal{C},从而得到{\boldsymbol{z}}: = {\boldsymbol{y}} + c{{\boldsymbol{s}}_1}以及{\boldsymbol{u}}: = {\boldsymbol{w}} - c{{\boldsymbol{s}}_2},在通过拒绝抽样后输出合法的签名\sigma = ({\boldsymbol{z}},c),其中\beta 和\beta ' 满足\Vert c{{\boldsymbol{s}}}_{1}{\Vert }_{\infty }\le \beta ,\Vert c{{\boldsymbol{s}}}_{2}{\Vert }_{\infty }\le \beta '.
算法3. Aigis-sig-签名算法.
输入:消息 \mu ,私钥sk = ({\boldsymbol{A}},{\boldsymbol{t}},{{\boldsymbol{s}}_1},{{\boldsymbol{s}}_2});
输出:签名\sigma = ({\boldsymbol{z}},c).
① 初始时设置{\boldsymbol{z}}: = \bot;
② while {\boldsymbol{z}} = \bot do
③ {\boldsymbol{y}}{ \leftarrow _\$ }S_{\gamma - 1}^l;
④ {\boldsymbol{w}}: = {\boldsymbol{Ay}};
⑤ {{\boldsymbol{w}}_{{{\rm{H}}}}} = HighBit{s_q}({\boldsymbol{w}},2\gamma ' );
⑥ c: = {H_0}({{\mu}} \left|\right|{{\boldsymbol{w}}_{{{\rm{H}}}}}) \in \mathcal{C};
⑦ {\boldsymbol{z}}: = {\boldsymbol{y}} + c{{\boldsymbol{s}}_1}, {\boldsymbol{u}}: = {\boldsymbol{w}} - c{{\boldsymbol{s}}_2};
⑧ ({{\boldsymbol{u}}_{{{\rm{H}}}}},{{\boldsymbol{u}}_{{{\rm{L}}}}}) = Decompos{e_q}({\boldsymbol{u}},2\gamma ' );
⑨ if \left\|{\boldsymbol{z}}\right|_\infty \geqslant \gamma - \beta 或 \left\|{{\boldsymbol{u}}_{{{\rm{L}}}}}\right\|_\infty \geqslant \gamma ' - \beta ' 或
{{\boldsymbol{u}}_{{{\rm{H}}}}} \ne {{\boldsymbol{w}}_{{{\rm{H}}}}} then
⑩ {\boldsymbol{z}}: = \bot;
⑪ end if
⑫ end while
⑬ return \sigma = ({\boldsymbol{z}},c).
3) 验证算法. 在得到 \mu 和\sigma = ({\boldsymbol{z}},c)后,首先利用Decompos{e_q}( \cdot )算法计算{\boldsymbol{Az}} - c{\boldsymbol{t}}的高位比特,然后根据{\boldsymbol{z}}的范围和挑战值c的正确性判断签名合法性,这里的\beta (以及未显式表达的\beta ' )与算法2中的\beta 不同.
算法4. Aigis-sig-验证算法.
输入:消息 \mu 以及对应的签名\sigma = ({\boldsymbol{z}},c),公钥pk = ({\boldsymbol{A}},{\boldsymbol{t}});
输出:1(接受签名)/ 0(拒绝签名).
① {\boldsymbol{w}}_{{{\rm{H}}}}' = HighBit{s_q}({\boldsymbol{Az}} - c{\boldsymbol{t}},2\gamma ' );
② if \left\|{\boldsymbol{z}}\right|_\infty < \gamma - \beta 且 c = {H_0}(\mu \left|\right|{\boldsymbol{w}}_{{{\rm{H}}}}' ) then
③ return 1;
④ else return 0;
⑤ end if
更详细的Aigis-sig签名方案的正确性以及安全性分析参见文献[16, 43].
2. 两方协同签名方案
本文基于AMSIS/AMLWE困难问题提出的两方协同签名方案有2个.
1) 密钥生成算法. 和Dilithium算法一样,用户{P_i}(i = 1,2)在选取随机的矩阵{{\boldsymbol{A}}_i}时,可以直接使用256 b的种子.
① {P_1}随机选取{{\boldsymbol{A}}_1}{ \leftarrow _\$ }R_q^{k \times l}并计算得到Hash值{g_1} = {H_{\text{1}}}({{\boldsymbol{A}}_1}),将{g_1}发送给{P_2},{P_2}进行同样的操作,将{g_2} = {H_{\text{1}}}({{\boldsymbol{A}}_2})发送给{P_1}.
② {P_1}收到{P_2}发送的{g_2}后,将{{\boldsymbol{A}}_1}发送给{P_2},{P_2}进行同样的操作,将{{\boldsymbol{A}}_2}发送给{P_1}.
③ {P_1}收到{P_2}发送的{{\boldsymbol{A}}_2}后,验证{H_1}({{\boldsymbol{A}}_2}) = {g_2},若不成立则中止,否则计算公共矩阵\overline{{\boldsymbol{A}}}:=[{\boldsymbol{A}}\Vert {{\boldsymbol{I}}}_{k}]\in {R}_{q}^{k\times (l+k)},其中{\boldsymbol{A}} = {{\boldsymbol{A}}_1} + {{\boldsymbol{A}}_2}.
④ {P_1}随机选取s{k_{1,1}}{ \leftarrow _\$ }S_\eta ^l,s{k_{1,2}}{ \leftarrow _\$ }S_{\eta '}^k,并计算得到{{\boldsymbol{t}}_1} = \overline {\boldsymbol{A}} \cdot s{k_1} = {\boldsymbol{A}} \cdot s{k_{1,1}} + s{k_{1,2}} \in R_q^k以及Hash值g_1' = {H_{\text{2}}}({{\boldsymbol{t}}_1}),将g_1'发送给{P_2},{P_2}也进行同样的操作,将g_2' = {H_{\text{2}}}({{\boldsymbol{t}}_2})发送给{P_1}.
⑤ {P_1}收到{P_2}发送的g_2'后,将{{\boldsymbol{t}}_1}发送给{P_2},{P_2}也进行同样的操作,将{{\boldsymbol{t}}_2}发送给{P_1}.
⑥ {P_1}收到{P_2}发送的{{\boldsymbol{t}}_2}后,验证{H_2}({{\boldsymbol{t}}_2}) = g_2',若不成立则中止,否则计算{\boldsymbol{ t}} = {{\boldsymbol{t}}_1} + {{\boldsymbol{t}}_2}.
如果上述过程都没有中止,则可以得到{P_i}的私钥为s{k_i} = ({\boldsymbol{A}},{{\boldsymbol{t}}_i},s{k_{i,1}},s{k_{i,2}}),公钥为pk = ({\boldsymbol{A}},{\boldsymbol{t}}).
注:在交换{{\boldsymbol{A}}_i}({{\boldsymbol{t}}_i})之前先交换Hash值{g_i}(g_i' ),是为了防止恶意的{P_2}在收到诚实的{P_1}发送的{{\boldsymbol{A}}_1}({{\boldsymbol{t}}_1})后,再自适应地选择{{\boldsymbol{A}}_2}({{\boldsymbol{t}}_2}).
2) 签名算法. 我们以用户{P_1}的视角为例介绍两方协同签名协议,对消息\mu \in \mathcal{M}进行签名的具体过程如图1所示,运行协议后得到{{\boldsymbol{z}}_1}. 同样地,{P_2}也会得到{{\boldsymbol{z}}_2},将两者合起来即得到签名\sigma = ({\boldsymbol{z}},c,{\boldsymbol{h}}).
和Dilithium 一样,签名算法的第1步是计算身份协议所需要用到的挑战值c \in \mathcal{C} = {B_\tau }({B_\tau }的定义与文献[13,16]相同,表示环R中恰好有\tau 个系数为 \pm 1且其余系数为0的元素组成的集合),该值应该由双方一起生成,因而需要双方交换多个消息,但是并不能直接交换{{\boldsymbol{w}}_1}和{{\boldsymbol{w}}_2}(或其对应的高位比特),主要原因有2个方面:
① 如果{P_1}将{{\boldsymbol{w}}_1}发送给了{P_2},而之后未通过拒绝抽样,签名过程中止,({{\boldsymbol{w}}_1},{{\boldsymbol{z}}_1})可能会泄露关于私钥s{k_{1,1}}的信息. 之前的工作[26]的解决方法是利用非标准的格困难假设——Rejected MLWE假设,然而这只是一个启发式假设,可能存在安全性问题.
② 如果{P_2}知道了({{\boldsymbol{w}}_1},{{\boldsymbol{z}}_1}),可以从{{\boldsymbol{z}}_1}中提取得到c \cdot s{k_{1,2}}从而得到{P_1}的私钥的一部分s{k_{1,2}},{P_1}同理,这也可能会导致安全性上的威胁.
我们用同态承诺方案来解决这个问题. {P_1}和{P_2}均可以用公钥pk = ({\boldsymbol{A}},{\boldsymbol{t}})和消息\mu 计算得到消息对应的承诺密钥{\boldsymbol{ck}} \leftarrow {H_{{\boldsymbol{ck}}}}(\mu ,pk),先互相交换承诺值{\boldsymbol{co}}{{\boldsymbol{m}}_i} = Commi{t_{{\boldsymbol{ck}}}}({{\boldsymbol{w}}_{i,{\rm{H}}}};{{\boldsymbol{r}}_i}),由于使用的是同态承诺,因此可以将不同用户的承诺值聚合在一起,并用来在签名生成阶段计算挑战值. 同时和密钥生成算法一样,在互相交换承诺值{\boldsymbol{co}}{{\boldsymbol{m}}_i}之前需要先交换承诺值对应的Hash值{H_3}({\boldsymbol{co}}{{\boldsymbol{m}}_i}),如果缺少了这一步,恶意的{P_2}可以在看到{P_1}的承诺值{\boldsymbol{co}}{{\boldsymbol{m}}_1}自适应地选择{\boldsymbol{co}}{{\boldsymbol{m}}_2}'.
在第3轮通信中,双方交换({{\boldsymbol{z}}_i},{{\boldsymbol{r}}_i}). 并验证对方提供的{\boldsymbol{co}}{{\boldsymbol{m}}_i}是否确实是用同态承诺方案计算得到,验证通过后,计算得到完整的{\boldsymbol{z}} = {{\boldsymbol{z}}_1} + {{\boldsymbol{z}}_2}.
3) 验证算法. 收到消息 \mu 对应的签名\sigma = ({\boldsymbol{z}},c,{\boldsymbol{h}})以及用来计算承诺的{\boldsymbol{r}},作如下验证.
1) 验证\left\|{\boldsymbol{z}}\right\|_{\infty } < 2\gamma -2\beta.
2) 用公钥pk = ({\boldsymbol{A}},{\boldsymbol{t}})和消息 \mu 计算得到消息对应的承诺密钥{\boldsymbol{ck}} \leftarrow {H_{{\boldsymbol{ck}}}}(\mu ,pk).
3) 计算{\boldsymbol{w}}: = {\boldsymbol{Az}} - c{\boldsymbol{t}},从而得到高位比特{{\boldsymbol{w}}_{\rm{H}}}: = HighBit{s_q}({\boldsymbol{Az}} - c{\boldsymbol{t}},4\gamma ' )和{\widetilde {\boldsymbol{w}}_{\rm{H}}}: = {{\boldsymbol{w}}_{\rm{H}}} - {\boldsymbol{h}}\,\bmod \,\dfrac{{q - 1}}{{2\gamma ' }}.
4) 计算{\boldsymbol{com}}: = Commi{t_{{\boldsymbol{ck}}}}({\widetilde {\boldsymbol{w}}_{\rm{H}}};{\boldsymbol{r}}).
5) 验证c = {H_0}(\mu ,{\boldsymbol{com}}),若通过,返回1(即接受签名),否则返回0(即拒绝签名).
2.1 方案的正确性分析
证明本文提出方案的正确性,实际上就是证明3个结论:
1) \left\| {\boldsymbol{z}}\right\|_{\infty } < 2(\gamma -\beta )
由签名算法的定义有\left\|{{\boldsymbol{z}}}_{i}\right\|_{\infty }\le \gamma -\beta,因此有\left\| {\boldsymbol{z}}\right\|_{\infty }= \left\|{{\boldsymbol{z}}}_{1}+{{\boldsymbol{z}}}_{2}\right\|_{\infty }\le \left\| {{\boldsymbol{z}}}_{1}\right\|_{\infty }+\left\| {{\boldsymbol{z}}}_{2}\right\|_{\infty } < 2(\gamma -\beta ).
2) {{\boldsymbol{w}}_{\rm{H}}} = HighBit{s_q}({\boldsymbol{Az}} - c{\boldsymbol{t}},4\gamma ' )
由{\boldsymbol{A}}{{\boldsymbol{z}}_i} \;-\; c{{\boldsymbol{t}}_i} \;= \;{\boldsymbol{A}}({{\boldsymbol{y}}_i} + c \cdot s{k_{i,1}}) \;-\; c({\boldsymbol{A}} \cdot s{k_{i,1}} + s{k_{i,2}}) \;= {\boldsymbol{A}}{{\boldsymbol{y}}_i} - c \cdot s{k_{i,2}} 有 {\boldsymbol{Az}} - c{\boldsymbol{t}} = {\boldsymbol{A}}({{\boldsymbol{z}}_1} + {{\boldsymbol{z}}_2}) - c({{\boldsymbol{t}}_1} + {{\boldsymbol{t}}_2}) = {\boldsymbol{A}}{{\boldsymbol{y}}_1} + c \cdot s{k_{1,2}} + {\boldsymbol{A}}{{\boldsymbol{y}}_2} + c \cdot s{k_{2,2}} - c({\boldsymbol{A}} \cdot s{k_{1,1}} + s{k_{1,2}} + {\boldsymbol{A}} \cdot s{k_{2,1}} +s{k_{2,2}}) ={\boldsymbol{A}}{{\boldsymbol{y}}_1} + {\boldsymbol{A}}{{\boldsymbol{y}}_2} - (c \cdot s{k_{1,2}} + c \cdot s{k_{2,2}}). 又因为 \Vert c\cdot s{k}_{1,2}{\Vert }_{\infty } < \beta ' 以及 \Vert c\cdot s{k}_{2,2}{\Vert }_{\infty } < \beta ' 有 \Vert c\cdot s{k}_{1,2}+c\cdot s{k}_{2,2}{\Vert }_{\infty }\le \Vert c\cdot s{k}_{1,2}{\Vert }_{\infty }+ \Vert c\cdot s{k}_{2,2}{\Vert }_{\infty } < 2\beta '.
同时根据由签名算法的定义得到LowBit{s_q}\left({\boldsymbol{Az}} -\right. \left. c{\boldsymbol{t}},4\gamma ' \right) < 2\gamma ' - 2\beta ',由引理1有
\begin{aligned} &HighBit{s_q}({\boldsymbol{Az}} - c{\boldsymbol{t}},4\gamma ' ) =\\ & HighBit{s_q}({\boldsymbol{Ay}} - (c \cdot s{k_{1,2}} + c \cdot s{k_{2,2}}),4\gamma ' ) = \\ & HighBit{s_q}({\boldsymbol{Ay}},4\gamma ' ) = HighBit{s_q}({\boldsymbol{w}},4\gamma ' ) = {{\boldsymbol{w}}_{\rm{H}}}. \end{aligned} 3) Ope{n_{\boldsymbol{ck}}}({\boldsymbol{com}},{\widetilde {\boldsymbol{w}}_{\rm{H}}},{\boldsymbol{r}}) = 1
由于{\boldsymbol{com}}是在签名算法中通过成功运行“挑战值计算阶段”以及承诺方案的加法同态性质生成的,因此有
\begin{aligned} & {\boldsymbol{com}} = {\boldsymbol{co}}{{\boldsymbol{m}}_1} + {\boldsymbol{co}}{{\boldsymbol{m}}_2}= \\ & Commi{t_{{\boldsymbol{ck}}}}({{\boldsymbol{w}}_{1,{\rm{H}}}};{{\boldsymbol{r}}_1}) + Commi{t_{{\boldsymbol{ck}}}}({{\boldsymbol{w}}_{2,{\rm{H}}}};{{\boldsymbol{r}}_2})= \\ & Commi{t_{{\boldsymbol{ck}}}}({{\boldsymbol{w}}_{1,{\rm{H}}}} + {{\boldsymbol{w}}_{2,{\rm{H}}}};{{\boldsymbol{r}}_1} + {{\boldsymbol{r}}_2}) \end{aligned} 是{{\boldsymbol{w}}_{1,{\rm{H}}}} + {{\boldsymbol{w}}_{2,{\rm{H}}}}对应的一个承诺值,即为{\widetilde {\boldsymbol{w}}_{\rm{H}}}对应的一个承诺.
验证方计算得到{{\boldsymbol{w}}_{\rm{H}}} = HighBit{s_q}({\boldsymbol{Az}} - c{\boldsymbol{t}},4\gamma ' )和签名算法是相同的,再利用{\boldsymbol{h}} = {{\boldsymbol{w}}_{\rm{H}}} - {\widetilde {\boldsymbol{w}}_{\rm{H}}}进行“纠正”得到{\widetilde {\boldsymbol{w}}_{\rm{H}}},因此有Ope{n_{\boldsymbol{ck}}}({\boldsymbol{com}},{\widetilde {\boldsymbol{w}}_{\rm{H}}},{\boldsymbol{r}}) = 1.
2.2 方案的安全性分析
本节给出两方协同签名的安全性定义以及本文所提方案的安全性证明. 和文献[21]一样,我们沿用Lindell给出的两方协同签名的基于游戏的安全性定义[5],在该定义中,假设敌手只能调用一次密钥生成算法,而多个签名会话可以同时执行.
我们证明本文提出的两方协同签名方案具有分布式签名的选择消息攻击下的存在性不可伪造性(distributed signature with existential unforgeability under chosen message attack, DS-EU-CMA),需要用到如下的实验Ex{p^{{\rm{DS }}- {\rm{EU}} - {\rm{CMA}}}}(\mathcal{A}):
初始时定义签名消息集合\mathcal{M}为空集,敌手可以询问协同签名的谕言机{\mathcal{O}^{{\rm{DS}}}},得到若干个消息签名对({\mu _i},{\sigma _i}),并将{\mu _i}添加到\mathcal{M}中,最后敌手需要产生一个新的({\mu ^*},{\sigma ^*}),其中{\mu ^*}\not = {\mu _i}.
两方协同签名方案DS-EU-CMA安全意味着对于任意概率多项式时间的敌手\mathcal{A},成功伪造签名的优势Ad{v^{{\rm{DS - EU - CMA}}}}(\mathcal{A})是可忽略的,其中优势的定义为
Ad{v^{{\rm{DS - EU - CMA}}}}(\mathcal{A}): = Pr[Ex{p^{{\rm{DS - EU - CMA}}}}(\mathcal{A}) \to 1]. 我们的安全证明的主要思想与文献[21, 29]类似,我们证明了:如果敌手能以不可忽略的概率成功进行一个有效的伪造,则可以攻破承诺方案的计算绑定性或者AMLWE/AMSIS假设,即能以概率\varepsilon _{{\rm{Binding}}}攻破承诺方案的计算绑定性,或能以概率\varepsilon _{{\text{D-AMLWE}}_{q,k,l,\eta ,\eta ' }}解决参数为 (q,k,l,\eta ,\eta ' ) 的判定性AMLWE问题,或能以概率\varepsilon _{{\text{AMSIS}}_{q,k,l+1,\delta ,\delta ' }}解决参数为(q,k,l + 1,\delta ,\delta ' )的AMSIS问题,其中\varepsilon均表示不可忽略的概率值. 证明过程中需要用到文献[44]提出的分叉引理,在此先进行介绍.
引理2. 分叉引理(general forking lemma)[44]. 对于固定的询问次数Q \geqslant 1以及集合\mathcal{H}(\mathcal{H}中的元素个数|\mathcal{H}| \geqslant 2),令\mathcal{B}是一个随机化算法,满足{(i,{\sigma _{{\rm{out}}}}) \leftarrow } {\mathcal{B}}(x,{\textit{h}_1},{\textit{h}_2}, … ,{\textit{h}_Q}),其输入{\textit{h}_1}, {\textit{h}_2},… ,{\textit{h}_Q} \in \mathcal{H}, x是由一个随机化的输入值生成算法\mathcal{I}\mathcal{G}产生,输出i \in \{ 0, 1,… ,Q\}, {\sigma _{{\rm{out}}}} 是一个辅助输出.
{\mathcal{F}_\mathcal{B}}(x)是与\mathcal{B}相关联的分叉算法,定义为:
1) \mathcal{B}选取\rho 作为随机的硬币(coins),以随机化.
2) 随机选取{\textit{h}_1}, {\textit{h}_2}, … ,{\textit{h}_Q}{ \leftarrow _\$ }\mathcal{H}.
3) 运行算法\mathcal{B}:(i,{\sigma _{{\rm{out}}}}) \leftarrow \mathcal{B}(x,{\textit{h}_1},{\textit{h}_2},…,{\textit{h}_Q};\rho ).
4) 如果i = 0,则返回(0, \bot , \bot ),否则有1 \leqslant i \leqslant Q重新随机选取{\textit{h}}_i' ,{\textit{h}}_{i+1}', … ,{\textit{h}}_Q' { \leftarrow _\$ }\mathcal{H}.
5) (i' ,{\sigma _{{\rm{out}}}'} ) \leftarrow \mathcal{B}\left(x,{\textit{h}_1},\;{\textit{h}_2},\;…,\;{\textit{h}_{i - 1}},\;{\textit{h}_i'} ,\;{\textit{h}}_{i+1}',\;…,\right. \left.{\textit{h}_Q'} ;\rho \right) .
6) 如果i = i' 且{\textit{h}_i}\not = {\textit{h}' _i},返回(1,{\sigma _{{\rm{out}}}},{\sigma _{{\rm{out}}}'} ),否则返回(0, \bot , \bot ).
定义\mathcal{B}的接受概率acc和分叉概率frk.
\begin{aligned} acc: =& Pr[i\not = 0:x \leftarrow \mathcal{I}\mathcal{G},{\textit{h}_1},{\textit{h}_2}, … ,{\textit{h}_Q} \leftarrow \mathcal{H},(i,{\sigma _{{\rm{out}}}}) \leftarrow \\ &\mathcal{B}(x,{\textit{h}_1},{\textit{h}_2},…,{\textit{h}_Q})], \\&frk: = Pr[b = 1:x \leftarrow \mathcal{I}\mathcal{G},(b,{\sigma _{{\rm{out}}}},{\sigma _{{\rm{out}}}'} ) \leftarrow {\mathcal{F}_\mathcal{B}}(x)], \end{aligned} 则有frk \geqslant acc \cdot \left( {\dfrac{{acc}}{Q} - \dfrac{1}{{|\mathcal{H}|}}} \right),也可以表示为 acc \leqslant \dfrac{Q}{{|\mathcal{H}|}} + \sqrt {Q \cdot frk} .
在本方案中,定义\mathcal{I}\mathcal{G}的输出为({\boldsymbol{A}},{\boldsymbol{t}},{\boldsymbol{c}}{{\boldsymbol{k}}^*}).
定理1. 假设承诺方案具有计算隐藏性、计算绑定性、密钥均匀性、加法同态性和\xi -bits最小熵. 那么对于任意的可以询问1次密钥生成随机谕言机,{Q_{\rm{S}}}次签名谕言机和{Q_{\rm{H}}}次随机谕言机{H_0},{H_1},{H_2},{H_3},{H_{{\boldsymbol{ck}}}}的概率多项式时间敌手,该两方协同签名方案是DS-EU-CMA安全的,其安全性依赖于参数为(q,k,l,\eta ,\eta ' )的AMLWE假设以及参数为(q,k,l + 1,\delta ,\delta ' )的AMSIS假设.
证明. 对于一个能攻破该两方协同签名方案的敌手\mathcal{A},我们首先构造一个关于\mathcal{A}的模拟器\mathcal{S},能在不使用诚实用户的密钥的前提下模拟协议中诚实用户{P_n}的行为. \mathcal{S}用到了SimKeyGen( \cdot )及SimSign( \cdot )谕言机[21, 29]. 我们通过一系列的中间游戏{{Gam}}{{\text{e}}_i}来定义\mathcal{S},并比较了每一个游戏和前一个游戏的差别. 在得到\mathcal{S}后,我们利用\mathcal{S}构造了算法\mathcal{B},并通过调用分叉引理获得针对2个不同的挑战值的伪造签名,这使得我们能攻破承诺方案的计算绑定性或者AMLWE/AMSIS假设.
{{Gam}}{{{e}}_0}:分为随机谕言机模拟(random oracle simulation)、诚实用户谕言机模拟和伪造3个部分.
1) 随机谕言机模拟. 本方案中用到5个Hash函数{H_0},{H_1},{H_2},{H_3},{H_{{\boldsymbol{ck}}}},分别模拟:
① {H_1}:{\{ 0,1\} ^*} \to {\{ 0,1\} ^{{l_1}}}(用在密钥生成算法中的公钥矩阵生成). 构造空的Hash列表H{T_1},当向H{T_1}询问x'时,若列表中已经有H{T_1}(x')则返回H{T_1}(x'),否则从{\{ 0,1\} ^{{l_1}}}中均匀随机地选取一个值y'当作H{T_1}(x'),并将(x',y')填入H{T_1}.
② {H_2}:{\{ 0,1\} ^*} \to {\{ 0,1\} ^{{l_2}}}(用在密钥生成算法中的私钥和{\boldsymbol{t}}的生成). 构造空的Hash列表H{T_2},当向H{T_2}询问x'时,若列表中已经有H{T_2}(x')则返回H{T_2}(x'),否则从{\{ 0,1\} ^{{l_2}}}中均匀随机地选取一个值 y' 当作H{T_2}(x'),并将(x',y')填入H{T_2}.
③ {H_3}:{\{ 0,1\} ^*} \to {\{ 0,1\} ^{{l_3}}}(用在签名算法中的交换承诺值). 构造空的Hash列表H{T_3},当向H{T_3}询问x'时,若列表中已经有H{T_3}(x')则返回H{T_3}(x'),否则从{\{ 0,1\} ^{{l_3}}}中均匀随机地选取一个值y'当作H{T_3}(x'),并将(x',y')填入H{T_3}.
④ {H_0}:{\{ 0,1\} ^*} \to \mathcal{C}(用在签名算法中的计算挑战值). 构造空的Hash列表H{T_0},并令ctr = 0. 注意到{H_0}的输入为(\mu ,{\boldsymbol{com}}),因此需要先询问随机谕言机{H_3}(\mu ,pk),若列表中已经有H{T_0}(\mu ,{\boldsymbol{com}})则返回H{T_0}(\mu ,{\boldsymbol{com)}},否则设ctr = ctr + 1,并将{\textit{h}_{ctr}}当作H{T_0}(\mu ,{\boldsymbol{com}}),将\left(\mu ,{\boldsymbol{com}}, \right. \left.{\textit{h}_{ctr}}\right)填入H{T_0}. 其中,\{ {\textit{h}_1},{\textit{h}_2}, … ,{\textit{h}_{{Q_{\rm{S}}} + {Q_{\rm{H}}} + 1}}\}是\mathcal{S}收到的作为输入的随机挑战值.
⑤ {H_{{\boldsymbol{ck}}}}:{\{ 0,1\} ^*} \to {\mathcal{S}_{{\boldsymbol{ck}}}}(用在计算承诺密钥). 构造空的Hash列表{H_{{\boldsymbol{ck}}}},由于{H_{{\boldsymbol{ck}}}}的输入为(\mu ,pk),故向H{T_{{\boldsymbol{ck}}}}询问(\mu ,pk),若列表中已经有 H{T_{{\boldsymbol{ck}}}}(\mu ,pk) ,则返回H{T_{{\boldsymbol{ck}}}}(\mu ,pk),否则从承诺密钥空间{\mathcal{S}_{{\boldsymbol{ck}}}}中均匀随机地选取一个值{\boldsymbol{y}}当作H{T_{{\boldsymbol{ck}}}}(\mu ,pk),并将(\mu ,pk,{\boldsymbol{y}})填入H{T_{{\boldsymbol{ck}}}}.
搜索Hash列表算法SearchHash(HT,{\boldsymbol{h}}). 在构造Hash列表HT后,可以定义算法SearchHash(HT,{\boldsymbol{h}}): 对于{\boldsymbol{h}},在列表HT中寻找原像\widetilde m满足HT(\widetilde m) = {\boldsymbol{h}},如果不存在原像,则返回flag = {\rm{alert}}并设置m = \bot ,如果存在不止一个原像,则返回flag = {\rm{bad}}.
2) 诚实用户谕言机模拟(honest party oracle simulation). 在这个游戏中,敌手\mathcal{A}的行为和两方协同签名中的一个诚实用户相同. 与文献[21, 29]类似,当\mathcal{A}询问诚实用户谕言机时,\mathcal{S}可以直接按照密钥生成算法和签名算法的定义进行模拟,限于篇幅,在此处不展开,感兴趣的读者可以参见文献[21, 29].
3) 伪造(forgery). 敌手\mathcal{A}输出一个伪造的消息签名对\left( {{\mu ^*},{\sigma ^*} = \left( {{{\boldsymbol{z}}^*},{c^*},{{\boldsymbol{h}}^*}} \right)} \right). 对于给定的伪造,\mathcal{S}操作为:
如果{\mu ^*} \notin \mathcal{M},返回(0, \bot );并计算承诺密钥{\boldsymbol{c}}{{\boldsymbol{k}}^*} \leftarrow{H_{{\boldsymbol{ck}}}}\left( {{\mu ^*}}\right., \left.{pk} \right)和挑战值{c^*} \leftarrow {H_0}\left( {{\mu ^*},{\boldsymbol{co}}{{\boldsymbol{m}}^*}} \right)以及{\widetilde {\boldsymbol{w}}_{\rm{H}}} = HighBit{s_q}\left( {{\boldsymbol{A}}{{\boldsymbol{z}}^{\text{*}}} - }\right. \left.{{c^{\text{*}}}{\boldsymbol{t}},4\gamma ' } \right) - {{\boldsymbol{h}}^*}\,\bmod \,\dfrac{{q - 1}}{{4\gamma ' }}.
如果承诺的打开值Ope{n_{\boldsymbol{ck}}}({\boldsymbol{co}}{{\boldsymbol{m}}^*};{\widetilde {\boldsymbol{w}}_{\rm{H}}};{{\boldsymbol{r}}^*})\not = 1或者{\left\| {{{\boldsymbol{z}}^*}} \right\|_\infty } \geqslant 2(\gamma - \beta ),则返回(0, \bot );否则可以找到下标{i_{\rm{f}}} \in \{ 1,2, … ,{Q_{\rm{S}}} + {Q_{\rm{H}}} + 1\}使得{c^*} = {\textit{h}_{{i_{\rm{f}}}}},返回
\left( {i_{\rm{f}}},{\sigma _{{\rm{out}}}}\right) = ({{\boldsymbol{z}}^*},{c^*},{{\boldsymbol{h}}^*},{{\boldsymbol{r}}^*},{\boldsymbol{co}}{{\boldsymbol{m}}^*},{\mu ^*},{\boldsymbol{c}}{{\boldsymbol{k}}^*}) . 将\mathcal{S}在第i个游戏中不输出(0, \bot )的概率记作Pr[{{Gam}}{{{e}}_i}],有Pr[{{Gam}}{{{e}}_0}]: = Ad{v^{{\rm{DS - EU - CMA}}}}(\mathcal{A}).
{{Gam}}{{{e}}_1}: 相较于{{Gam}}{{{e}}_0},{{Gam}}{{{e}}_1}仅改变\mathcal{S}的签名过程,主要的变化在于挑战值c改为从集合\mathcal{C}中均匀随机选取,因此\mathcal{S}能在不与敌手\mathcal{A}交互的情况下计算出{{\boldsymbol{z}}_n}. 在收到挑战值{\textit{h}_i}后,\mathcal{S}运行搜索Hash列表算法SearchHash(H{T_3},{\textit{h}_i}),找到原像{\boldsymbol{co}}{{\boldsymbol{m}}_i}并计算{\boldsymbol{com}} = {\boldsymbol{co}}{{\boldsymbol{m}}_n} + {\boldsymbol{co}}{{\boldsymbol{m}}_i},最后,\mathcal{S}用c当作对随机谕言机{H_0}的询问(\mu ,{\boldsymbol{com}})的回答. 除了3种情况之外,{{Gam}}{{{e}}_1}和{Gam}{{{e}}_0}是等同的.
1) 在\mathcal{S}或\mathcal{A}对{H_3}的至多 {Q_{\rm{H}}} + 2{Q_{\rm{S}}}次询问中,产生了至少一次碰撞,发生的概率为\dfrac{{{{({Q_{\rm{H}}} + 2{Q_{\rm{S}}}+ 1)}^2}}}{{{2^{{l_3} + 1}}}}.
2) 在对{H_0}的 {{Q_{\rm{S}}}} 次询问中,至少失败了1次,分2种情况:
① {H_3}({\boldsymbol{co}}{{\boldsymbol{m}}_n})在\mathcal{A}对{H_3}的 {Q_{\rm{H}}} + 2{Q_{\rm{S}}}次询问中已经被询问过,这意味着\mathcal{A}已经猜到了Commi{t_{{\boldsymbol{ck}}}}的输出,发生概率为\dfrac{{{{Q_{\rm{S}}}} \cdot ({Q_{\rm{H}}} + 2{{Q_{\rm{S}}}})}}{{{2^\xi }}}.
② Hash列表H{T_0}中(\mu ,{\boldsymbol{com}})对应的Hash值已经被\mathcal{S}或\mathcal{A}在之前的对{H_0}的至多{Q_{\rm{H}}} + {{Q_{\rm{S}}}}次询问时设置过,发生概率为\dfrac{{{{Q_{\rm{S}}}} \cdot ({Q_{\rm{H}}} + {{Q_{\rm{S}}}})}}{{{2^\xi }}}.
3) \mathcal{A}在没有询问{H_3}时,就已经猜到了{H_3}的2个输出中的至少1个,发生概率为\dfrac{{{{2Q_{\rm{S}}}}}}{{{2^{{l_3}}}}}.
由此可得
\begin{aligned} &|Pr[{{Gam}}{{{e}}_1}] - Pr[{{Gam}}{{{e}}_0}]| \leqslant \frac{{{{({Q_{\rm{H}}} + 2{Q_{\rm{S}}}+ 1)}^2}}}{{{2^{{l_3} + 1}}}} + \\ &{{Q_{\rm{S}}}}\left( {\frac{{2{Q_{\rm{H}}} + 3{{Q_{\rm{S}}}}}}{{2\xi }} + \frac{2}{{{2^{{l_3}}}}}} \right).\end{aligned} {{Gam}}{{{e}}_2}: 相对于{{Gam}}{{{e}}_1},{{Gam}}{{{e}}_2}继续改变\mathcal{S}的签名过程,改变方式取决于\Vert {{\boldsymbol{z}}}_{1}{\Vert }_{\infty }的大小:如果\Vert {{\boldsymbol{z}}}_{1}{\Vert }_{\infty }\ge \gamma -\beta,则均匀随机地选取{{\boldsymbol{w}}_n}{ \leftarrow _\$ }R_q^k;否则令{{\boldsymbol{w}}_n} = {\boldsymbol{A}}{{\boldsymbol{y}}_n},其中{\boldsymbol{y}}{ \leftarrow _\$ }S_{\gamma - 1}^l.
和之前的游戏一样,\mathcal{S}将{{\boldsymbol{w}}_{n,{\rm{H}}}}进行承诺得到{\boldsymbol{co}}{{\boldsymbol{m}}_n} = Commi{t_{{\boldsymbol{ck}}}}({{\boldsymbol{w}}_{n,{\rm{H}}}},{{\boldsymbol{r}}_n}),其中{{\boldsymbol{r}}_n}{ \leftarrow _\$ }{\mathcal{S}_r},并将{H_3}({\boldsymbol{co}}{{\boldsymbol{m}}_n})发送给敌手\mathcal{A}.
{{Gam}}{{{e}}_2}和{Gam}{{{e}}_1}之间的区别是\mathcal{A}在进行{{Q_{\rm{S}}}}次询问后,区分一个模拟的承诺方案和一个真实的承诺方案的优势不同,即攻破承诺方案的隐藏性的优势不同. 因此有|Pr[{{Game}}_{2}]-Pr[{{Game}}_{1}]|\le {Q}_{{\rm{S}}}\cdot \varepsilon _{{\rm{Hiding}}}.
{{Gam}}{{{e}}_3}: 在这个游戏中,\mathcal{S}并不直接生成{{\boldsymbol{z}}_n},也不第一个拒绝抽样\Vert {{\boldsymbol{z}}}_{1}{\Vert }_{\infty } < \gamma -\beta. 相反,\mathcal{S}模拟拒绝抽样:以1 - \dfrac{{|S_{\gamma - \beta - 1}^k|}}{{|S_{\gamma - 1}^l|}}的概率随机选取{{\boldsymbol{w}}_n}{ \leftarrow _\$ }R_q^k. 以\dfrac{{|S_{\gamma - \beta - 1}^k|}}{{|S_{\gamma - 1}^l|}}的概率随机选取{{\boldsymbol{z}}_n}{ \leftarrow _\$ }S_{\gamma - \beta - 1}^l并定义{{\boldsymbol{w}}_n} = {\boldsymbol{A}}{{\boldsymbol{z}}_n} - c \cdot ({{\boldsymbol{t}}_n} - s{k_{n,2}}).
{{Gam}}{{{e}}_3}和{{Gam}}{{e}_2}之间的区别是\mathcal{A}区分一个随机选取的签名和一个真实的签名之间的优势,类似于文献[29],我们可以得到这2个{{Game}}中生成{{\boldsymbol{w}}_n}的方式是相同的,即有Pr[{{Gam}}{{{e}}_3}] = Pr[{{Gam}}{{{e}}_2}].
{Gam}{{{e}}_4}:在这个游戏中,我们的目的是完全移除签名过程中的私钥. 在没有拒绝抽样时(概率为\dfrac{{|S_{\gamma - \beta - 1}^k|}}{{|S_{\gamma - 1}^l|}}),{{\boldsymbol{w}}_n'} = {\boldsymbol{A}}{{\boldsymbol{z}}_n} - c{{\boldsymbol{t}}_n} 因 \Vert c\cdot s{k}_{n,2}\Vert < \beta 且\Vert LowBit{s}_{q} ({\boldsymbol{A}}{z}_{n}- c{{\boldsymbol{t}}}_{n},2\gamma ' ){\Vert }_{\infty } < \gamma ' -\beta,由引理1可知{{Gam}}{{{e}}_3}中的{\boldsymbol{A}}{{\boldsymbol{z}}_n} - c({{\boldsymbol{t}}_n} - s{k_{n,2}})和{{Gam}}{{{e}}_4}中的{\boldsymbol{A}}{{\boldsymbol{z}}_n} - c{{\boldsymbol{t}}_n}在模为2\gamma ' 时具有相同的高位比特,即{{Gam}}{{{e}}_4}中{{\boldsymbol{w}}_n}的高位比特和{{Gam}}{{{e}}_3}中{{\boldsymbol{w}}_n}的高位比特的分布相同,因此有Pr[{{Gam}}{{{e}}_4}] = Pr[{{Gam}}{{{e}}_3}].
接下来修改密钥产生过程:
{{Gam}}{{e}_5}:在这个游戏中,开始修改密钥产生过程. 模拟器\mathcal{S}拥有{\boldsymbol{ A}}{ \leftarrow _\$ }R_q^{k \times l}后,随机选取h{k_n}{ \leftarrow _\$ }{\{ 0,1\} ^{{l_1}}}并将其发送给敌手\mathcal{A},在收到h{k_i}后,\mathcal{S}运行SearchHash (H{T_1}, h{k_i})找到原像{{\boldsymbol{A}}_i}并计算{{\boldsymbol{A}}_n} = {\boldsymbol{A}} - {{\boldsymbol{A}}_i},以h{k_n}作为{H_1}({{\boldsymbol{A}}_n})的回答. {{Gam}}{{{e}}_5}和{{Gam}}{{{e}}_4}之间的公共矩阵{\boldsymbol{A}}并没有发生变化. 除了3种情况之外,{{Gam}}{e_5}和{{Gam}}{{{e}}_4}是等同的:
1) 在\mathcal{S}或\mathcal{A}对{H_1}的至多{Q_{\rm{H}}}次询问中,产生了至少1次碰撞,发生概率为\dfrac{{({Q_{\rm{H}}} + 1){Q_{\rm{H}}}}}{{{2^{{l_1} + 1}}}}.
2) \mathcal{S}以h{k_n}作为{H_1}({{\boldsymbol{A}}_n})的回答失败. 若在之前\mathcal{A}对随机谕言机{H_1}的 {Q_{\rm{H}}} 次询问中,{H_1}({{\boldsymbol{A}}_n})已经被\mathcal{A}询问过,则会出现这种情况,发生概率为\dfrac{{{Q_{\rm{H}}}}}{{{q^{d \cdot k \cdot l}}}}.
3) \mathcal{A}在没有询问{H_1}时,就已经猜到了{H_1}的2个输出中的至少1个,发生概率为\dfrac{{{{2Q_{\rm{S}}}}}}{{{2^{{l_1}}}}}. 由此可得
|Pr[{{Gam}}{{e}_5}] - Pr[{{Gam}}{{{e}}_4}]| \leqslant \dfrac{{({Q_{\rm{H}}} + 1){Q_{\rm{H}}}}}{{{2^{{l_1} + 1}}}} + \dfrac{{{Q_{\rm{H}}}}}{{{q^{d \cdot k \cdot l}}}} + \dfrac{2}{{{2^{{l_1}}}}}. {{Gam}}{{{e}}_6}: 在这个游戏中,继续修改密钥生成过程,\mathcal{S}产生{{\boldsymbol{t}}_n}{ \leftarrow _\$ }R_q^k来代替{{\boldsymbol{t}}_n} = {\boldsymbol{A}} \cdot s{k_{n,1}} + s{k_{n,2}},如果敌手\mathcal{A}可以区分{{Gam}}{{e}_5}和{{Gam}}{{{e}}_6},根据定义2,\mathcal{A}可以攻破参数为(q,k,l,\eta ,\eta ' )的Decisional-AMLWE问题,因此有|Pr[{{Game}}_{6}]-Pr[{Game}_{5}]|\le {\varepsilon }_{{\rm{D-AMLWE}}_{q,k,l,\eta ,\eta ' }}.
{{Gam}}{{{e}}_7}: 在这个游戏中,\mathcal{S}以公钥{\boldsymbol{t}} \in R_q^k作为输入,随机选取com{k_n}{ \leftarrow _\$ }{\{ 0,1\} ^{{l_2}}}并将其发送给\mathcal{A}. 在收到\mathcal{A}返回的com{k_i}后,\mathcal{S}运行SearchHash(H{T_2},com{k_i})找到原像{{\boldsymbol{t}}_i}并计算{{\boldsymbol{t}}_n} = {\boldsymbol{t}} - {{\boldsymbol{t}}_i}.
最后,\mathcal{S}以com{k_n}作为{H_2}({{\boldsymbol{t}}_n})的回答. {{Gam}}{{{e}}_7}和{Gam}{{{e}}_6}之间{\boldsymbol{t}}和{{\boldsymbol{t}}_n}并没有发生变化. 除了3种情况之外,{{Gam}}{{{e}}_7}和{Gam}{e_6}是等同的:
1) 在\mathcal{S}或\mathcal{A}对{H_2}的至多 {Q_{\rm{H}}} 次询问中,产生了至少1次碰撞,发生概率为\dfrac{{({Q_{\rm{H}}} + 1){Q_{\rm{H}}}}}{{{2^{{l_2} + 1}}}}.
2) \mathcal{S}以com{k_n}作为{H_2}({{\boldsymbol{t}}_n})的回答失败. 若在之前\mathcal{A}对随机谕言机{H_2}的 {Q_{\rm{H}}} 次询问中,{H_2}({{\boldsymbol{t}}_n})已经被\mathcal{A}询问过,则会出现这种情况,发生概率为\dfrac{{{Q_{\rm{H}}}}}{{{q^{d \cdot k}}}}.
3) \mathcal{A}在没有询问{H_2}之前,就已经猜到了{H_2}的2个输出中的至少1个,发生的概率为\dfrac{2}{{{2^{{l_2}}}}}. 由此可得
|Pr[{{Gam}}{{{e}}_7}] - Pr[{{Gam}}{{{e}}_6}]| \leqslant \frac{{({Q_{\rm{H}}} + 1){Q_{\rm{H}}}}}{{{2^{{l_2} + 1}}}} + \frac{{{Q_{\rm{H}}}}}{{{q^{d \cdot k}}}} + \frac{2}{{{2^{{l_2}}}}}. {{Gam}}{{{e}}_8}:在这个游戏中,将AMSIS问题实例嵌入到证明中,AMSIS实例具有形式[{\boldsymbol{A}}' ||{{\boldsymbol{I}}_k}],其中{\boldsymbol{A}}' { \leftarrow _\$ }R_q^{k \times (l + 1)}. {\text{Gam}}{{\text{e}}_7}中的公钥({\boldsymbol{A}},{\boldsymbol{t}})是从R_q^{k \times l} \times R_q^k中均匀随机选取的,因此令{\boldsymbol{A}}' = [{\boldsymbol{A}}||{\boldsymbol{t}}]并不影响公钥({\boldsymbol{A}},{\boldsymbol{t}})的分布.
接下来嵌入承诺密钥{\boldsymbol{c}}{{\boldsymbol{k}}^\# } \leftarrow {H_{{\boldsymbol{ck}}}}(\mu ,pk),和文献[21, 29]类似,由于该承诺方案具有密钥均匀性,因此可以直接从承诺密钥空间{\mathcal{S}_{{\boldsymbol{ck}}}}上均匀选取承诺密钥,这样模拟出的承诺密钥和诚实生成的承诺密钥是不可区分的. 假设给\mathcal{S}一个承诺密钥{\boldsymbol{c}}{{\boldsymbol{k}}^\# }作为输入,我们希望\mathcal{S}对除了一个询问之外的所有询问全部返回的是模拟的承诺密钥. 在使用询问进行伪造签名时,\mathcal{S}应该使用一个预先定义好的承诺密钥{\boldsymbol{c}}{{\boldsymbol{k}}^\# },只需要调整模拟谕言机{H_{{\boldsymbol{ck}}}}的方式:当收到对{H_{{\boldsymbol{ck}}}}的询问时,以\omega 的概率均匀随机选取 H{T_{{\boldsymbol{ck}}}}(\mu ,pk){ \leftarrow _\$ }{\mathcal{S}_{{\boldsymbol{ck}}}} ,以1 - \omega 的概率选取H{T_{{\boldsymbol{ck}}}}(\mu ,pk) = {\boldsymbol{c}}{{\boldsymbol{k}}^\# }.
如果模拟成功(即\mathcal{S}不返回(0, \bot ), 则有{\boldsymbol{c}}{{\boldsymbol{k}}^\# } = {\boldsymbol{ck }}= {H_{{\boldsymbol{ck}}}}({\mu ^*},pk). 考虑到所做的修改,我们需要调整\mathcal{S}不返回(0, \bot )的概率,即有
Pr[{{Gam}}{{{e}}_8}] \geqslant {\omega ^{{Q_{\rm{H}}} + {{Q_{\rm{S}}}}}} \cdot (1 - \omega ) \cdot Pr [{{Gam}}{{{e}}_7}]. 综上,我们依赖模拟器\mathcal{S}构造了一个算法\mathcal{B}能攻破使用承诺密钥{\boldsymbol{c}}{{\boldsymbol{k}}^\# }的承诺方案的绑定性,或者找到一个输入为{\boldsymbol{A}}' = [{\boldsymbol{A}}||{\boldsymbol{t}}]的AMSIS问题的解. 由于算法\mathcal{B}输入({\boldsymbol{A}},{\boldsymbol{t}},{\boldsymbol{c}}{{\boldsymbol{k}}^\# })并调用分叉引理中的分叉算法\mathcal{F},可以以frk的概率得到2个伪造的输出{{\boldsymbol{\sigma}} _{\rm{{out}}}} =( {{\boldsymbol{z}}^*},{{{c}}^*},{{\boldsymbol{h}}^*}, {{\boldsymbol{r}}^*},{\boldsymbol{co}}{{\boldsymbol{m}}^*},{\mu ^*},{\boldsymbol{c}}{{\boldsymbol{k}}^*} ) 和{{\boldsymbol{\sigma}} _{{\rm{out}}}'} = \left( {{\boldsymbol{z}}' ,c' ,{\boldsymbol{h}}' ,{\boldsymbol{r}}' ,{\boldsymbol{com}}' ,\mu ' ,{\boldsymbol{ck}}' } \right),由分叉引理有
Pr\left[ {{{Gam}}{{{e}}_8}} \right] = acc \leqslant \dfrac{{{Q_{\rm{H}}} + {{Q_{\rm{S}}}} + 1}}{{|C|}} + \sqrt {\left( {{Q_{\rm{H}}} + {{Q_{\rm{S}}}} + 1} \right) \cdot frk}. 根据分叉算法的定义,所有分叉前产生的值都是相同的,即有{\boldsymbol{co}}{{\boldsymbol{m}}^*} = {\boldsymbol{com}}' ,{\mu ^*} = \mu '以及{\boldsymbol{c}}{{\boldsymbol{k}}^*} = {\boldsymbol{ck}}' = {\boldsymbol{c}}{{\boldsymbol{k}}^\# },且满足{c^*}\not = c' . 因此有
Ope{n_{{\boldsymbol{ck}}^*}}\left( {{\boldsymbol{co}}{{\boldsymbol{m}}^*},{{\widetilde {\boldsymbol{w}}}_{\rm{H}}}^*,{{\boldsymbol{r}}^*}} \right) = Ope{n_{{\boldsymbol{ck}}}^*}\left( {{\boldsymbol{co}}{{\boldsymbol{m}}^*},{{\widetilde {\boldsymbol{w}}}_{\rm{H}}}' ,{\boldsymbol{r}}' } \right) = 1.
其中
\begin{gathered} {\widetilde {\boldsymbol{w}}_{\rm{H}}}^* = HighBit{s_q}\left( {{\boldsymbol{A}}{{\boldsymbol{z}}^{\text{*}}} - {c^{\text{*}}}{\boldsymbol{t}},4\gamma ' } \right) - {{\boldsymbol{h}}^*}\,\bmod \,\dfrac{{q - 1}}{{4\gamma ' }}, \\ {\widetilde {\boldsymbol{w}}_{\rm{H}}}' = HighBit{s_q}\left( {{\boldsymbol{Az}}' - c' {\boldsymbol{t}},4\gamma ' } \right) - {\boldsymbol{h}}' \,\bmod \,\dfrac{{q - 1}}{{4\gamma ' }}. \\ \end{gathered} 按照{\widetilde {\boldsymbol{w}}_{\rm{H}}}^*和{\widetilde {\boldsymbol{w}}_{\rm{H}}}'是否相等2种情况分类讨论:
情形1.{\widetilde {\boldsymbol{w}}_{\rm{H}}}^*\not = {\widetilde {\boldsymbol{w}}_{\rm{H}}}',此时\mathcal{A}已经找到了承诺{\boldsymbol{co}}{{\boldsymbol{m}}^*}的同一个承诺密钥{\boldsymbol{c}}{{\boldsymbol{k}}^*}对应的2个有效的打开,这意味着\mathcal{A}已经攻破了承诺方案的绑定性,发生的概率为{\varepsilon}_{{\rm{Binding}}}.
情形2.{\widetilde {\boldsymbol{w}}_{\rm{H}}}^* = {\widetilde {\boldsymbol{w}}_{\rm{H}}}',此时有HighBit{s_q}\left( {{\boldsymbol{A}}{{\boldsymbol{z}}^{\text{*}}} - {c^{*}}{\boldsymbol{t}},4\gamma ' } \right) - {{\boldsymbol{h}}^*} = HighBit{s_q}\left( {{\boldsymbol{Az}}' - c' {\boldsymbol{t}},4\gamma ' } \right) - {\boldsymbol{h}}',将该式的两边同时乘以4\gamma ' 并结合 HighBit{s_q}( \cdot ) 和 LowBit{s_q}( \cdot ) 的定义有
\begin{gathered} ({\boldsymbol{A}}{{\boldsymbol{z}}^{\text{*}}} - {c^{\text{*}}}{\boldsymbol{t}}) - LowBit{s_q}\left( {{\boldsymbol{A}}{{\boldsymbol{z}}^{\text{*}}} - {c^{\text{*}}}{\boldsymbol{t}},4\gamma ' } \right) - 4\gamma ' \cdot {{\boldsymbol{h}}^*} = \\ ({\boldsymbol{Az}}' - c' {\boldsymbol{t}}) - LowBit{s_q}\left( {{\boldsymbol{Az}}' - c' {\boldsymbol{t}},4\gamma ' } \right) - 4\gamma ' \cdot {\boldsymbol{h}}' , \end{gathered} 将{{\boldsymbol{x}}^*} = LowBit{s_q}\left( {{\boldsymbol{A}}{{\boldsymbol{z}}^{*}} - {c^{*}}{\boldsymbol{t}},4\gamma ' } \right) + 4\gamma ' \cdot {{\boldsymbol{h}}^*} 和{\boldsymbol{x}}' = LowBit{s_q}\left( {{\boldsymbol{A}}{\boldsymbol{z}}' - c' {\boldsymbol{t}},4\gamma ' } \right) + 4\gamma ' \cdot {\boldsymbol{h}}'代入,可得
{\boldsymbol{A}}{{\boldsymbol{z}}^{*}} - {c^{*}}{\boldsymbol{t}} - {{\boldsymbol{x}}^*} = {\boldsymbol{Az}}' - c' {\boldsymbol{t}} - {\boldsymbol{x}}',即
[{\boldsymbol{A}}||{\boldsymbol{t}}||{\boldsymbol{I}}] \cdot \left[ {\begin{array}{*{20}{c}} {{{\boldsymbol{z}}^*} - {\boldsymbol{z}}' } \\ {c' - {c^*}} \\ {{\boldsymbol{x}}' - {{\boldsymbol{x}}^*}} \end{array}} \right] = { {0}}. 由于伪造的签名是有效的,有\Vert LowBit{s}_{q}({\boldsymbol{A}}{{\boldsymbol{z}}}^{*}- {c}^{*}{\boldsymbol{t}},4\gamma ' ){\Vert }_{\infty } < 2(\gamma ' -\beta ' )以及\Vert LowBit{s}_{q}({\boldsymbol{Az}}' -c' {\boldsymbol{t}}, 4\gamma ' ){\Vert }_{\infty } < 2(\gamma ' -\beta ' ),同时由于{{\boldsymbol{h}}^*},{\boldsymbol{h}}' \in {\{ - 1,0,1\} ^k},因此有
\Vert {{\boldsymbol{x}}}^{*}{\Vert }_{\infty } \le \Vert LowBit{s}_{q}\left({\boldsymbol{A}}{{\boldsymbol{z}}}^{\text{*}} - {c}^{\text{*}}{\boldsymbol{t}},4\gamma ' \right){\Vert }_{\infty } + 4\gamma ' \Vert {{\boldsymbol{h}}}^{*}{\Vert }_{\infty }\le 6\gamma ' -2\beta '. 同理有\Vert {\boldsymbol{x}}' {\Vert }_{\infty }\le 6\gamma ' -2\beta ',可以得到
\Vert {\boldsymbol{x}}' -{{\boldsymbol{x}}}^{*}{\Vert }_{\infty }\le 12\gamma ' -4\beta ' . 又由于\Vert {{\boldsymbol{z}}}^{*}{\Vert }_{\infty } < 2(\gamma -\beta )以及\Vert {\boldsymbol{z}}' {\Vert }_{\infty } < 2(\gamma -\beta ),有
\Vert {{\boldsymbol{z}}}^{*}-{\boldsymbol{z}}' {\Vert }_{\infty } < 4(\gamma -\beta ) . 故\mathcal{A}找到了参数为(q,k,l + 1,\delta ,\delta ' )的AMSIS问题的解,其中\delta 取决于\Vert {{\boldsymbol{z}}}^{*}-{\boldsymbol{z}}' {\Vert }_{\infty } < 4(\gamma -\beta ),\delta ' 取决于\Vert {\boldsymbol{x}}' -{{\boldsymbol{x}}}^{*}{\Vert }_{\infty }\le 12\gamma ' -4\beta ',发生的概率为{\varepsilon }_{\text{AMSIS}(q,k,l+1,\delta ,\delta ' )}. 由分叉引理可知
frk\le {\varepsilon }_{{\rm{Binding}}}+{\varepsilon}_{\text{AMSIS}(q,k,l+1,\delta ,\delta ' )}. 综上,我们得到敌手成功伪造签名的概率优势为
\begin{aligned} &Ad{v}^{{\rm{DS}}-{\rm{EU}}-{\rm{CMA}}}(\mathcal{A})=Pr[{{Game}}_{0}]\le\\ &|Pr[{{Game}}_{8}]|+{\displaystyle \sum _{i=0}^{8}|}Pr[{{Game}}_{i+1}]-Pr[{{Game}}_{i}]|\le\\ &\frac{{\left({Q}_{{\rm{H}}}+2{Q}_{{\rm{S}}}+1\right)}^{2}}{{2}^{{l}_{3}+1}}+{Q}_{{\rm{S}}}\left(\frac{2{Q}_{{\rm{H}}}+3{Q}_{{\rm{S}}}}{{2}^{\xi }}+\frac{2}{{2}^{{l}_{3}}}\right)+{Q}_{{\rm{S}}}\cdot {\varepsilon }_{{\rm{Hiding}}}+\\ &\frac{\left({Q}_{{\rm{H}}}+1\right){Q}_{{\rm{H}}}}{{2}^{{l}_{1}+1}}+\frac{{Q}_{{\rm{H}}}}{{q}^{d\cdot k\cdot l}}+\frac{2}{{2}^{{l}_{1}}}+{\varepsilon }_{{\text{D-AMLWE}}_{q,k,l,\eta ,\eta ' }}+\frac{\left({Q}_{{\rm{H}}}+1\right){Q}_{{\rm{H}}}}{{2}^{{l}_{2}+1}} +\\ &\frac{{Q}_{{\rm{H}}}}{{q}^{d\cdot k}}+\frac{2}{{2}^{{l}_{2}}}+\frac{1}{{\omega }^{{Q}_{{\rm{H}}}+{Q}_{{\rm{S}}}}(1-\omega )}\cdot \frac{{Q}_{{\rm{H}}}+{Q}_{{\rm{S}}}+1}{\left|C\right|} +\\ &\frac{\sqrt{({Q}_{{\rm{H}}}+{Q}_{{\rm{S}}}+1)\cdot ({\varepsilon }_{{\rm{Binding}}}+{\varepsilon }_{{\text{AMSIS}}_{q,k,l+1,\delta ,\delta ' }})}}{{\omega }^{{Q}_{{\rm{H}}}+{Q}_{{\rm{S}}}}(1-\omega )}.\end{aligned} 因此,若敌手以不可忽略的概率成功伪造签名,则能以不可忽略的概率攻破承诺方案的计算绑定性或AMLWE/AMSIS假设.证毕.
3. 性能分析与比较
为密码方案选择合适的参数需要在多个方面权衡,本方案参数的选择应该在保证足够安全性的前提下,使得期望重复次数(影响通信轮数和签名时间)较小且拥有较短的签名和密钥尺寸,因此我们主要考虑这3项指标,并以此评价方案的性能.
3.1 重复次数的期望值(通信重复轮数)
签名生成算法用到了拒绝抽样技术,以得到 \Vert {{\boldsymbol{z}}}_{i}{\Vert }_{\infty }\le \gamma -\beta -1 ,\Vert LowBit{s}_{q}({{\boldsymbol{w}}}_{i}-c\cdot s{k}_{i,2},2\gamma ' ){\Vert }_{\infty }\le \gamma ' - \beta - 1以及\Vert LowBit{s}_{q}({\boldsymbol{Az}}-c{\boldsymbol{t}},4\gamma ' ){\Vert }_{\infty }\le 2\gamma ' -2\beta -1,需要考虑重复的轮数,主要由1)~ 3)决定:
1) \Vert {{\boldsymbol{z}}}_{i}{\Vert }_{\infty }\le \gamma -\beta -1
如果 \Vert c\cdot s{k}_{i,1}\Vert \le \beta 成立,那么当\Vert {{\boldsymbol{y}}}_{i}{\Vert }_{\infty }\le \gamma -2\beta -1时,总有\Vert {{\boldsymbol{z}}}_{i}{\Vert }_{\infty }=\Vert {{\boldsymbol{y}}}_{i}+c\cdot s{k}_{i,1}{\Vert }_{\infty }\le \gamma -\beta -1,该范围的大小为2(\gamma - \beta ) - 1. 由于{{\boldsymbol{y}}_i}{ \leftarrow _\$ }S_{\gamma - 1}^l中的每个多项式系数都是从\left\{- (\gamma - 1),…,(\gamma - 1)\right\}中均匀随机选取(即对于固定的c \cdot s{k_{i,1}},{{\boldsymbol{z}}_i}共有2\gamma - 1种可能值), 因此\Vert {{\boldsymbol{z}}}_{i}{\Vert }_{\infty }\le \gamma -\beta -1的概率为
{\left( {\frac{{2\left( {\gamma - \beta } \right) - 1}}{{2\gamma - 1}}} \right)^{n \cdot l}} = {\left( {1 - \frac{\beta }{{\gamma - 1/2}}} \right)^{n \cdot l}} \approx {{\rm{e}}^{ - nl\beta /\gamma }}, 其中“ \approx ”利用了 \gamma \gg \dfrac{1}{2}的事实.
2) \Vert LowBit{s}_{q}({{\boldsymbol{w}}}_{i}-c\cdot s{k}_{i,2},2\gamma ' ){\Vert }_{\infty }\le \gamma ' -\beta ' -1
计算\Vert LowBit{s}_{q}({{\boldsymbol{w}}}_{i}-c\cdot s{k}_{i,2},2\gamma ' ){\Vert }_{\infty }\le \gamma ' -\beta ' -1成立的概率,由于其中的多项式的每个系数都在模 2\gamma ' 的剩余系中均匀分布,因此
\Vert LowBit{s}_{q}({{\boldsymbol{w}}}_{i}-c\cdot s{k}_{i,2},2\gamma ' ){\Vert }_{\infty }\le \gamma ' -\beta ' -1 成立的概率为
{\left( {\frac{{2\left( {\gamma ' - \beta ' } \right) - 1}}{{2\gamma ' }}} \right)^{n \cdot k}} = {\left( {1 - \frac{{\beta ' + 1/2}}{{\gamma ' }}} \right)^{n \cdot k}} \approx {{\rm{e}}^{ - nk\beta ' /\gamma ' }}, 其中“ \approx ”利用了 \gamma \gg \dfrac{1}{2} 的事实.
3) \Vert LowBit{s}_{q}({\boldsymbol{Az}}-c{\boldsymbol{t}},4\gamma ' ){\Vert }_{\infty }\le 2\gamma ' -2\beta ' -1
不难验证满足2),则3)一定成立. 换句话说,对于满足2)的{{\boldsymbol{w}}_1} - c \cdot s{k_{1,2}}和{{\boldsymbol{w}}_2} - c \cdot s{k_{2,2}},一定有
\Vert LowBit{s}_{q}({\boldsymbol{Az}}-c{\boldsymbol{t}},4\gamma ' ){\Vert }_{\infty }\le 2(\gamma ' -\beta ' ) 成立,结合\Vert c{\boldsymbol{t}}{\Vert }_{\infty }\le 2\beta '及引理1可知不会泄露信息.
对于2个用户P_i,i = 1,2,当\Vert {{\boldsymbol{z}}}_{i}{\Vert }_{\infty }\le \gamma -\beta -1且\Vert LowBit{s}_{q}({{\boldsymbol{w}}}_{i}-c\cdot s{k}_{i,2},2\gamma ' ){\Vert }_{\infty }时得到合法的签名,其概率为
Pr[{\rm{success}}] = {({{\rm{e}}^{ - nl\beta /\gamma }} \cdot {{\rm{e}}^{ - nk\beta ' /\gamma ' }})^2} = {{\rm{e}}^{ - 2n(l\beta /\gamma + k\beta ' /\gamma ' )}}. 因此重复次数的期望值可以估计为
E = 1/Pr[{\rm{success}}] = {{\rm{e}}^{2n(l\beta /\gamma + k\beta ' /\gamma ' )}}. 3.2 密钥和签名大小
{P_i}的私钥为s{k_i} = ({\boldsymbol{A}},{{\boldsymbol{t}}_i},s{k_{i,1}},s{k_{i,2}}),公钥为pk = ({\boldsymbol{A}},{\boldsymbol{t}}),其中{\boldsymbol{A}} \in R_q^{k \times l},{\boldsymbol{t}} \in R_q^k.
1) 计算公钥大小. {\boldsymbol{A}} = \displaystyle\sum\limits_{i=1}^{2} {{{\boldsymbol{A}}_i}} = {{\boldsymbol{A}}_1} + {{\boldsymbol{A}}_2},类似于Dilithium签名方案以及Aigis-sig签名方案,用户{P_i}(i = 1,2)的{{\boldsymbol{A}}_i}可以由256 b的种子生成,因此只需要保存种子,共512b,公钥(单位B)共需要约
\frac{512+n\cdot k\cdot \lceil{{\rm{lb}}q}\rceil}{8}. 2) 计算私钥大小. {P_i}的私钥s{k_i} = ({\boldsymbol{A}},{{\boldsymbol{t}}_i},s{k_{i,1}},s{k_{i,2}}), 其中s{k_{i,1}}{ \leftarrow _\$ }S_\eta ^l,s{k_{i,2}}{ \leftarrow _\$ }S_{\eta ' }^k, 私钥(单位B)共需要约
\begin{aligned} &\frac{512}{8}+\frac{n \cdot k \cdot\lceil {\rm{ lb}} q \rceil}{8}+\frac{n \cdot 1 \cdot(\lceil{ {\rm{lb}}} \eta \rceil+1)}{8}+\\ &\frac{n \cdot k \cdot\left(\lceil{ {\rm{lb}}} \eta{'} \rceil +1\right)}{8} .\end{aligned} 这里和文献[24]一样,由于s{k_{i,1}}和s{k_{i,2}}的每个系数都可能是负的元素,因此需要额外1b来表示符号.
3) 计算签名大小. 签名由({\boldsymbol{z}},c,{\boldsymbol{h}})共3个部分组成:
{\boldsymbol{z}}是一个l维向量,且满足\Vert {\boldsymbol{z}}{\Vert }_{\infty }\le 2(\gamma -\beta )-1,因此{\boldsymbol{z}}的大小约为n\cdot l\cdot (\left\lceil {{{{\rm{lb}}}}((\gamma -\beta )-1 )} \right\rceil+1).
c是挑战值,和文献[13, 16, 22]选取自相同的挑战值集合,因此c的大小为 \tau \cdot(\left\lceil {{\rm{ lb}} n} \right\rceil +1) .
\begin{aligned} & {\boldsymbol{h}} = {{\boldsymbol{w}}_{\rm{H}}} - {\widetilde {\boldsymbol{w}}_{\rm{H}}} = HighBit{s_q}({\boldsymbol{Az}} - c{\boldsymbol{t}},4\gamma ' ) -\\ &\left({{\boldsymbol{w}}_{1,{\rm{H}}}} + {{\boldsymbol{w}}_{2,{\rm{H}}}}\bmod \,\frac{{q - 1}}{{2\gamma ' }}\right), \end{aligned} {\boldsymbol{h}} 是一个k维向量且\Vert {\boldsymbol{h}}{\Vert }_{\infty }\le \dfrac{q-1}{4\gamma ' },{\boldsymbol{h}} 的大小为n \cdot k \cdot \left(\left\lceil{\rm{ lb}} \left(\dfrac{q-1}{4 \gamma{'}}\right)\right\rceil+1\right).
综上,签名(单位B)共需要约
\begin{aligned} &\frac{n \cdot l \cdot(\left\lceil{ {\rm{lb}}(2(\gamma-\beta)-1)}\right\rceil+1)}{8}+\frac{\tau (\left\lceil { {\rm{lb}} n}\right\rceil+1)}{8}+\\ &\frac{n\cdot k \cdot \left(\left\lceil { {\rm{lb}} \left(\dfrac{q-1}{4\gamma' }\right)}\right\rceil+1\right)}{8} .\end{aligned} 特别地,当\eta ' = \eta ,\beta ' = \beta 时,本文的方案与Dilizium 2.0两方协同签名方案本质上等价,也就是说Dilizium 2.0可以视为本文方案的一个特例.
我们选取Dilithium第2轮的参数[13]以及Aigis相对应的参数[16]进行实例化,参数如表1所示,得到的密钥大小和签名大小的对比见表2,签名成功所需重复次数的对比见表3.
表 2 密钥大小及签名大小的比较Table 2. Comparison in Key Sizes and Signature Sizes表 3 期望重复次数比较Table 3. Comparison in Expect Repeations方案 期望重复次数 方案 期望重复次数 Aitps-1024 (本文) e3.534=34.3 Aigis-sig-1024[16] 5.86 Dilizium 2.0-1024[29] e3.495=33.0 Dilithium-1024[13] 5.90 Aitps-1280 (本文) e4.0575=57.8 Aigis-sig-1280[16] 7.61 Dilizium 2.0-1280[29] e3.763=43.1 Dilithium-1280[13] 6.60 Aitps-1536 (本文) e3.791=44.3 Aigis-sig-1536[16] 6.67 Dilizium 2.0-1536[29] e2.908=18.3 Dilithium-1536[13] 4.30 由表2可知,我们提出的两方协同签名方案比文献[24, 29]拥有更短的密钥和签名. 而在决定运行时间的期望重复次数方面,虽然大于文献[29]的方案,但由文献[16]和表3可知,即使重复次数略大,在进行工程上的优化以及使用AVX2进行加速后,Aigis-sig甚至在一些参数下快于Dilithium(具体运行时间对比参见文献[16]),因此我们合理地认为实际情况下Aitps(本文提出的基于Aigis-sig的两方协同签名方案)与Dilizium 2.0(现有最优的基于Dilithium的两方协同签名方案)效率相当.
4. 总结及展望
本文提出的Aitps是一种基于格的两方协同签名协议,允许2个用户在不泄露各自私钥的情况下通过交互对给定的消息进行签名,同时任何一方都无法重构密钥和独自完成整个签名过程,保证了密钥的安全性. 在协议的安全性方面,我们将其归约到非对称模格困难问题以及用到的承诺方案的计算隐藏性(本质上也是基于模格问题的困难性). 由于现有的最优的相关方案Dilizium 2.0没有评估效果,我们也给出了Aitps方案各项评价指标的计算公式(也适用于Dilizium 2.0方案),并采用CRYSTALS-Dilithium和Aigis-sig的推荐参数进行实例化,相比之下,本文提出的方案比现有的所有基于Dilithium的两方签名方案具有更小的密钥和签名尺寸,特别是签名尺寸,能减少至少20%.
与文献[21]一样,本文提出的两方协同签名方案很容易扩展成为安全的多方协同签名方案. 在未来的工作中,我们将进一步考虑使用提交给NIST的CRYSTALS-Dilithium签名方案中对公钥的压缩技巧继续减小公钥尺寸,以及尝试降低期望重复次数.
作者贡献声明:文嘉明提出算法设计思路并撰写论文;王后珍提出算法优化及分析思路,并参与撰写论文;刘金会和张焕国提出指导意见并修改论文.
-
表 1 Dilithium 和Aigis-sig 的推荐参数
Table 1 Recommended Parameters of Dilithium and Aigis-sig
参数类型 Dilithium 安全级别 参数类型 Aigis-sig 安全级别 128 b 192 b 256 b 128 b 192 b 256 b 输入参数设置 多项式次数n 256 256 256 输入参数设置 多项式次数n 256 256 256 矩阵行数k 4 5 6 矩阵行数k 4 5 6 矩阵列数l 3 4 5 矩阵列数l 3 4 5 模数q 8380417 8380417 8380417 模数q 2021377 3870721 3870721 私钥sk1, sk2范围\eta 6 5 3 私钥sk1范围\eta 2 2 1 私钥sk2范围\eta' 3 5 5 c中\pm 1 个数\tau 60 60 60 c中\pm 1 个数\tau 60 60 60 签名截取参数\beta 325 275 175 签名截取参数\beta 120 120 60 签名截取参数\beta' 175 275 275 签名范围参数\gamma 523776 523776 523776 签名范围参数\gamma 131072 131072 131072 签名范围参数 \gamma' 261888 261888 261888 签名范围参数 \gamma' 168448 322560 322560 输出参数性能 公钥大小/ B 1184 1472 1760 输出参数性能 公钥大小/ B 1056 1312 1568 私钥大小/ B 2800 3504 3856 私钥大小/ B 2448 3376 3888 签名大小/ B 2044 2701 3366 签名大小/ B 1852 2445 3046 期望重复次数 5.90 6.60 4.30 期望重复次数 5.86 7.61 6.67 经典安全性 100 141 174 经典安全性 99 141 179 量子安全性 91 128 158 量子安全性 90 128 163 表 2 密钥大小及签名大小的比较
Table 2 Comparison in Key Sizes and Signature Sizes
表 3 期望重复次数比较
Table 3 Comparison in Expect Repeations
方案 期望重复次数 方案 期望重复次数 Aitps-1024 (本文) e3.534=34.3 Aigis-sig-1024[16] 5.86 Dilizium 2.0-1024[29] e3.495=33.0 Dilithium-1024[13] 5.90 Aitps-1280 (本文) e4.0575=57.8 Aigis-sig-1280[16] 7.61 Dilizium 2.0-1280[29] e3.763=43.1 Dilithium-1280[13] 6.60 Aitps-1536 (本文) e3.791=44.3 Aigis-sig-1536[16] 6.67 Dilizium 2.0-1536[29] e2.908=18.3 Dilithium-1536[13] 4.30 -
[1] 中国互联网络信息中心. 第49次《中国互联网络发展状况统计报告》[EB/OL]. (2022-02-25)[2022-07-23]. http://www.cnnic.net.cn/n4/2022/0401/c88−1131.html CNNIC. The 49th statistical report on China’s Internet development [EB/OL]. (2022-02-25)[2022-07-23]. http://www.cnnic.net.cn/n4/2022/0401/c88−1131.html
[2] 冯琦,何德彪,罗敏,等. 移动互联网环境下轻量级 SM2两方协同签名[J]. 计算机研究与发展,2020,57(10):2136−2146 doi: 10.7544/issn1000-1239.2020.20200401 Feng Qi, He Debiao, Luo Min, et al. Efficient two-party SM2 signing protocol for mobile Internet[J]. Journal of Computer Research and Development, 2020, 57(10): 2136−2146 (in Chinese) doi: 10.7544/issn1000-1239.2020.20200401
[3] Shoup V. Practical threshold signatures[C]//Proc of the 19th Int Conf on the Theory and Application of Cryptographic Techniques (EUROCRYPT). Berlin: Springer, 2000: 207−220
[4] Damgård I, Mikkelsen G L, Skeltved T. On the security of distributed multiprime RSA[C]//Proc of the 17th Int Conf on Information Security and Cryptology(ICISC). Berlin: Springer, 2014: 18−33
[5] Lindell Y. Fast secure two-party ECDSA signing[C]//Proc of the 37th Annual Int Cryptology Conf(CRYPTO). Berlin: Springer, 2017: 613−644
[6] Doerner J, Kondi Y, Lee E, et al. Secure two-party threshold ECDSA from ECDSA assumptions[C]//Proc of the 39th IEEE Symp on Security and Privacy(S&P). Piscataway, NJ: IEEE, 2018: 980−997
[7] Xue Haiyang, Au M H, Xie Xiang, et al. Efficient online-friendly two-party ECDSA signature[C]//Proc of the 27th ACM SIGSAC Conf on Computer and Communications Security(CCS). New York: ACM, 2021: 558−573
[8] Maxwell G, Poelstra A, Seurin Y, et al. Simple Schnorr multi-signatures with applications to bitcoin[J]. Designs, Codes and Cryptography, 2019, 87(9): 2139−2164 doi: 10.1007/s10623-019-00608-x
[9] Komlo C, Goldberg I. FROST: Flexible round-optimized Schnorr threshold signatures[C]//Proc of the 27th Selected Areas in Cryptography (SAC). Berlin: Springer, 2014: 34−65
[10] Garillot F, Kondi Y, Mohassel P. Threshold schnorr with stateless deterministic signing from standard assumptions[C]//Proc of the 41st Annual Int Cryptology Conf (CRYPTO). Berlin: Springer, 2021: 127−156
[11] Shor P W. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer[J]. SIAM Review, 1999, 41(2): 303−332 doi: 10.1137/S0036144598347011
[12] Ajtai M. Generating hard instances of lattice problems (extended abstract)[C]//Proc of the 28th Annual ACM Symp on the Theory of Computing (STOC). New York: ACM, 1996: 99–108
[13] Ducas L, Durmus A, Lepoint T, et al. CRYSTALS-Dilithium: A lattice-based digital signature scheme[J]. IACR Transactions on Cryptographic Hardware and Embedded Systems, 2018, 2018(1): 238−268
[14] Bos J, Ducas L, Kiltz E, et al. CRYSTALS-Kyber: A CCA-secure module-lattice-based KEM[C]//Proc of IEEE European Symp on Security and Privacy(EuroS&P). Piscataway, NJ: IEEE, 2018: 353–367
[15] Fouque P A, Hoffstein J, Kirchner P, et al. Falcon: Fast-Fourier lattice-based compact signatures over NTRU [EB/OL]. (2020-01-10)[2022-07-23].https://falcon-sign.info/
[16] Zhang Jiang, Yu Yu, Fan Shuqin, et al. Tweaking the asymmetry of asymmetric-key cryptography on lattices: KEMs and signatures of smaller sizes[C]//Proc of the 23rd IACR Int Conf on Practice and Theory of Public-Key Cryptography (PKC). Berlin: Springer, 2020: 37–65
[17] Lu Xianhui, Liu Yamin, Zhang Zhenfei, et al. LAC: Practical ring-LWE based public-key encryption with byte-level modulus [J/OL]. IACR Cryptology ePrint Archive, 2018 [2022-09-25].https://eprint.iacr.org/2018/1009
[18] 沈诗羽,何峰,赵运磊. Aigis密钥封装算法多平台高效实现与优化[J]. 计算机研究与发展,2021,58(10):2238−2252 Shen Shiyu, He Feng, Zhao Yunlei. Multi-platform efficient implementation and optimization of Aigis-enc algorithm[J]. Journal of Computer Research and Development, 2021, 58(10): 2238−2252 (in Chinese)
[19] 周朕,何德彪,罗敏,等. 紧凑的Aigis-sig 数字签名方案软硬件协同实现方法[J]. 网络与信息安全学报,2021,7(2):64−76 doi: 10.11959/j.issn.2096-109x.2021026 Zhou Zhen, He Debiao, Luo Min, et al. Compact software/hardware co-design and implementation method of Aigis-sig digital signature scheme[J]. Chinese Journal of Network and Information Security, 2021, 7(2): 64−76 (in Chinese) doi: 10.11959/j.issn.2096-109x.2021026
[20] Cozzo D, Smart N P. Sharing the LUOV: Threshold post-quantum signatures[C]//Proc of the 17th IMA Int Conf on Cryptography and Coding (IMACC). Berlin: Springer, 2019: 128–153
[21] Damgard I, Orlandi C, Takahashi A, et al. Two-round n-out-of-n and multi-signatures and trapdoor commitment from lattices[J]. Journal of Cryptology, 2022, 35(2): 1−56
[22] Lyubashevsky V. Fiat-Shamir with aborts: Applications to lattice and factoring-based signatures[C]//Proc of the 15th Int Conf on the Theory and Application of Cryptology and Information Security (ASIACRYPT). Berlin: Springer, 2009: 598–616
[23] Baum C, Damgård I, Lyubashevsky V et al. More efficient commitments from structured lattice assumptions[C]//Proc of the 11th Int Conf on Security and Cryptography for Networks (SCN). Berlin: Springer, 2018: 368–385
[24] Vakarjuk J, Snetkov N, Willemson J. Dilizium: A two-party lattice-based signature scheme[J]. Entropy, 2021, 23(8): 989−1018 doi: 10.3390/e23080989
[25] Lyubashevsky V, Micciancio D, Peikert C, et al. SWIFFT: A modest proposal for FFT hashing[C]//Proc of the 15th Int Conf on Fast Software Encryption (FSE). Berlin: Springer, 2008: 54–72
[26] Fukumitsu M, Hasegawa S. A lattice-based provably secure multisignature scheme in quantum random oracle model[C]//Proc of the 14th Int Conf on Provable and Security (ProvSec). Berlin: Springer, 2020: 45–64
[27] Garcia-Escartin J C, Gimeno V, Moyano-Fernández J J. Quantum collision finding for homomorphic Hash functions [J/OL]. IACR Cryptology ePrint Archive, 2021 [2022-09-25].https://eprint.iacr.org/2021/1016
[28] Bai Shi, Galbraith S D. An improved compression technique for signatures based on learning with errors[C]//Proc of Cryptographers’ Track at the RSA Conf (CT-RSA). Berlin: Springer, 2014: 28–47
[29] Laud P, Snetkov N, Vakarjuk J. DiLizium 2.0: Revisiting two-party crystals-Dilithium [J/OL]. IACR Cryptology ePrint Archive, 2022 [2022-09-25].https://eprint.iacr.org/2022/644
[30] Langlois A, Stehlé D. Worst-case to average-case reductions for module lattices[J]. Designs, Codes and Cryptography, 2015, 75(3): 565−599 doi: 10.1007/s10623-014-9938-4
[31] Chor B, Goldwasser S, Micali S. Verifiable secret sharing and achieving simultaneity in the presence of faults (extended abstract)[C] //Proc of the 26th Annual Symp on Foundations of Computer Science(FOCS). Los Alamitos, CA: IEEE Computer Society, 1985: 383–395
[32] Lyubashevsky V, Nguyen N K, Seiler G. SMILE: Set membership from ideal lattices with applications to ring signatures and confidential transactions[C]//Proc of the 41st Annual Int Cryptology Conf (CRYPTO). Berlin: Springer, 2021: 611–640
[33] 田杨童, 张煌, 谢少浩, 等. 后量子的智能电表隐私保护方案[J]. 计算机研究与发展, 2019, 56(10): 2229−2242 Tian Yangtong, Zhang Huang, Xie Shaohao, et al [J]. Journal of Computer Research and Development, 2019, 56(10): 2229−2242 (in Chinese)
[34] Lyubashevsky V, Nguyen N K, Plancon M, et al. Shorter lattice-based group signatures via “almost free” encryption and other optimizations[C]//Proc of the 27th Int Conf on Theory and Application of Cryptology and Information Security (ASIACRYPT). Berlin: Springer, 2021: 218–248
[35] Esgin M F, Steinfeld R, Sakzad A, et al. Short lattice-based one-out-of-many proofs and applications to ring signatures[C]//Proc of the 17th Int Conf on Applied Cryptography and Network Security (ACNS). Berlin: Springer, 2019: 67–88
[36] NIST. PQC standardization process: Announcing four candidates to be standardized, plus fourth round candidates [EB/OL]. (2022-07-05)[2022-07-25].https://csrc.nist.gov/News/2022/pqc-candidates-to-be-standardized-and-round-4
[37] Bernstein D J, Hülsing A, Kölbl S, et al. The SPHINCS+ signature framework[C]//Proc of the 26th ACM SIGSAC Conf on Computer and Communications Security (CCS). New York: ACM, 2019: 2129−2146
[38] Güneysu T, Lyubashevsky V, Pöppelmann T. Practical lattice-based cryptography: A signature scheme for embedded systems[C]//Proc of the 14th Int Conf on Cryptographic Hardware and Embedded Systems (CHES). Berlin: Springer, 2012: 530–547
[39] Lyubashevsky V. Lattice signatures without trapdoors[C]//Proc of the 31st Int Conf on the Theory and Application of Cryptographic Techniques (EUROCRYPT). Berlin: Springer, 2012: 738−755
[40] Ducas L, Durmus A, Lepoint T, et al. Lattice signatures and bimodal Gaussians[C]// Proc of the 33rd Annual Int Cryptology Conf (CRYPTO). Berlin: Springer, 2013: 40–56
[41] Bruinderink L G, Hülsing A, Lange T, et al. Flush, gauss, and reload —A cache attack on the BLISS lattice-based signature scheme[C]// Proc of the 18th Int Conf on Cryptographic Hardware and Embedded Systems (CHES). Berlin: Springer, 2016: 323–345
[42] Pessl P, Bruinderink L G, Yarom Y. To BLISS-B or not to be: Attacking strongswan’s implementation of post-quantum signatures[C]//Proc of the 24th ACM SIGSAC Conf on Computer and Communications Security (CCS). New York: ACM, 2017: 1843–1855
[43] Zhang Jiang, Yu Yu, Fan Shuqin, et al. Aigis: A family of signatures and key encapsulatIon mechanisms from asymmetric (M)LWE and (M)SIS (the part of digital signature) [EB/OL]. (2019-02-28)[2022-07-25].https://sfjs.cacrnet.org.cn/site/term/list_72_1.html
[44] Bellare M, Neven G. Multi-signatures in the plain public-key model and a general forking lemma [C]//Proc of the 13th ACM SIGSAC Conf on Computer and Communications Security (CCS). New York: ACM, 2006: 390–399
-
期刊类型引用(3)
1. 李莉,宣佳铮,高尚,郭国疆. 基于不经意多项式估值的SM4协同加解密方案. 计算机应用研究. 2024(06): 1862-1868 . 百度学术
2. 张春玲,董新微,吴冰,胡志亮,孙俊杰,刘冬晖,傅颖勋. 面向电力物联网的分布式认证与安全传输架构. 应用科技. 2024(05): 80-90 . 百度学术
3. 王后珍,秦婉颖,刘芹,余纯武,沈志东. 基于身份的群组密钥分发方案. 计算机研究与发展. 2023(10): 2203-2217 . 本站查看
其他类型引用(0)