基于格的兩輪多重簽名方案

姜 玫，馬昌社

(華南師范大學(xué)計算機學(xué)院，廣州 510631)

多重簽名[1]允許一組簽名者聯(lián)合對同一消息進行簽名，生成一個壓縮的多重簽名且驗證者只需驗證最終簽名便可確認多個簽名者對同一消息進行了簽名[2]. 自1983年ITAKURA和NAKAMURA[1]提出多重簽名的概念以來，多重簽名的方案設(shè)計得到了充分研究，這些方案的安全性可歸約于大整數(shù)分解問題[3-4]、離散對數(shù)問題[5-7]及格上困難問題[8]. 多重簽名應(yīng)用廣泛，適用于電子合同、文件簽署、電子商務(wù)和電子政務(wù)等眾多領(lǐng)域[9].

2008年，BAGHERZANDI等[6]提出了基于離散對數(shù)的兩輪多重簽名BCJ方案，并在公鑰驗證模型下證明方案的安全性；2010年，MA等[7]提出了可在普通公鑰模型下證明安全的兩輪多重簽名MWLD方案，其安全性可歸約為求解離散對數(shù)問題；2016年，SYTA等[10]提出了具有較好擴展性的兩輪多重簽名CoSi方案，并認為該方案的安全性可歸約為求解離散對數(shù)的困難性，但未給出方案的形式化安全證明；2018年，MAXWELL等[11]提出了第一個支持公鑰聚合功能的兩輪多重簽名MuSig方案，并在普通公鑰模型下證明方案的安全性.

然而，DRIJVERS等[12]指出BCJ方案[6]、MWLD方案[7]、CoSi方案[10]以及MuSig方案[11]存在的安全缺陷，并依次針對這4個方案的安全漏洞進行了亞指數(shù)時間攻擊；同時，基于BCJ方案，提出了首個可形式化證明安全且只需2輪通信的mBCJ方案，其安全性可歸約于求解離散對數(shù)的困難性. mBCJ方案采用了具有二義性的同態(tài)承諾，其中同態(tài)承諾可實現(xiàn)MS-BN方案[5]中前2輪通信的效果，進一步降低多重簽名方案的通信代價；二義性的同態(tài)承諾能夠有效避免偽造者從歸約中抽取簽名私鑰，從而求解離散對數(shù)問題的具體實例，保證了mBCJ方案的安全性. 然而，基于離散對數(shù)問題構(gòu)造的方案不能抵抗量子攻擊，因此，mBCJ方案不適用于量子時代多方合作簽名場景.

基于格上困難問題構(gòu)造的方案能夠抵抗量子攻擊，滿足了人們對方案安全性的最新需求. 在構(gòu)造格上兩輪多重簽名方案時，本可沿用與mBCJ方案相似的構(gòu)造思路——以普通Schnorr簽名為基礎(chǔ)，結(jié)合二義性同態(tài)承諾實現(xiàn)格上兩輪多重簽名，然而，通過分析格上困難問題與離散對數(shù)問題的不同之處，發(fā)現(xiàn)構(gòu)造格上多重簽名方案時，直接選用同態(tài)承諾可節(jié)省方案的通信量和計算量.

因此，本文以GLP簽名[13]為基礎(chǔ)，結(jié)合格上高效同態(tài)承諾[14]，在多項式環(huán)上設(shè)計了一個支持公鑰聚合[11]功能的兩輪多重簽名方案(TLMS方案)，并在隨機預(yù)言機模型中證明該方案的安全性.

1 預(yù)備知識

1.1 符號說明

N表示一個正整數(shù)且為2的方冪，q表示一個素數(shù)；表示多項式環(huán)[x]/(xN+1)，q表示多項式環(huán)q[x]/(xN+1)，q中環(huán)元素為N-1階多項式且每一項系數(shù)屬于[-(q-1)/2,(q-1)/2]，d表示q的子集且每一項系數(shù)屬于[-d,d]，其中d+. 文中所有向量均為列向量，vΤ表示向量v的轉(zhuǎn)置；分別表示向量v的1-范數(shù)、2-范數(shù)、無窮范數(shù). 對于正整數(shù)η，η表示中無窮范數(shù)至多為η的多項式集合. 假設(shè)A表示集合，表示從A中均勻隨機抽取元素a. 參考文獻表示階為N-1且32項系數(shù)為±1、其余項系數(shù)為0的多項式集合. 參考文獻[14]，以特殊方式選擇參數(shù)q，使得q中范數(shù)小的元素可逆；挑戰(zhàn)空間為+}，差集為}.

