文嘉明 王后珍,3 劉金會(huì),4 張煥國(guó)

1（武漢大學(xué)國(guó)家網(wǎng)絡(luò)安全學(xué)院 武漢 430072）

2（空天信息安全與可信計(jì)算教育部重點(diǎn)實(shí)驗(yàn)室（武漢大學(xué)） 武漢 430072）

3（密碼科學(xué)技術(shù)國(guó)家重點(diǎn)實(shí)驗(yàn)室 北京 100878）

4（西北工業(yè)大學(xué)網(wǎng)絡(luò)空間安全學(xué)院 西安 710072）

（wenjm@whu.edu.cn）

隨著互聯(lián)網(wǎng)的飛速發(fā)展，手機(jī)等移動(dòng)設(shè)備的適用范圍不斷擴(kuò)大.根據(jù)中國(guó)互聯(lián)網(wǎng)絡(luò)信息中心發(fā)布的第49 次中國(guó)互聯(lián)網(wǎng)報(bào)告[1]，截至2021 年12 月，我國(guó)網(wǎng)民規(guī)模已達(dá)10.32 億人次，其中即時(shí)通信用戶規(guī)模達(dá)10.07 億人次，網(wǎng)絡(luò)支付用戶規(guī)模達(dá)9.04 億人次，網(wǎng)絡(luò)購(gòu)物用戶規(guī)模達(dá)8.42 億人次，在線辦公用戶規(guī)模達(dá)4.69 億人次.移動(dòng)設(shè)備日漸豐富的功能也帶來(lái)了更嚴(yán)重的隱私信息泄露問(wèn)題.作為傳統(tǒng)簽名的替代，數(shù)字簽名伴隨著網(wǎng)絡(luò)安全的需求出現(xiàn)，為用戶提供身份認(rèn)證和數(shù)據(jù)完整性認(rèn)證等，在移動(dòng)設(shè)備的各個(gè)功能中發(fā)揮重要作用.

然而，數(shù)字簽名的安全性建立在簽名密鑰安全的基礎(chǔ)上，如果密鑰不慎泄露，或者被惡意的網(wǎng)站和應(yīng)用程序等竊取，可能會(huì)出現(xiàn)惡意者冒充等情況，導(dǎo)致隱私信息被濫用、財(cái)產(chǎn)損失甚至威脅到國(guó)家安全.目前用來(lái)保護(hù)簽名密鑰安全的方法主要分為2 種[2]：借助硬件設(shè)備令牌保護(hù)密鑰和使用多方協(xié)同簽名的思想保護(hù)密鑰.受限于便利性和成本，前者難以大規(guī)模部署到移動(dòng)設(shè)備或物聯(lián)網(wǎng)設(shè)備中；而后者則是由2 個(gè)及以上的設(shè)備分別存儲(chǔ)密鑰的一部分，簽名時(shí)需要多個(gè)設(shè)備交互完成，任何一方都無(wú)法獨(dú)立地進(jìn)行簽名，分布式的處理能較好地保護(hù)密鑰安全.

多方協(xié)同簽名是一種特殊的門限簽名，參與簽名的用戶Pi首先運(yùn)行密鑰生成算法獲得私鑰ski，然后通過(guò)與其余用戶的交互生成公鑰pk.簽名過(guò)程也需要交互，對(duì)于給定的消息 μ，如果所有的用戶都同意對(duì) μ進(jìn)行簽名并誠(chéng)實(shí)參與交互，則交互后得到一個(gè)能用pk驗(yàn)證的合法消息簽名對(duì) (μ,σ).

盡管多方協(xié)同簽名協(xié)議已經(jīng)被研究了很長(zhǎng)時(shí)間，然而現(xiàn)有的大多數(shù)工作都集中在多方協(xié)同RSA 簽名[3-4]、多方協(xié)同ECDSA 簽名[5-7]、多方協(xié)同Schnorr簽名[8-10]以及多方協(xié)同SM2 簽名[2]等，這些方案都基于整數(shù)分解或者離散對(duì)數(shù)困難假設(shè)，Shor[11]已經(jīng)證明了這些困難假設(shè)無(wú)法抵抗量子計(jì)算機(jī)的攻擊.

