文嘉明 王后珍,3 劉金會,4 張煥國

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

2（空天信息安全與可信計算教育部重點實驗室（武漢大學） 武漢 430072）

3（密碼科學技術(shù)國家重點實驗室 北京 100878）

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

（wenjm@whu.edu.cn）

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

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

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

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

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

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

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

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

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

本文的主要貢獻包括3 個方面：

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

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

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

1 預(yù)備知識

1.1 符號說明

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

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

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

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

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

1.2 格上的困難問題

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

算法1.Dilithium-簽名算法.

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

算法2.Dilithium-驗證算法.

更詳細的Dilithium 簽名方案的正確性以及安全性分析參見文獻[13].

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

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

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

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

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

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

算法4.Aigis-sig-驗證算法.

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

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

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

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

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

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

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

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

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

1）驗證 ‖z‖∞<2γ-2β.

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

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

2.1 方案的正確性分析

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

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

3）Openck(com,,r)=1

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

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

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

2.2 方案的安全性分析

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

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

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

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

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

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

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

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

2）隨機選取 h1,h2,…,hQ←$H.

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

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

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

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

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

Game0：分為隨機諭言機模擬（random oracle simulation）、誠實用戶諭言機模擬和偽造3 個部分.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 性能分析與比較

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

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

3.2 密鑰和簽名大小

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

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

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

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

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

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

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

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

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

4 總結(jié)及展望

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

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

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