1.2 困難問題及引理

問題2[16](Ring-SISm,q,β問題)給定m個多項式組成的向量a=(a1,a2,…,am)Τ要求找到一個非零向量x=(x1,x2,…,xm)m，使其滿足且

引理1[17]選擇參數(shù)N≥p≥1且為2的方冪，參數(shù)q為素數(shù)且滿足q=2p+1(mod 4p)，則多項式xN+1可分解為環(huán)中p個不可約多項式的乘積，且對于多項式環(huán)q中任意非零環(huán)元素y，若y的范數(shù)滿足或者則y存在逆元.

1.3 多重簽名及其安全性

假設(shè)一組簽名者L={1,2,…,l}將對消息m進行多重簽名. 一般地，多重簽名方案MS=(MKeyGen,MSign,MVerify)由以下3個算法組成：

(1)MKeyGen：密鑰生成算法，給定安全參數(shù)θ，該概率算法為每位簽名者i生成簽名私鑰ski和驗證公鑰pki；

(2)MSign：多重簽名生成算法，輸入公鑰集合PK={pk1,pk2,…,pkl}和消息m，若簽名成功,則該概率算法返回多重簽名σ，否則返回⊥；

(3)MVerify：多重簽名驗證算法，輸入待驗證簽名σ、消息m和公鑰集合PK={pk1,pk2,…,pkl}，若待驗證簽名有效,則該確定性算法返回1，否則返回0.

參照文獻[18]，下面給出多重簽名方案的安全定義.

定義1(安全定義)多重簽名方案MS=(MKeyGen,MSign,MVerify)是EUF-CMA安全的，若任意概率多項式時間的偽造者在以下游戲中獲勝的概率可忽略不計：

step 1：挑戰(zhàn)者輸入安全參數(shù)θ并執(zhí)行密鑰生成算法，產(chǎn)生簽名密鑰對(sk,pk)，且向偽造者發(fā)送驗證公鑰pk；

step 2：偽造者自適應(yīng)地發(fā)起消息mi(1≤i≤q)的簽名查詢，挑戰(zhàn)者執(zhí)行簽名生成算法產(chǎn)生簽名σi并發(fā)送給偽造者；

step 3：偽造者利用簽名σi(1≤i≤q)，偽造一個新消息m*的簽名σ*，若簽名σ*有效，則偽造者在游戲中獲勝.

1.4 廣義分叉引理

2006年，BELLARE和NEVEN[5]提出了分析數(shù)字簽名安全性的重要工具:

引理2[5](廣義分叉引理)假設(shè)q>1，集合H至少含有2個元素. 算法是一個隨機算法，輸入(x,h1,h2,…,hq)，可得輸出(J,δ)，其中0≤J≤q. IG是一個隨機算法,稱為輸入發(fā)生器. 算法的接受率acc為以下實驗中J≥1的概率：隨機選取和(x,h1,h2,…,hq). 基于算法的分叉算法GF同樣為隨機算法，其輸入為x，具體執(zhí)行過程如下：

如果I=I′且hI≠h′I,則返回(1,δ,δ′)，否則返回(0,ε,ε).

2 TLMS方案

2018年，BAUM等[14]提出了一個基于格的高效同態(tài)承諾方案:

(1)KeyGen算法：構(gòu)造矩陣A1和A2滿足A1=[InA′1]，其中In為n階單位矩陣，且且并輸出矩陣A1、A2.

(2)Commit算法：為了承諾x隨機抽取多項式向量計算承諾值并輸出.

結(jié)合格上高效同態(tài)承諾方案，本文給出了TLMS方案，該方案包括MKeyGen算法、MSign協(xié)議和MVerify算法，各算法的執(zhí)行過程如下：

(i)第1輪交互.

公布階段：若簽名者i為樹結(jié)構(gòu)Τ的根節(jié)點，則向子節(jié)點發(fā)送唯一的會話標識符ssid及消息m；否則等待接收ssid、m并將其發(fā)送至子節(jié)點.