相比之下，基于格上的困難假設(shè)構(gòu)造的密碼學(xué)方案，目前被認(rèn)為是抗量子的，同時(shí)具有運(yùn)算快、平均情況和最壞情況困難性等價(jià)等優(yōu)點(diǎn)[12]，受到了研究者們的廣泛關(guān)注.美國(guó)國(guó)家標(biāo)準(zhǔn)技術(shù)研究院（National Institute of Standards and Technology,NIST）舉辦的抗量子密碼（post-quantum cryptography，PQC）征集項(xiàng)目的抗量子密鑰封裝和數(shù)字簽名方案，就有相當(dāng)一部分是基于格的方案，例如CRYSTALS-Dilithium[13]，CRYSTALS-Kyber[14]，F(xiàn)alcon[15]等.中國(guó)密碼學(xué)會(huì)在2019 年舉辦的全國(guó)密碼算法設(shè)計(jì)競(jìng)賽中的獲獎(jiǎng)算法大部分也是基于格困難問(wèn)題構(gòu)造的，例如Aigisenc/sig[16]和 LAC.PKE[17]等.其中Aigis 設(shè)計(jì)團(tuán)隊(duì)觀察到Dilithium 簽名方案實(shí)際上可以非對(duì)稱地選擇參數(shù)，在保證總的重復(fù)次數(shù)相當(dāng)?shù)那闆r下，通過(guò)改變前后2 個(gè)拒絕抽樣的條件及其決定的重復(fù)次數(shù)，能取得更佳的效果.因而，該團(tuán)隊(duì)使用了參數(shù)選取更加靈活的非對(duì)稱模格問(wèn)題AMLWE/AMSIS（asymmetry module learning with errors/short integer solutions）來(lái)代替Dilithium 中的模格問(wèn)題MLWE/MSIS（module learning with errors/short integer solutions），設(shè)計(jì)出Aigis-sig 簽名方案，在安全性不變或略強(qiáng)的前提下達(dá)到更好的綜合效果，特別是擁有更短的公鑰、私鑰和簽名長(zhǎng)度，具體參見(jiàn)1.5 節(jié).值得一提的是，基于AMLWE/AMSIS的Aigis 方案不僅性能優(yōu)秀，它還是我國(guó)學(xué)者自主設(shè)計(jì)的抗量子密碼方案，也已經(jīng)出現(xiàn)在不同平臺(tái)上對(duì)其實(shí)現(xiàn)進(jìn)行優(yōu)化的相關(guān)工作[18-19].除了提升算法本身和優(yōu)化實(shí)現(xiàn)之外，基于其設(shè)計(jì)特殊類型簽名，例如能更好地保護(hù)密鑰安全的多方協(xié)同簽名，對(duì)研究國(guó)產(chǎn)抗量子密碼算法、維護(hù)網(wǎng)絡(luò)安全和國(guó)家安全也具有重要的意義.

2019 年，Cozzo 等人[20]對(duì)NIST 征集的抗量子數(shù)字簽名方案中所有進(jìn)入第2 輪的算法轉(zhuǎn)換成多方協(xié)同簽名（分布式簽名）進(jìn)行了評(píng)估，得出的結(jié)論是：如果直接使用已有的安全多方計(jì)算的通用技術(shù)，基于格的方案將需要用到線性秘密共享和混淆電路等，以及它們之間的互相轉(zhuǎn)換，會(huì)帶來(lái)較大的計(jì)算開(kāi)銷，需要較長(zhǎng)的時(shí)間.

2022 年，Damgard 等人[21]利用Lyubashevsky[22]提出的構(gòu)造基于格的數(shù)字簽名的“FSwA（Fiat-Shamir with aborts）”范式，得到了2 個(gè)交互輪數(shù)較小的基于格的多方協(xié)同簽名協(xié)議（使用加法同態(tài)承諾方案需要交互3 輪，使用陷門加法同態(tài)承諾方案僅需要交互2 輪），文中的秘密向量是從離散高斯分布中選取的，承諾方案則來(lái)自于文獻(xiàn)[23]及其擴(kuò)展方案，該協(xié)同簽名方案可以看作Dilithium 簽名方案的分布式版本，文獻(xiàn)[23]中給出了完整的安全性證明，其安全性基于MSIS 問(wèn)題和MLWE 問(wèn)題.

