Aigis-sig方案的門限數(shù)字簽名協(xié)議研究

Aigis-sig方案的門限數(shù)字簽名協(xié)議研究*

趙秀鳳,付雨信息工程大學密碼工程學院,鄭州4500011引言數(shù)字簽名是公鑰密碼體系的重要組成部分,在電子商務(wù)、電子政務(wù)、加密貨幣等多個領(lǐng)域都發(fā)揮著重要作用.在標準的數(shù)字簽名方案中,簽名者使用私鑰對消息簽名,驗證者使用公鑰驗證簽名的合法性.近年來,由于區(qū)塊鏈技術(shù)的快速發(fā)展,門限簽名在該領(lǐng)域得到了深入研究與廣泛應(yīng)用.其中一個主要原因是,在移動互聯(lián)網(wǎng)應(yīng)用背景下,部分移動終端的防護能力較差,簽名私鑰存儲的安全性很難得到有效保證.在(t,n)-門限簽名協(xié)議中,每個參與者擁有一個簽名私鑰份額,簽名過程中任何不少于t個參與者的集合能夠利用各自私鑰份額生成簽名份額,然后通過重構(gòu)簽名份額生成完整簽名.簽名過程中單個參與者無法恢復完整的簽名私鑰,既保證簽名的正確性,又保證簽名私鑰的安全性,驗證過程可由單個參與者利用驗證公鑰獨立完成.門限簽名協(xié)議可以抵御單點腐化帶來的安全隱患,具有更好的魯棒性.目前,國際上基于橢圓曲線數(shù)字簽名算法(ellipticcurvedigitalsignaturealgorithm,ECDSA)已經(jīng)設(shè)計了兩方數(shù)字簽名協(xié)議[1]、門限數(shù)字簽名協(xié)議[2].國內(nèi)有學者對基于ECDSA和國密算法SM2的兩方協(xié)同生成數(shù)字簽名的方法進行了研究[3,4].ECDSA和SM2算法的安全性基于離散對數(shù)問題的困難性,因此均不能抵抗量子計算攻擊.對于格上困難問題,目前還沒有提出有效的量子求解算法,所以研究如何設(shè)計安全高效的基于格的數(shù)字簽名方案的門限簽名協(xié)議十分必要.FSwA(Fiat-ShamirwithAborts)框架[5,6]是構(gòu)建基于格的數(shù)字簽名方案最流行的技術(shù)之一,目前被廣泛應(yīng)用于基于格的數(shù)字簽名方案的設(shè)計中.美國國家標準與技術(shù)研究所征集第三輪候選算法CRYSTALS-Dilithium[7]、國內(nèi)算法競賽獲獎算法Aigis-sig[8]、木蘭[9]等都采用了該框架.使用FSwA框架的數(shù)字簽名方案,在簽名生成過程中需要進行拒絕采樣條件的驗證[6],以確保簽名值不會泄露簽名私鑰信息.但是拒絕采樣環(huán)節(jié)也是構(gòu)造門限簽名協(xié)議的主要障礙,在協(xié)議交互過程中,協(xié)議中間值需要保密,即需要密態(tài)計算協(xié)議中間值,因此本文擬引入全同態(tài)加密技術(shù)來解決此問題.Boneh等人[10]基于門限全同態(tài)加密技術(shù)設(shè)計了一類通用的門限簽名協(xié)議構(gòu)造方法,即先通過門限秘密分享體制生成簽名私鑰份額并分發(fā)給各參與者,采用同態(tài)計算簽名電路的方法生成簽名份額,再通過重構(gòu)算法生成簽名.但是Boneh等人[10]只在理論上給出了門限簽名協(xié)議的通用化構(gòu)造方法,并未對協(xié)議中間值的保密及協(xié)議重復運行次數(shù)等問題進行充分討論.Damg?rd等人[11]基于Dilithium-G[12]方案,借助陷門同態(tài)承諾方案,設(shè)計了一個兩輪的(n,n)-門限簽名協(xié)議,并證明了該協(xié)議滿足適應(yīng)性選擇消息攻擊下的存在不可偽造性.Dilithum-G方案是CRYSTALS-Dilithium方案的變體,兩個方案的主要區(qū)別在于拒絕采樣的實現(xiàn)方式不同.Dilithum-G方案中挑戰(zhàn)向量服從高斯分布,其和分布仍服從高斯分布.在上述門限簽名協(xié)議中,生成門限簽名一般需要對各參與方生成的挑戰(zhàn)向量求和,使用Dilihtium-G方案可以確保生成的挑戰(zhàn)向量和仍服從高斯分布,因而更適用于構(gòu)造門限簽名協(xié)議[11].在CRYSTALS-Dilithium方案和Aigis-sig方案中,挑戰(zhàn)向量服從均勻分布,因此,不同于上述方法,本文將擴展的Shamir秘密分享體制用于門限簽名協(xié)議設(shè)計中,使得挑戰(zhàn)向量的線性組合仍服從均勻分布.此外,由于Aigis-sig方案中使用的主要代數(shù)結(jié)構(gòu)為多項式環(huán)R=Z[X]/(XN+1),因此本文引入了基于多項式的Shamir門限秘密分享方案,并證明了秘密分享方案在不同的模約化操作下的正確性.本文基于Aigis-sig方案,利用全同態(tài)加密技術(shù)和秘密分享體制,設(shè)計了一個安全的(2,n)-門限簽名協(xié)議,分析結(jié)果表明該協(xié)議滿足正確性和可行性,在兩個參與者都是誠實的情況下,生成的門限數(shù)字簽名滿足適應(yīng)性選擇消息攻擊下的存在不可偽造性.當對協(xié)議交互信息進行承諾和零知識證明時,可實現(xiàn)惡意參與者存在時適應(yīng)性選擇消息攻擊下的存在不可偽造性.2基礎(chǔ)知識2.1Aigis-sig方案Aigis-sig方案[8]安全性基于非對稱模上帶錯誤學習(asymmetricmodulelearningwitherrors,AMLWE)問題和非對稱模上小整數(shù)解(asymmetricmodulesmallintegersolutions,AMSIS)問題的困難性[8].與格上其他同類方案相比,Aigis-sig方案能在確保安全性不變的前提下實現(xiàn)更好的綜合效率,特別是擁有更短的公鑰、私鑰和簽名長度.綜合考慮安全性、效率和構(gòu)造可行性等因素,本文選擇不帶公鑰壓縮的Aigis-sig方案構(gòu)造安全的門限簽名協(xié)議.Aigis-sig方案使用的代數(shù)結(jié)構(gòu)為多項式環(huán)R=Z[X]/(XN+1)及子環(huán)Rq=Zq[X]/(XN+1).環(huán)R上的加法和乘法運算定義如下:不帶公鑰壓縮的Aigis-sig方案包含3個算法:簽名驗證算法Aigis-sig.Verify(pk,M,σ):給定公鑰pk=(ρ,t),消息M和簽名σ=(z,c),首先計算A=Expand(ρ),μ=CRH(CRH(pk)||M),w′1=HighBitsq(Az-ct,2γ2).然后計算c′=H(μ,w′1).如果‖z‖∞＜γ1-β1且c′=c,接受簽名,否則拒絕簽名.算法1Aigis-sig方案Decompose算法r=rmod+qr0=rmod±αifr-r0=q-1thenr1=0;r0=r0-1;endelser1=r-r0αendreturn(r1,r0)由算法1可知,若(r1,r0)=Decomposeq(r,α),則有r1=HighBitsq(r,α),r0=LowBitsq(r,α).r,z∈Z,α為正整數(shù),α|(q-1).當上述算法被作用到多項式或多項式向量時,其含義是對應(yīng)操作被分別獨立地作用到多項式的每個系數(shù)上.Aigis-sig方案通過引理1來保證正確性:2.2同態(tài)加密方案同態(tài)加密是一類密碼學原語,它允許用戶在不解密的情況下對加密數(shù)據(jù)進行運算.Gentry在2009年構(gòu)造出了第一個全同態(tài)加密方案[13],隨后又出現(xiàn)了各種全同態(tài)加密優(yōu)化方案,如BFV[14]、Bra12[15]、BGV[16]、GSW[17]、FHEW[18]、CKKS[19]等.一般來說,一個全同態(tài)加密方案包含下列算法:密鑰生成算法HE.KeyGen(κ,L):輸入安全參數(shù)κ、層次參數(shù)L,運行密鑰生成算法,輸出公鑰pkHE,私鑰skHE和運算密鑰evkHE.加密算法EncpkHE(m):輸入公鑰pk和明文m,輸出密文ct.解密算法DecskHE(ct):輸入私鑰sk和密文ct,輸出明文m.密文同態(tài)加法運算EvalAddevkHE(ct1,ct2):輸入m1和m2的密文ct1和ct2,輸出m1+m2的密文ctadd.明密文同態(tài)乘法運算EvalMultConstevkHE(m1,ct2):輸入m1,m2的密文ct2,輸出密文ctmult_const,且DecskHE(ctmult_const)=m1·m2.密文同態(tài)運算HomEval(evkHE,f,ct1,···,ctl):使用同態(tài)運算密鑰evkHE,對函數(shù)f作用的一系列密文cti(i=1,···,l)進行算術(shù)運算,輸出密文ctf.函數(shù)f表示的是包含若干個加法或乘法的運算電路.在密態(tài)計算協(xié)議中間值時,除了進行上述同態(tài)基本運算外,部分中間值還需要進行同態(tài)密文比較運算.文獻[20]表明,基于CKKS方案的同態(tài)密文比較算法實現(xiàn)效率較高,因此在(2,n)-門限簽名的協(xié)議構(gòu)造中本文采用了CKKS同態(tài)加密方案.2.3Shamir秘密分享體制由命題1及文獻[22]中定理2知,基于多項式環(huán)且系數(shù)mod±p意義下(t,n)-Shamir門限方案是正確的.由基于多項式環(huán)的(t,n)-Shamir門限方案的機密性可知,任何少于t個參與者的集合都不能得到關(guān)于秘密的任何信息,因此敵手能得到秘密k∈Rp的概率是可忽略的.且有如下命題成立:命題2給定系統(tǒng)參數(shù),敵手至多可以破壞t-1個成員,那么敵手能得到秘密ss∈Rp的概率是可忽略的.2.4安全性定義數(shù)字簽名方案的安全性歸約實驗[8]定義如下:EXPERIMENT2.4.1:Expt-SignS,π(1κ)(1)(pk,sk)←KeyGen(1κ)(2)(M*,σ*)←SSignsk(·)(pk),其中簽名預言機的定義為:對詢問的消息M,生成簽名σ←Sign(sk,M),添加(M,σ)到集合Q中,然后返回(M,σ)作為回答.(3)該實驗輸出為1當且僅當有(M*,σ*)/∈Q且Verifypk(M*,σ*)=1.定義3如果對于任意概率多項式時間的敵手S均存在一個和κ有關(guān)的可忽略函數(shù)λ,使得下式成立:我們稱數(shù)字簽名方案π=(KeyGen,Sign,Verify)滿足在適應(yīng)性選擇消息攻擊下的強存在不可偽造性(strongexistentialunforgeabilityagainstadaptivechosen-messageattack,SUF-CMA).定義敵手優(yōu)勢為AdvSUF-CMAπ(S)=Pr[Expt-SignS,π(1κ)=1].如果敵手通過多項式次適應(yīng)性選擇消息的(2,n)-門限簽名查詢,能夠偽造出還沒被詢問消息的門限簽名,則Expt-ThreSignA,Π(1κ)=1,即敵手贏得了該實驗.(2,n)-門限簽名協(xié)議的安全性定義如下.定義4如果對于任意的概率多項式時間的敵手A,均存在一個和κ有關(guān)的可忽略函數(shù)λ′,使得下式成立:則稱基于數(shù)字簽名方案π設(shè)計的(2,n)-門限簽名協(xié)議Π滿足適應(yīng)性選擇消息攻擊下的存在不可偽造性(existentialunforgeabilityagainstadaptivechosen-messageattack,EUF-CMA).定義敵手優(yōu)勢為AdvΠ(A)=Pr[Expt-ThreSignA,Π(1κ)=1].3(2,n)-門限Aigis-sig簽名協(xié)議3.1簽名私鑰分享協(xié)議可信中心D隨機選擇ρ$←-{0,1}256,計算A=Expand(ρ)∈Rk×lq,(s1,s2)$←-Slη1×Skη2,計算t=As1+s2,并將公鑰(A,t)通過公開信道發(fā)送給驗證者.然后中心D通過(2,n)-門限方案產(chǎn)生簽名私鑰份額并通過保密信道分發(fā)份額.圖1簽名私鑰分享協(xié)議Figure1Secretsharingprotocol3.2門限簽名協(xié)議P1收到z2后計算z=(L1z1+L2z2)mod±p=y+cs1,并進行拒絕采樣條件的驗證:當拒絕采樣條件的驗證均通過時,P1和P2生成門限簽名(z,c),否則重新運行門限簽名協(xié)議.圖2給出了在門限簽名協(xié)議中，P1和P2的交互過程。圖2門限簽名協(xié)議Figure2Thresholdsigningprotocol4(2,n)-門限Aigis-sig簽名協(xié)議分析4.1正確性分析4.1.1向量y生成方法合理性4.1.2向量y的隨機性引理2設(shè)y1和y2是Zp上兩個相互獨立的隨機變量,且均服從Zp上均勻分布,k1,k2∈Z*p為定值,那么(k1y1+k2y2)mod±p服從Zp上均勻分布.證明:?z∈Zp,有證明:對y1和y2分量的每個系數(shù)應(yīng)用引理2即證.4.2門限簽名的正確性Aigis-sig方案中使用拒絕采樣技術(shù)[8],確保生成簽名值不泄露簽名私鑰信息.在引入(2,n)-Shamir門限方案后,參與者在生成門限簽名后進行拒絕采樣條件的驗證.4.3可行性分析在簽名份額的生成過程中,引入了全同態(tài)加密方案[19]后,一是可以密態(tài)實現(xiàn)非線性運算,同時確保簽名私鑰的安全性,二是與其他同態(tài)加密方案相比,CKKS方案支持較快地同態(tài)密文比較運算[20].首先,當w=Ay=A((L1y1+L2y2)mod±p)時,有Az-ct=w-cs2成立,簽名驗證算法接受門限簽名協(xié)議生成的簽名.在計算(L1y1+L2y2)mod±p時,由于(L1,L2)為公開參數(shù),為保證敵手和P2均不能在多項式時間內(nèi)求解隨機向量y1,P1計算ct1=Encpk1,HE(y1),將ct1發(fā)送給P2,P2收到ct1后只能密態(tài)計算(L1y1+L2y2)mod±p.此外,如果P2不計算ct5而直接將ct4發(fā)送給P1,雖然敵手不能在多項式時間內(nèi)求解w,但P1可以使用sk1,HE解出w,收到z2后,根據(jù)等式Az-ct=w-cs2計算簽名私鑰s2.P2計算ct5發(fā)送給P1,P1解出w1=Decsk1,HE(ct5)=HighBitsq(w,2γ2),P1此時只獲得w的高位比特信息,P1不能在多項式時間內(nèi)求解w,確保了簽名私鑰的安全性.4.4安全性分析本節(jié)基于Aigis-sig方案的安全性,基于多項式環(huán)的(t,n)-Shamir門限方案的安全性和CKKS同態(tài)加密方案的安全性來證明(2,n)-門限簽名協(xié)議的安全性.定理1假設(shè)Aigis-Sig方案滿足適應(yīng)性選擇消息攻擊下強存在不可偽造性[8],基于多項式環(huán)的(t,n)-Shamir門限方案是可證安全的,CKKS同態(tài)加密方案是可證明選擇明文攻擊安全[19],那么(2,n)-門限簽名協(xié)議滿足適應(yīng)性選擇消息攻擊下的存在不可偽造性.盡管協(xié)議的兩個參與者都是誠實的,敵手A不能控制任一參與者并參與到協(xié)議的交互過程中,但是敵手A可以擁有兩個參與者交互運行的視圖,也可以獲取協(xié)議運行中的公開信息,并進行多項式次適應(yīng)性選擇消息的門限簽名查詢.因此對于任意攻擊方案Π的敵手A如果能在實驗Expt-ThreSignA,Π(1κ)中以不可忽略的概率偽造出門限簽名,則可能的情況為:敵手在簽名私鑰分享協(xié)議中獲取了至少兩個參與者的秘密份額;敵手解出同態(tài)密文,并利用協(xié)議運行中的公開信息計算出簽名私鑰;敵手利用多項式次適應(yīng)性選擇消息的門限簽名查詢,并利用詢問結(jié)果偽造出Aigis-sig方案的合法簽名.則敵手A分別以不可忽略的優(yōu)勢攻破(2,n)-門限方案,同態(tài)加密方案或者偽造出合法的Aigis-sig簽名.這與本文的給出的安全性假設(shè)矛盾,因此,有下述公式成立:即敵手能偽造一個新消息的門限簽名概率是可忽略的.4.5門限簽名協(xié)議比較表1給出了不同的門限簽名協(xié)議在功能性、安全性等方面的比較.Boneh等人[10]基于門限全同態(tài)加密技術(shù)設(shè)計了一類通用的門限簽名構(gòu)造方法,利用該方法設(shè)計的門限簽名協(xié)議的安全性基于帶錯誤學習(learningwitherrors,LWE)問題的困難性.文獻[11]中門限簽名協(xié)議是基于Dilithium-G方案設(shè)計的,Dilithium-G方案是CRYSTALS-Dilithium的一個變體,它使用離散高斯采樣生成向量y.Dilithium-G方案安全性基于模上帶錯誤學習問題(modulelearningwi