承諾階段：簽名者i等待接收其子節(jié)點jCi發(fā)送的數(shù)據(jù)(tj,1,tj,2,apkj). 簽名者i查詢(b,e,f)←H0(m)，分別抽取和并計算承諾值和承諾值簽名者i查詢ui=H1(PK,pki)并計算部分聚合公鑰若簽名者i不是樹結(jié)構(gòu)Τ的根節(jié)點，則向其父節(jié)點發(fā)送數(shù)據(jù)(ti,1,ti,2,apki)，否則進入下一階段.

(ii)第2輪交互.

挑戰(zhàn)階段：若簽名者i為樹結(jié)構(gòu)Τ的根節(jié)點，則設(shè)置t1=ti,1、t2=ti,2以及apk=apki，查詢c←H2(t1,t2,apk,m)，并向其子節(jié)點發(fā)送數(shù)據(jù)(t1,t2,apk). 否則，等待接收數(shù)據(jù)(t1,t2,apk)，查詢c←H2(t1,t2,apk,m)，并向其子節(jié)點發(fā)送數(shù)據(jù)(t1,t2,apk).

響應(yīng)階段：簽名者i等待接收其子節(jié)點jCi發(fā)送的數(shù)據(jù)(zj,gj). 簽名者i計算z′i←αi+c·ui·ski. 若z′id-1 024×d-1 024，則設(shè)置并向其父節(jié)點發(fā)送數(shù)據(jù)(zi,gi)；否則重啟簽名協(xié)議. 若簽名者i為樹結(jié)構(gòu)Τ的根節(jié)點，則設(shè)置z←zi和g←gi，并輸出簽名σ←(t1,t2,z,g).

(3)MVerify算法：給定一組簽名者的聚合公鑰apk、消息m和待驗證多重簽名σ=(t1,t2,z,g)，驗證者查詢(b,e,f)←H0(m)和c←H2(t1,t2,apk,m). 若z且則判定簽名有效并返回1，否則返回0.

3 方案分析

3.1 正確性分析

t1modq，

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

3.2 安全性分析

定理1在隨機預(yù)言機模型下，若存在1個概率多項式時間的偽造者，在至多進行qH次隨機預(yù)言機查詢、qS次簽名查詢且至多涉及l(fā)max個公鑰的前提下，成功偽造TLMS多重簽名σ=(t1,t2,z,g)的概率為δ，其中承諾值t1,t2q，聚合后的簽名l·(d-1 024)×l·(d-1 024)(l為簽名者人數(shù)，部分簽名d-1 024×d-1 024，d>1 024)，隨機向量g則存在1個同樣時間復(fù)雜度的算法，給定能夠找到2個非零向量o1,o2q，使得a·o1+o2=0且的概率至少為其中，qA=δ-2(qH+lmax·qS)2/qn，DH1、DH2分別表示哈希函數(shù)H1、H2的值域.

證明假設(shè)參數(shù)x=(q,A,d)，其中Α=(a1)，多項式a服從q中的均勻分布. 給定攻擊TLMS方案的偽造者，可構(gòu)造1個模擬真實簽名環(huán)境的算法，具體構(gòu)造如下：

(1)輸入：參數(shù)x，哈希函數(shù)H1的響應(yīng)1,1,1,2,…,1,qH，哈希函數(shù)H2的響應(yīng)2,1,2,2,…,2,qH，隨機拋幣ρ.

(i)隨機預(yù)言機H0(m)查詢. 算法查詢表L0(m)，若其已定義則直接返回(b,e,f). 否則，算法從q中隨機抽取多項式并存儲于表L0(m)，隨后返回L0(m).

(ii)隨機預(yù)言機H1(PK,pki)查詢. 算法查詢表L1(PK,pki)，若其已定義則直接返回L1(PK,pki). 否則，算法查詢表L3(pki)，若其未定義，則將公鑰pki存儲于表L3. 然后，算法解析公鑰集合PK={pk1,pk2,…,pkl},并檢查每個公鑰pkjPK是否已存儲于表L3. 在保證每個公鑰pkjPK均存儲于表L3后，再依據(jù)以下3種情況一次性賦值H1(PK,pkj)滿足1≤j≤l：

①pkj=pk*且pk*PK；

②pkj≠pk*且pk*PK；

③pk*PK.