Vakarjuk 等人[24]也給出了一個(gè)3 輪的兩方協(xié)同簽名方案——Dilizium，與文獻(xiàn)[21]中方案的不同之處在于Dilizium 使用SWIFFT 同態(tài)Hash 函數(shù)[25]替換加法同態(tài)承諾方案，雖然得到了更小的密鑰和簽名尺寸，但是其缺點(diǎn)在于依賴Rejected MLWE 困難假設(shè)，是一種啟發(fā)式的困難假設(shè)[26]，同時(shí)SWIFFT 同態(tài)Hash 函數(shù)并不是對(duì)所有輸入都是加法同態(tài)的.現(xiàn)在也已經(jīng)出現(xiàn)了對(duì)具備同態(tài)性的Hash 函數(shù)的量子攻擊方法[27]，這可能會(huì)威脅到安全性，盡管如此，我們?nèi)詫⒃摲桨讣{入對(duì)比.

此外，文獻(xiàn)[21,24]中基于Dilithium 設(shè)計(jì)的兩方協(xié)同簽名方案均未考慮Dilithium 中用到的簽名尺寸壓縮技巧[28]，而最新方案Dilizium 2.0[29]采用了類似壓縮技術(shù)，使其更接近于NIST 標(biāo)準(zhǔn)化的Dilithium 算法，然而該工作并沒(méi)有評(píng)估實(shí)際的效率（重復(fù)次數(shù)）、密鑰和簽名尺寸等，也未進(jìn)行參數(shù)選取和實(shí)例化.

本文的主要貢獻(xiàn)包括3 個(gè)方面：

1）采用AMSIS/AMLWE 問(wèn)題對(duì)基于MSIS/MLWE問(wèn)題的Dilizium 2.0 兩方協(xié)同簽名方案進(jìn)行了修改和推廣，得到新方案Aitps.充分利用AMSIS/AMLWE的非對(duì)稱特性能夠更靈活地選擇參數(shù)，從而在安全性、計(jì)算效率、密鑰和簽名長(zhǎng)度這3 個(gè)方面達(dá)到更好的權(quán)衡，得到更優(yōu)的綜合性能.值得注意的是，Aitps方案可以被看作是Dilizium 2.0 方案的一個(gè)擴(kuò)展，在選取適當(dāng)參數(shù)時(shí)，Aitps 和Dilizium 2.0 本質(zhì)上等價(jià)，即Dilizium 2.0 可以看成Aitps 的一個(gè)特例.除此以外，Dilithium 設(shè)計(jì)團(tuán)隊(duì)和Aigis 設(shè)計(jì)團(tuán)隊(duì)對(duì)其方案的后續(xù)優(yōu)化，也適用于本文提出的方案.

2）使用“FSwA”范式構(gòu)造基于格的多方簽名在安全性上需要解決的一個(gè)關(guān)鍵問(wèn)題是防止未通過(guò)拒絕抽樣時(shí)的私鑰信息泄露，我們使用同態(tài)承諾解決了這個(gè)問(wèn)題（見(jiàn)第2 節(jié)）.對(duì)于新設(shè)計(jì)的Aitps 兩方協(xié)同簽名方案，我們提供了完整的安全性證明，結(jié)果表明其可以有效保護(hù)各方的簽名密鑰，具備兩方協(xié)同簽名在選擇消息攻擊下的存在性不可偽造性[5].

3）為了對(duì)比效果，本文給出了Aitps 方案的重復(fù)次數(shù)、密鑰和簽名大小的評(píng)估方法，該評(píng)估方法也適用于Dilizium 2.0 方案.我們使用Dilithium 第2 輪的參數(shù)[13]和Aigis-sig 的參數(shù)[16]將Dilizium 2.0 和Aitps全部進(jìn)行了實(shí)例化，并將Dilizium[24]（其密鑰和簽名尺寸優(yōu)于文獻(xiàn)[21]）也進(jìn)行計(jì)算并納入對(duì)比，相比之下，本文方案的密鑰以及簽名尺寸優(yōu)于現(xiàn)有的所有基于Dilithium 的兩方協(xié)同簽名方案，例如在同等的安全強(qiáng)度下，簽名尺寸可縮減20%以上.據(jù)我們所知，該結(jié)果也是基于格的兩方協(xié)同簽名方案中最優(yōu)的.

1 預(yù)備知識(shí)

1.1 符號(hào)說(shuō)明

本文用AT表示矩陣A的轉(zhuǎn)置，Ik表示k階單位矩陣，「x? 表示大于等于實(shí)數(shù)x的最小整數(shù)，lb 表示以2為底的對(duì)數(shù).

R和Rq分別表示多項(xiàng)式環(huán) Z[x]/(xn+1) 和Zq[x]/(xn+1).其中，n為正整數(shù)，n-1即為環(huán)中的多項(xiàng)式的最高次數(shù)，實(shí)際方案中一般選取n為2 的冪次（例如n=256）；q表示環(huán)Rq的模數(shù)，一般選取較大的素?cái)?shù)，在選取時(shí)需要綜合考慮方案的其他參數(shù)和工程實(shí)現(xiàn)的效率.表1 給出了一套具體參數(shù)的例子.

Table 1 Recommended Parameters of Dilithium and Aigis-sig表1 Dilithium 和Aigis-sig 的推薦參數(shù)

對(duì)于η>0，用Sη表示由所有的滿足‖w‖∞≤η的多項(xiàng)式w∈R（或Rq）組成的集合.

對(duì)于集合（或分布）D，用x←$D表示從集合（或按照分布）D中均勻隨機(jī)選取x.

1.2 格上的困難問(wèn)題

本文直接采用正規(guī)型（A）MLWE/（A）MSIS 問(wèn)題及假設(shè)，定義如下.

由D3中的(A;t)恢復(fù)(s1;s2)稱為計(jì)算性AMLWE問(wèn)題（computational AMLWE），區(qū)分2 個(gè)分布D3和D4中的(A,t)稱為判定性AMLWE 問(wèn)題（decisional AMLWE）.

Zhang 等人[16]已經(jīng)證明，對(duì)于目前已知最好的求解算法，有困難性關(guān)系：

1.3 （同態(tài)）承諾方案

承諾方案最早由Chor 等人[31]在研究可驗(yàn)證的秘密分享時(shí)提出，現(xiàn)在已經(jīng)被用在各種特殊類型簽名中，例如環(huán)簽名[32-33]、群簽名[34]等.在承諾方案中，對(duì)于給定的消息m∈Sm，承諾者選擇隨機(jī)向量r∈Sr用來(lái)計(jì)算m的承諾值com=Commitck(m;r)，其中ck∈Sck是承諾密鑰，并將承諾值com發(fā)送給接收者.在承諾打開(kāi)階段，承諾者將與承諾值相關(guān)的信息發(fā)送給接收者，接收者能利用承諾值以及相關(guān)信息計(jì)算得到一個(gè)打開(kāi)值（opening），并驗(yàn)證其確實(shí)是最初承諾的消息值.

除了具備正確性之外，承諾方案還需要具備隱藏性和綁定性2 個(gè)安全屬性.

1）隱藏性（hiding）指的是承諾值不會(huì)泄露被承諾值的任何信息，即通過(guò)com=Commitck(m;r)無(wú)法得到關(guān)于m或r的信息.

2）綁定性（binding）指的是打開(kāi)一個(gè)承諾不能得到2 個(gè)不同的值，即打開(kāi)com=Commitck(m;r)得到(m′,r′)，則 (m′,r′)≠(m,r)的概率是可忽略的.

根據(jù)敵手的能力和計(jì)算時(shí)間進(jìn)行分類：若敵手擁有無(wú)限計(jì)算時(shí)間與資源則稱為統(tǒng)計(jì)隱藏性（綁定性），若限制在多項(xiàng)式時(shí)間則稱為計(jì)算隱藏性（綁定性）.

在滿足正確性和安全性后，該承諾方案還具備3個(gè)性質(zhì)[21]：

1）密鑰均勻性（uniform key）.產(chǎn)生承諾密鑰的算法得到的承諾密鑰ck∈Sck在 Sck上均勻分布.

2）ξ-bits 最小熵.稱一個(gè)承諾方案至少有 ξ-bits最小熵，如果對(duì)于 ?ck∈Sck和 ?m∈Sm，均有

3）加法同態(tài)性.對(duì)于任意的m1,m2∈Sm以及隨機(jī)數(shù)r1,r2∈Sr，計(jì)算得到com1=Commitck(m1;r1)和com2=Commitck(m2;r2)，滿足加法同態(tài)性，即

1.4 CRYSTALS-Dilithium 數(shù)字簽名方案

2022 年7 月，NIST 宣布了PQC 項(xiàng)目第3 輪的評(píng)審結(jié)果[36]，確定了4 種即將標(biāo)準(zhǔn)化的算法，其中最為推薦的是CRYSTALS-Kyber（密鑰封裝）和 CRYSTALSDilithium（數(shù)字簽名），此外，另一個(gè)基于格的簽名方案Falcon 和基于Hash 的簽名方案SPHINCS+[37]也將標(biāo)準(zhǔn)化.在數(shù)字簽名方面，根據(jù)設(shè)計(jì)團(tuán)隊(duì)向NIST 提交的材料以及官方評(píng)價(jià)顯示，F(xiàn)alcon 是利用“Hashand-Sign”范式構(gòu)造，雖然擁有更短的尺寸，但其簽名算法內(nèi)部邏輯較復(fù)雜，實(shí)現(xiàn)難度較大；SPHINCS+是一類基于Hash 的無(wú)狀態(tài)簽名方案，其安全性依賴于底層Hash 函數(shù)的安全性，提供可靠的安全保證，然而會(huì)導(dǎo)致性能上的巨大成本.相對(duì)而言，Dilithium 擁有很強(qiáng)的安全性和優(yōu)秀的性能，能勝任絕大多數(shù)場(chǎng)景需求.

Dilithium 是一類基于格上的困難問(wèn)題構(gòu)造的數(shù)字簽名算法，算法的設(shè)計(jì)用到了“Fiat-Shamir with Aborts”范式，并使用了一些壓縮技巧[28,38]，主要具備3 個(gè)優(yōu)點(diǎn)[13]：

1）容易安全地實(shí)現(xiàn).此前的基于格的數(shù)字簽名方案[39-40]等需要從離散高斯分布中抽樣得到秘密值，效率較低，還容易遭到側(cè)信道攻擊而導(dǎo)致實(shí)現(xiàn)的不安全[41-42].與它們不同，Dilithium 簽名方案只需要進(jìn)行均勻抽樣，且除了抽樣之外，其余的運(yùn)算操作（例如多項(xiàng)式乘法和舍入）都可以在恒定時(shí)間內(nèi)完成，這有利于增強(qiáng)實(shí)現(xiàn)上的安全性.

2）公鑰+簽名尺寸優(yōu).為了能長(zhǎng)期使用，Dilithium團(tuán)隊(duì)提交給NIST 的參數(shù)選取非常保守，即便如此，Dilithium 方案的“公鑰+簽名”的尺寸也是現(xiàn)有的不使用離散高斯抽樣的格簽名方案中最小的.

3）模塊化切換.只需在環(huán)上進(jìn)行更多或更少的操作，或者修改其中所用的可擴(kuò)展輸出長(zhǎng)度Hash 函數(shù)（XOF，推薦使用SHAKE-128 或SHAKE-256）就可以切換不同級(jí)別的安全性.換句話說(shuō)，一旦獲得某個(gè)安全級(jí)別的更優(yōu)化實(shí)現(xiàn)，就很容易獲得其他安全級(jí)別的更優(yōu)化的實(shí)現(xiàn).

將Decomposeq(·)算法作用于多項(xiàng)式（例如環(huán)Rq中的元素）或由多項(xiàng)式組成的向量、矩陣時(shí)，表示對(duì)應(yīng)操作被分別獨(dú)立地作用到多項(xiàng)式的每個(gè)系數(shù).使用Decomposeq(·)算法，能對(duì)任意的由Rq中的多項(xiàng)式組成的向量 Θ和小范數(shù)向量 Λ，在不保存 Θ的情況下恢復(fù)Θ+Λ的高位比特，其正確性由引理1 保證：

引理1[13].Θ,Λ 是由Rq中的多項(xiàng)式組成的向量，ρ1和 ρ2是正整數(shù)，如果 ‖Λ‖∞≤ρ2且 ‖LowBitsq(Θ,ρ1)‖∞<則等式HighBitsq(Θ,ρ1)=HighBitsq(Θ+Λ,ρ1)成立.

Dilithium 簽名方案包括3 個(gè)子算法：密鑰生成算法、簽名算法和驗(yàn)證算法，這里介紹不考慮壓縮公鑰t的簡(jiǎn)化版本.

1）密鑰生成算法.首先使用種子生成矩陣A，然后均勻隨機(jī)選取sk1=s1←$,sk2=s2←$并計(jì)算t=As1+s2，公鑰pk=(A,t)，私鑰sk=(A,t,s1,s2).

算法1.Dilithium-簽名算法.

3）驗(yàn)證算法.在得到 μ和 σ=(z,c)后，首先利用Decomposeq(·)算法計(jì)算Az-ct的高位比特，然后根據(jù)z的范圍和挑戰(zhàn)值c的正確性判斷簽名合法性.

算法2.Dilithium-驗(yàn)證算法.