(iii)隨機預(yù)言機H2(t1,t2,apk,m)查詢. 算法首先查詢表L2(t1,t2,apk,m),若其已定義則直接返回L2(t1,t2,apk,m). 否則，算法進行內(nèi)部查詢H0(m)并存儲相關(guān)數(shù)據(jù). 然后，算法增加計數(shù)器ctr2并設(shè)置L2(t1,t2,apk,m)=2,ctr2，返回L2(t1,t2,apk,m).

δ-2(qH+lmax·qS)2/qn.

(1)

(2)

(3)

A(z-z*)+(c*-c)apk=0,

(4)

輸入?yún)?shù)x，運行分叉算法GF，得到其中，I=I′. 在分叉算法GF執(zhí)行過程中，分叉點位于第I次隨機預(yù)言機查詢H1(PK,pk*). 在分叉點之前，算法模擬的2次執(zhí)行環(huán)境是相同的，因此可知2次隨機預(yù)言機查詢H1(PK,pk*)的參數(shù)相同，即PK=PK′，pk*=pk*′. 此外，根據(jù)算法對隨機預(yù)言機H1(PK,pkj)的響應(yīng)可知：當(dāng)pkj≠pk*時，當(dāng)pkj=pk*時，從而可得apk≠apk′. 依據(jù)分叉算法GF的輸出，可得2個聚合公鑰等式:及假設(shè)公鑰集合中包含l*個pk*，結(jié)合式(4)可得:

(5)

(6)

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

A[(z-z*)(c*′-c′)-(z*-z*′)(c*-c)+

(7)

‖(z-z*)(c*′-c′)-(z*-z*′)(c*-c)+

256l·(d-1 024)+|l*|·643.

接下來需要證明

(z-z*)(c*′-c′)-(z*-z*′)(c*-c)+

(8)

依據(jù)文獻[19]的思路，可在證明過程中選擇系數(shù)稍大的多項式sk′(存在另一個多項式sk″，滿足A·sk′=A·sk″). 若

(z-z*)(c*′-c′)-(z*-z*′)(c*-c)+

(9)

則存在另一個sk″，使得

(z-z*)(c*′-c′)-(z*-z*′)(c*-c)+

(10)

3.3 參數(shù)分析

在實際選擇TLMS方案參數(shù)時，綜合考慮簽名協(xié)議重復(fù)次數(shù)、多重簽名長度和安全強度等因素，給出2組方案性能較優(yōu)的參數(shù)集(表1).

表1 方案參數(shù)集Table 1 The sets of scheme parameters

以表1中參數(shù)集合I為例，介紹如何計算簽名私鑰長度、驗證公鑰長度、多重簽名長度以及根式埃爾米特因子ξ. 簽名私鑰ski由2個從1中隨機抽取的多項式si和vi組成，因此，簽名私鑰長度可表示為比特. 驗證公鑰pkiq,則驗證公鑰長度為比特. 多重簽名σ由4個多項式組成，其中,t1,t2q，zl·(d-1 024)×l·(d-1 024),g因此，多重簽名長度為比特. 此時，可得到TLMS方案的根式埃爾米特因子同理可知:TLMS方案選取表1中參數(shù)集合II時，私鑰長度、公鑰長度及多重簽名長度分別為3 246、32 768、215 698比特，根式埃爾米特因子為1.005 5.

由表1可知TLMS方案所需參數(shù)較大，從而產(chǎn)生較長的公鑰和簽名. 但TLMS方案可支持公鑰聚合功能，降低簽名驗證代價；且通過結(jié)合同態(tài)承諾方案減少簽名者之間的通信次數(shù)，降低簽名消耗的通信代價. 因此，TLMS方案是降低多重簽名通信研究的一次有意義的嘗試.

4 結(jié)論

多重簽名是一種特殊的數(shù)字簽名，其允許一組簽名者合作對消息產(chǎn)生壓縮的簽名，可應(yīng)用于合同簽署、可信路由以及區(qū)塊鏈等場景. 本文構(gòu)造了一個基于格上困難問題并支持公鑰聚合功能的兩輪多重簽名方案，在隨機預(yù)言機模型中證明了該方案的安全性. 本方案具有較低的通信量和計算量，并能夠抵抗量子攻擊，可滿足未來量子時代最新的安全需求.

然而，在隨機預(yù)言機模型下證明安全的方案在現(xiàn)實應(yīng)用中可能難以保證安全性. 因此，如何在標準模型下構(gòu)造可抵抗量子攻擊的有效多重簽名方案可作為進一步的研究方向.