更詳細(xì)的Dilithium 簽名方案的正確性以及安全性分析參見(jiàn)文獻(xiàn)[13].

1.5 Aigis-sig 數(shù)字簽名方案

2020 年1 月，中國(guó)密碼學(xué)會(huì)發(fā)布了全國(guó)密碼算法設(shè)計(jì)競(jìng)賽的結(jié)果，Aigis-sig 數(shù)字簽名方案是公鑰密碼組獲得一等獎(jiǎng)的3 個(gè)方案中唯一的簽名方案，并且其對(duì)應(yīng)的密鑰封裝方案Aigis-enc 同樣也獲得了一等獎(jiǎng)，在國(guó)內(nèi)抗量子公鑰密碼設(shè)計(jì)中具有高度評(píng)價(jià)，經(jīng)過(guò)進(jìn)一步的改進(jìn)后，將成為我國(guó)自主設(shè)計(jì)的重要抗量子密碼方案.

Aigis-sig 的主要設(shè)計(jì)思想與Dilithium 類似，改進(jìn)之處在于使用了更加靈活的非對(duì)稱的格上困難問(wèn)題——AMSIS 問(wèn)題和AMLWE 問(wèn)題，通過(guò)改變私鑰s2的選取范圍以及拒絕抽樣的條件，得到了更優(yōu)的公鑰尺寸或簽名尺寸，以及更強(qiáng)的安全性.Aigis-sig 簽名方案包括3 個(gè)子算法：密鑰生成算法、簽名算法和驗(yàn)證算法，這里介紹不考慮壓縮公鑰t的簡(jiǎn)化版本.

1）密鑰生成算法.首先使用種子生成矩陣A，然后均勻隨機(jī)選取sk1=s1←$,sk2=s2←$并計(jì)算t=As1+s2，公鑰pk=(A,t)，私鑰sk=(A,t,s1,s2).

算法3.Aigis-sig-簽名算法.

3）驗(yàn)證算法.在得到 μ和 σ=(z,c)后，首先利用Decomposeq(·)算法計(jì)算Az-ct的高位比特，然后根據(jù)z的范圍和挑戰(zhàn)值c的正確性判斷簽名合法性，這里的 β（以及未顯式表達(dá)的 β′）與算法2 中的 β不同.

算法4.Aigis-sig-驗(yàn)證算法.

2 兩方協(xié)同簽名方案

本文基于AMSIS/AMLWE 困難問(wèn)題提出的兩方協(xié)同簽名方案有2 個(gè).

2）簽名算法.我們以用戶P1的視角為例介紹兩方協(xié)同簽名協(xié)議，對(duì)消息 μ∈M進(jìn)行簽名的具體過(guò)程如圖1 所示，運(yùn)行協(xié)議后得到z1.同樣地，P2也會(huì)得到z2，將兩者合起來(lái)即得到簽名 σ=(z,c,h).

和Dilithium 一樣，簽名算法的第1 步是計(jì)算身份協(xié)議所需要用到的挑戰(zhàn)值c∈C=Bτ（Bτ的定義與文獻(xiàn)[13,16]相同，表示環(huán)R中恰好有 τ 個(gè)系數(shù)為 ±1且其余系數(shù)為 0的元素組成的集合），該值應(yīng)該由雙方一起生成，因而需要雙方交換多個(gè)消息，但是并不能直接交換w1和w2（或其對(duì)應(yīng)的高位比特），主要原因有2 個(gè)方面：

①如果P1將w1發(fā) 送給了P2，而之后未通過(guò)拒絕抽樣，簽名過(guò)程中止，(w1,z1) 可能會(huì)泄露關(guān)于私鑰sk1,1的信息.之前的工作[26]的解決方法是利用非標(biāo)準(zhǔn)的格困難假設(shè)——Rejected MLWE 假設(shè)，然而這只是一個(gè)啟發(fā)式假設(shè)，可能存在安全性問(wèn)題.

②如果P2知道了 (w1,z1)，可以從z1中提取得到c·sk1,2從而得到P1的私鑰的一部分sk1,2，P1同理，這也可能會(huì)導(dǎo)致安全性上的威脅.

我們用同態(tài)承諾方案來(lái)解決這個(gè)問(wèn)題.P1和P2均可以用公鑰pk=(A,t) 和消息 μ計(jì)算得到消息對(duì)應(yīng)的承諾密鑰ck←Hck(μ,pk)，先互相交換承諾值comi=Commitck(wi,H;ri)，由于使用的是同態(tài)承諾，因此可以將不同用戶的承諾值聚合在一起，并用來(lái)在簽名生成階段計(jì)算挑戰(zhàn)值.同時(shí)和密鑰生成算法一樣，在互相交換承諾值comi之前需要先交換承諾值對(duì)應(yīng)的Hash 值H3(comi)，如果缺少了這一步，惡意的P2可以在看到P1的承諾值com1自適應(yīng)地選擇com2′.

在第3 輪通信中，雙方交換 (zi,ri).并驗(yàn)證對(duì)方提供的comi是否確實(shí)是用同態(tài)承諾方案計(jì)算得到，驗(yàn)證通過(guò)后，計(jì)算得到完整的z=z1+z2.

3）驗(yàn)證算法.收到消息 μ對(duì)應(yīng)的簽名σ=(z,c,h)以及用來(lái)計(jì)算承諾的r，作如下驗(yàn)證.

1）驗(yàn)證 ‖z‖∞<2γ-2β.

2）用公鑰pk=(A,t) 和消息 μ計(jì)算得到消息對(duì)應(yīng)的承諾密鑰ck←Hck(μ,pk).

5）驗(yàn)證c=H0(μ,com)，若通過(guò)，返回1（即接受簽名），否則返回0（即拒絕簽名）.

2.1 方案的正確性分析

證明本文提出方案的正確性，實(shí)際上就是證明3個(gè)結(jié)論：

同時(shí)根據(jù)由簽名算法的定義得到LowBitsq(Azct,4γ′)<2γ′-2β′，由引理1 有

3）Openck(com,,r)=1

由于com是在簽名算法中通過(guò)成功運(yùn)行“挑戰(zhàn)值計(jì)算階段”以及承諾方案的加法同態(tài)性質(zhì)生成的，因此有

是w1,H+w2,H對(duì)應(yīng)的一個(gè)承諾值，即為對(duì)應(yīng)的一個(gè)承諾.

驗(yàn)證方計(jì)算得到wH=HighBitsq(Az-ct,4γ′)和簽名算法是相同的，再利用h=wH-進(jìn)行“糾正”得到，因此有Openck(com,,r)=1.

2.2 方案的安全性分析

本節(jié)給出兩方協(xié)同簽名的安全性定義以及本文所提方案的安全性證明.和文獻(xiàn)[21]一樣，我們沿用Lindell 給出的兩方協(xié)同簽名的基于游戲的安全性定義[5]，在該定義中，假設(shè)敵手只能調(diào)用一次密鑰生成算法，而多個(gè)簽名會(huì)話可以同時(shí)執(zhí)行.

我們證明本文提出的兩方協(xié)同簽名方案具有分布式簽名的選擇消息攻擊下的存在性不可偽造性（distributed signature with existential unforgeability under chosen message attack,DS-EU-CMA），需要用到如下的實(shí)驗(yàn)ExpDS-EU-CMA(A)：

初始時(shí)定義簽名消息集合 M為空集，敵手可以詢問(wèn)協(xié)同簽名的諭言機(jī) ODS，得到若干個(gè)消息簽名對(duì)(μi,σi)，并將 μi添加到 M中，最后敵手需要產(chǎn)生一個(gè)新的 (μ?,σ?)，其中 μ?≠μi.

兩方協(xié)同簽名方案DS-EU-CMA 安全意味著對(duì)于任意概率多項(xiàng)式時(shí)間的敵手 A，成功偽造簽名的優(yōu)勢(shì)AdvDS-EU-CMA(A)是可忽略的，其中優(yōu)勢(shì)的定義為

我們的安全證明的主要思想與文獻(xiàn)[21,29]類似，我們證明了：如果敵手能以不可忽略的概率成功進(jìn)行一個(gè)有效的偽造，則可以攻破承諾方案的計(jì)算綁定性或者AMLWE/AMSIS 假設(shè)，即能以概率 εBinding攻破承諾方案的計(jì)算綁定性，或能以概率解決參數(shù)為 (q,k,l,η,η′)的判定性AMLWE 問(wèn)題，或能以概率解決參數(shù)為 (q,k,l+1,δ,δ′)的AMSIS 問(wèn)題，其中 ε均表示不可忽略的概率值.證明過(guò)程中需要用到文獻(xiàn)[44]提出的分叉引理，在此先進(jìn)行介紹.

引理2.分叉引理（general forking lemma）[44].對(duì)于固定的詢問(wèn)次數(shù)Q≥1以及集合 H（H中的元素個(gè)數(shù)|H|≥2），令 B是一個(gè)隨機(jī)化算法，滿足(i,σout)←B(x,h1,h2,…,hQ)，其輸入 h1,h2,…,hQ∈H,x是由一個(gè)隨機(jī)化的輸入值生成算法 IG產(chǎn)生，輸出i∈{0,1,…,Q},σout是一個(gè)輔助輸出.

FB(x)是與 B相關(guān)聯(lián)的分叉算法，定義為：

1）B 選取 ρ作為隨機(jī)的硬幣（coins），以隨機(jī)化.

2）隨機(jī)選取 h1,h2,…,hQ←$H.

3）運(yùn)行算法 B：(i,σout)←B(x,h1,h2,…,hQ;ρ).

定義 B的接受概率acc和分叉概率frk.

在本方案中，定義IG 的輸出為(A,t,ck?).

定理1.假設(shè)承諾方案具有計(jì)算隱藏性、計(jì)算綁定性、密鑰均勻性、加法同態(tài)性和 ξ-bits 最小熵.那么對(duì)于任意的可以詢問(wèn)1 次密鑰生成隨機(jī)諭言機(jī)，QS次簽名諭言機(jī)和QH次隨機(jī)諭言機(jī)H0,H1,H2,H3,Hck的概率多項(xiàng)式時(shí)間敵手，該兩方協(xié)同簽名方案是DSEU-CMA 安全的，其安全性依賴于參數(shù)為(q,k,l,η,η′)的AMLWE 假設(shè)以及參數(shù)為 (q,k,l+1,δ,δ′)的AMSIS假設(shè).

證明.對(duì)于一個(gè)能攻破該兩方協(xié)同簽名方案的敵手 A，我們首先構(gòu)造一個(gè)關(guān)于 A 的模擬器 S，能在不使用誠(chéng)實(shí)用戶的密鑰的前提下模擬協(xié)議中誠(chéng)實(shí)用戶Pn的行為.S 用到了S imKeyGen(·) 及S imS ign(·)諭言機(jī)[21,29].我們通過(guò)一系列的中間游戲Gamei來(lái)定義 S，并比較了每一個(gè)游戲和前一個(gè)游戲的差別.在得到S 后，我們利用 S 構(gòu)造了算法 B，并通過(guò)調(diào)用分叉引理獲得針對(duì)2 個(gè)不同的挑戰(zhàn)值的偽造簽名，這使得我們能攻破承諾方案的計(jì)算綁定性或者AMLWE/AMSIS 假設(shè).

Game0：分為隨機(jī)諭言機(jī)模擬（random oracle simulation）、誠(chéng)實(shí)用戶諭言機(jī)模擬和偽造3 個(gè)部分.

1）隨機(jī)諭言機(jī)模擬.本方案中用到5 個(gè)Hash 函數(shù)H0,H1,H2,H3,Hck，分別模擬：

①H1:{0,1}?→{0,1}l1（用在密鑰生成算法中的公鑰矩陣生成）.構(gòu)造空的Hash 列表HT1，當(dāng)向HT1詢問(wèn)x′時(shí)，若列表中已經(jīng)有HT1(x′) 則返回HT1(x′)，否則從{0,1}l1中均勻隨機(jī)地選取一個(gè)值y′當(dāng)作HT1(x′)，并將(x′,y′)填入HT1.

②H2:{0,1}?→{0,1}l2（用在密鑰生成算法中的私鑰和t的生成）.構(gòu)造空的Hash 列表HT2，當(dāng)向HT2詢問(wèn)x′時(shí)，若列表中已經(jīng)有HT2(x′) 則返回HT2(x′)，否則從 {0,1}l2中均勻隨機(jī)地選取一個(gè)值y′當(dāng)作HT2(x′)，并將 (x′,y′)填入HT2.

③H3:{0,1}?→{0,1}l3（用在簽名算法中的交換承諾值）.構(gòu)造空的Hash 列表HT3，當(dāng)向HT3詢問(wèn)x′時(shí)，若列表中已經(jīng)有HT3(x′) 則返回HT3(x′)，否則從{0,1}l3中均勻隨機(jī)地選取一個(gè)值y′當(dāng)作HT3(x′)，并將(x′,y′)填入HT3.

④H0:{0,1}?→C（用在簽名算法中的計(jì)算挑戰(zhàn)值）.構(gòu)造空的Hash 列表HT0，并令ctr=0.注意到H0的輸入為 (μ,com)，因此需要先詢問(wèn)隨機(jī)諭言機(jī)H3(μ,pk)，若列表中已經(jīng)有HT0(μ,com)則返回HT0(μ,com)，否則設(shè)ctr=ctr+1，并將 hctr當(dāng)作HT0(μ,com)，將(μ,com,hctr)填入HT0.其中，{h1,h2,…,hQS+QH+1}是 S收到的作為輸入的隨機(jī)挑戰(zhàn)值.

⑤Hck:{0,1}?→Sck（用在計(jì)算承諾密鑰）.構(gòu)造空的Hash 列表Hck，由于Hck的輸入為 (μ,pk)，故向HTck詢問(wèn) (μ,pk)，若列表中已經(jīng)有HTck(μ,pk)，則返回HTck(μ,pk)，否則從承諾密鑰空間 Sck中均勻隨機(jī)地選取一個(gè)值y當(dāng)作HTck(μ,pk)，并將 (μ,pk,y)填入HTck.

搜索Hash 列表算法S earchHash(HT,h).在構(gòu)造Hash 列表HT后，可以定義算法S earchHash(HT,h):對(duì)于h，在列表HT中尋找原像滿足HT()=h，如果不存在原像，則返回flag=alert 并設(shè)置m=⊥，如果存在不止一個(gè)原像，則返回flag=bad.

2）誠(chéng)實(shí)用戶諭言機(jī)模擬（honest party oracle simulation）.在這個(gè)游戲中，敵手 A的行為和兩方協(xié)同簽名中的一個(gè)誠(chéng)實(shí)用戶相同.與文獻(xiàn)[21,29]類似，當(dāng)A詢問(wèn)誠(chéng)實(shí)用戶諭言機(jī)時(shí)，S可以直接按照密鑰生成算法和簽名算法的定義進(jìn)行模擬，限于篇幅，在此處不展開(kāi)，感興趣的讀者可以參見(jiàn)文獻(xiàn)[21,29].

3）偽造（forgery）.敵手 A輸出一個(gè)偽造的消息簽名對(duì) (μ?,σ?=(z?,c?,h?)).對(duì)于給定的偽造，S操作為：

將 S 在第i個(gè)游戲中不輸出 (0,⊥)的概率記作Pr[Gamei]，有Pr[Game0]:=AdvDS-EU-CMA(A).

Game1: 相較于Game0，Game1僅改變 S的簽名過(guò)程，主要的變化在于挑戰(zhàn)值c改為從集合 C中均勻隨機(jī)選取，因此 S能在不與敵手 A交互的情況下計(jì)算出zn.在收到挑戰(zhàn)值 hi后，S運(yùn)行搜索Hash 列表算法S earchHash(HT3,hi)，找到原像comi并計(jì)算com=comn+comi，最后，S 用c當(dāng)作對(duì)隨機(jī)諭言機(jī)H0的詢問(wèn)(μ,com)的回答.除了3 種情況之外，Game1和Game0是等同的.

和之前的游戲一樣，S將wn,H進(jìn)行承諾得到comn=Commitck(wn,H,rn)，其中rn←$Sr，并將H3(comn)發(fā)送給敵手 A.

Game2和Game1之間的區(qū)別是 A 在進(jìn)行QS次詢問(wèn)后，區(qū)分一個(gè)模擬的承諾方案和一個(gè)真實(shí)的承諾方案的優(yōu)勢(shì)不同，即攻破承諾方案的隱藏性的優(yōu)勢(shì)不同.因此有 |Pr[Game2]-Pr[Game1]|≤QS·εHiding.

因此，若敵手以不可忽略的概率成功偽造簽名，則能以不可忽略的概率攻破承諾方案的計(jì)算綁定性或AMLWE/AMSIS 假設(shè).證畢.

3 性能分析與比較

為密碼方案選擇合適的參數(shù)需要在多個(gè)方面權(quán)衡，本方案參數(shù)的選擇應(yīng)該在保證足夠安全性的前提下，使得期望重復(fù)次數(shù)（影響通信輪數(shù)和簽名時(shí)間）較小且擁有較短的簽名和密鑰尺寸，因此我們主要考慮這3 項(xiàng)指標(biāo)，并以此評(píng)價(jià)方案的性能.

3.1 重復(fù)次數(shù)的期望值（通信重復(fù)輪數(shù)）

3.2 密鑰和簽名大小

這里和文獻(xiàn)[24]一樣，由于ski,1和ski,2的每個(gè)系數(shù)都可能是負(fù)的元素，因此需要額外1b 來(lái)表示符號(hào).

3）計(jì)算簽名大小.簽名由(z,c,h)共3 個(gè)部分組成：

z是一個(gè)l維向量，且滿足 ‖z‖∞≤2(γ-β)-1，因此z的大小約為n·l·(「lb((γ-β)-1)?+1).

c是挑戰(zhàn)值，和文獻(xiàn)[13,16,22]選取自相同的挑戰(zhàn)值集合，因此c的大小為 τ·(「lbn?+1).

綜上，簽名（單位B）共需要約

特別地，當(dāng) η′=η,β′=β時(shí)，本文的方案與Dilizium2.0兩方協(xié)同簽名方案本質(zhì)上等價(jià)，也就是說(shuō)Dilizium 2.0 可以視為本文方案的一個(gè)特例.

我們選取Dilithium 第2 輪的參數(shù)[13]以及Aigis相對(duì)應(yīng)的參數(shù)[16]進(jìn)行實(shí)例化，參數(shù)如表1 所示，得到的密鑰大小和簽名大小的對(duì)比見(jiàn)表2，簽名成功所需重復(fù)次數(shù)的對(duì)比見(jiàn)表3.

Table 3 Comparison in Expect Repeations表3 期望重復(fù)次數(shù)比較

由表2 可知，我們提出的兩方協(xié)同簽名方案比文獻(xiàn)[24,29]擁有更短的密鑰和簽名.而在決定運(yùn)行時(shí)間的期望重復(fù)次數(shù)方面，雖然大于文獻(xiàn)[29]的方案，但由文獻(xiàn)[16]和表3 可知，即使重復(fù)次數(shù)略大，在進(jìn)行工程上的優(yōu)化以及使用AVX2 進(jìn)行加速后，Aigissig 甚至在一些參數(shù)下快于Dilithium（具體運(yùn)行時(shí)間對(duì)比參見(jiàn)文獻(xiàn)[16]），因此我們合理地認(rèn)為實(shí)際情況下Aitps（本文提出的基于Aigis-sig 的兩方協(xié)同簽名方案）與Dilizium 2.0（現(xiàn)有最優(yōu)的基于Dilithium 的兩方協(xié)同簽名方案）效率相當(dāng).

4 總結(jié)及展望

本文提出的Aitps 是一種基于格的兩方協(xié)同簽名協(xié)議，允許2 個(gè)用戶在不泄露各自私鑰的情況下通過(guò)交互對(duì)給定的消息進(jìn)行簽名，同時(shí)任何一方都無(wú)法重構(gòu)密鑰和獨(dú)自完成整個(gè)簽名過(guò)程，保證了密鑰的安全性.在協(xié)議的安全性方面，我們將其歸約到非對(duì)稱模格困難問(wèn)題以及用到的承諾方案的計(jì)算隱藏性（本質(zhì)上也是基于模格問(wèn)題的困難性）.由于現(xiàn)有的最優(yōu)的相關(guān)方案Dilizium 2.0 沒(méi)有評(píng)估效果，我們也給出了Aitps 方案各項(xiàng)評(píng)價(jià)指標(biāo)的計(jì)算公式（也適用于Dilizium 2.0 方案），并采用CRYSTALSDilithium 和Aigis-sig 的推薦參數(shù)進(jìn)行實(shí)例化，相比之下，本文提出的方案比現(xiàn)有的所有基于Dilithium 的兩方簽名方案具有更小的密鑰和簽名尺寸，特別是簽名尺寸，能減少至少20%.

與文獻(xiàn)[21]一樣，本文提出的兩方協(xié)同簽名方案很容易擴(kuò)展成為安全的多方協(xié)同簽名方案.在未來(lái)的工作中，我們將進(jìn)一步考慮使用提交給NIST 的CRYSTALS-Dilithium 簽名方案中對(duì)公鑰的壓縮技巧繼續(xù)減小公鑰尺寸，以及嘗試降低期望重復(fù)次數(shù).

作者貢獻(xiàn)聲明：文嘉明提出算法設(shè)計(jì)思路并撰寫論文；王后珍提出算法優(yōu)化及分析思路，并參與撰寫論文；劉金會(huì)和張煥國(guó)提出指導(dǎo)意見(jiàn)并修改論文.