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

趙秀鳳, 付 雨

信息工程大學(xué) 密碼工程學(xué)院, 鄭州 450001

1 引言

數(shù)字簽名是公鑰密碼體系的重要組成部分, 在電子商務(wù)、電子政務(wù)、加密貨幣等多個(gè)領(lǐng)域都發(fā)揮著重要作用. 在標(biāo)準(zhǔn)的數(shù)字簽名方案中, 簽名者使用私鑰對消息簽名, 驗(yàn)證者使用公鑰驗(yàn)證簽名的合法性. 近年來, 由于區(qū)塊鏈技術(shù)的快速發(fā)展, 門限簽名在該領(lǐng)域得到了深入研究與廣泛應(yīng)用. 其中一個(gè)主要原因是,在移動(dòng)互聯(lián)網(wǎng)應(yīng)用背景下, 部分移動(dòng)終端的防護(hù)能力較差, 簽名私鑰存儲(chǔ)的安全性很難得到有效保證. 在(t,n)-門限簽名協(xié)議中, 每個(gè)參與者擁有一個(gè)簽名私鑰份額, 簽名過程中任何不少于t個(gè)參與者的集合能夠利用各自私鑰份額生成簽名份額, 然后通過重構(gòu)簽名份額生成完整簽名. 簽名過程中單個(gè)參與者無法恢復(fù)完整的簽名私鑰, 既保證簽名的正確性, 又保證簽名私鑰的安全性, 驗(yàn)證過程可由單個(gè)參與者利用驗(yàn)證公鑰獨(dú)立完成. 門限簽名協(xié)議可以抵御單點(diǎn)腐化帶來的安全隱患, 具有更好的魯棒性.

目前, 國際上基于橢圓曲線數(shù)字簽名算法(elliptic curve digital signature algorithm, ECDSA) 已經(jīng)設(shè)計(jì)了兩方數(shù)字簽名協(xié)議[1]、門限數(shù)字簽名協(xié)議[2]. 國內(nèi)有學(xué)者對基于ECDSA 和國密算法SM2 的兩方協(xié)同生成數(shù)字簽名的方法進(jìn)行了研究[3,4]. ECDSA 和SM2 算法的安全性基于離散對數(shù)問題的困難性,因此均不能抵抗量子計(jì)算攻擊. 對于格上困難問題, 目前還沒有提出有效的量子求解算法, 所以研究如何設(shè)計(jì)安全高效的基于格的數(shù)字簽名方案的門限簽名協(xié)議十分必要.

FSwA (Fiat-Shamir with Aborts) 框架[5,6]是構(gòu)建基于格的數(shù)字簽名方案最流行的技術(shù)之一, 目前被廣泛應(yīng)用于基于格的數(shù)字簽名方案的設(shè)計(jì)中. 美國國家標(biāo)準(zhǔn)與技術(shù)研究所征集第三輪候選算法CRYSTALS-Dilithium[7]、國內(nèi)算法競賽獲獎(jiǎng)算法Aigis-sig[8]、木蘭[9]等都采用了該框架. 使用FSwA框架的數(shù)字簽名方案, 在簽名生成過程中需要進(jìn)行拒絕采樣條件的驗(yàn)證[6], 以確保簽名值不會(huì)泄露簽名私鑰信息. 但是拒絕采樣環(huán)節(jié)也是構(gòu)造門限簽名協(xié)議的主要障礙, 在協(xié)議交互過程中, 協(xié)議中間值需要保密, 即需要密態(tài)計(jì)算協(xié)議中間值, 因此本文擬引入全同態(tài)加密技術(shù)來解決此問題. Boneh 等人[10]基于門限全同態(tài)加密技術(shù)設(shè)計(jì)了一類通用的門限簽名協(xié)議構(gòu)造方法, 即先通過門限秘密分享體制生成簽名私鑰份額并分發(fā)給各參與者, 采用同態(tài)計(jì)算簽名電路的方法生成簽名份額, 再通過重構(gòu)算法生成簽名. 但是Boneh 等人[10]只在理論上給出了門限簽名協(xié)議的通用化構(gòu)造方法, 并未對協(xié)議中間值的保密及協(xié)議重復(fù)運(yùn)行次數(shù)等問題進(jìn)行充分討論. Damg?rd 等人[11]基于Dilithium-G[12]方案, 借助陷門同態(tài)承諾方案,設(shè)計(jì)了一個(gè)兩輪的(n,n)-門限簽名協(xié)議, 并證明了該協(xié)議滿足適應(yīng)性選擇消息攻擊下的存在不可偽造性.Dilithum-G 方案是CRYSTALS-Dilithium 方案的變體,兩個(gè)方案的主要區(qū)別在于拒絕采樣的實(shí)現(xiàn)方式不同. Dilithum-G 方案中挑戰(zhàn)向量服從高斯分布, 其和分布仍服從高斯分布. 在上述門限簽名協(xié)議中, 生成門限簽名一般需要對各參與方生成的挑戰(zhàn)向量求和, 使用Dilihtium-G 方案可以確保生成的挑戰(zhàn)向量和仍服從高斯分布, 因而更適用于構(gòu)造門限簽名協(xié)議[11]. 在CRYSTALS-Dilithium 方案和Aigis-sig 方案中,挑戰(zhàn)向量服從均勻分布, 因此, 不同于上述方法, 本文將擴(kuò)展的Shamir 秘密分享體制用于門限簽名協(xié)議設(shè)計(jì)中, 使得挑戰(zhàn)向量的線性組合仍服從均勻分布. 此外, 由于Aigis-sig 方案中使用的主要代數(shù)結(jié)構(gòu)為多項(xiàng)式環(huán)R= Z[X]/(XN+1), 因此本文引入了基于多項(xiàng)式的Shamir 門限秘密分享方案, 并證明了秘密分享方案在不同的模約化操作下的正確性. 本文基于Aigis-sig 方案, 利用全同態(tài)加密技術(shù)和秘密分享體制,設(shè)計(jì)了一個(gè)安全的(2,n)-門限簽名協(xié)議, 分析結(jié)果表明該協(xié)議滿足正確性和可行性, 在兩個(gè)參與者都是誠實(shí)的情況下, 生成的門限數(shù)字簽名滿足適應(yīng)性選擇消息攻擊下的存在不可偽造性. 當(dāng)對協(xié)議交互信息進(jìn)行承諾和零知識(shí)證明時(shí), 可實(shí)現(xiàn)惡意參與者存在時(shí)適應(yīng)性選擇消息攻擊下的存在不可偽造性.

2 基礎(chǔ)知識(shí)

2.1 Aigis-sig 方案

Aigis-sig 方案[8]安全性基于非對稱模上帶錯(cuò)誤學(xué)習(xí)(asymmetric module learning with errors,AMLWE) 問題和非對稱模上小整數(shù)解(asymmetric module small integer solutions, AMSIS) 問題的困難性[8]. 與格上其他同類方案相比, Aigis-sig 方案能在確保安全性不變的前提下實(shí)現(xiàn)更好的綜合效率,特別是擁有更短的公鑰、私鑰和簽名長度. 綜合考慮安全性、效率和構(gòu)造可行性等因素, 本文選擇不帶公鑰壓縮的Aigis-sig 方案構(gòu)造安全的門限簽名協(xié)議.

Aigis-sig 方案使用的代數(shù)結(jié)構(gòu)為多項(xiàng)式環(huán)R=Z[X]/(XN+1) 及子環(huán)Rq=Zq[X]/(XN+1). 環(huán)R上的加法和乘法運(yùn)算定義如下:

不帶公鑰壓縮的Aigis-sig 方案包含3 個(gè)算法:

簽名驗(yàn)證算法Aigis-sig.Verify(pk,M,σ): 給定公鑰pk=(ρ,t),消息M和簽名σ=(z,c),首先計(jì)算A= Expand(ρ),μ= CRH(CRH(pk)||M),w′1= HighBitsq(Az-ct,2γ2). 然后計(jì)算c′=H(μ,w′1).如果‖z‖∞＜γ1-β1且c′=c, 接受簽名, 否則拒絕簽名.

算法1 Aigis-sig 方案Decompose 算法r = r mod+q r0 = r mod±α if r-r0 = q-1 then r1 = 0;r0 = r0 -1;end else r1 = r-r0 α end return (r1,r0)

由算法1 可知, 若(r1,r0) = Decomposeq(r,α), 則有r1= HighBitsq(r,α),r0= LowBitsq(r,α).r,z ∈Z,α為正整數(shù),α|(q-1). 當(dāng)上述算法被作用到多項(xiàng)式或多項(xiàng)式向量時(shí), 其含義是對應(yīng)操作被分別獨(dú)立地作用到多項(xiàng)式的每個(gè)系數(shù)上.

Aigis-sig 方案通過引理1 來保證正確性:

2.2 同態(tài)加密方案

同態(tài)加密是一類密碼學(xué)原語, 它允許用戶在不解密的情況下對加密數(shù)據(jù)進(jìn)行運(yùn)算. Gentry 在2009年構(gòu)造出了第一個(gè)全同態(tài)加密方案[13], 隨后又出現(xiàn)了各種全同態(tài)加密優(yōu)化方案, 如BFV[14]、Bra12[15]、BGV[16]、GSW[17]、FHEW[18]、CKKS [19] 等.

一般來說, 一個(gè)全同態(tài)加密方案包含下列算法:

密鑰生成算法HE.KeyGen(κ,L): 輸入安全參數(shù)κ、層次參數(shù)L,運(yùn)行密鑰生成算法,輸出公鑰pkHE,私鑰skHE和運(yùn)算密鑰evkHE.

加密算法EncpkHE(m): 輸入公鑰pk 和明文m, 輸出密文ct.

解密算法DecskHE(ct): 輸入私鑰sk 和密文ct, 輸出明文m.

密文同態(tài)加法運(yùn)算EvalAddevkHE(ct1,ct2): 輸入m1和m2的密文ct1和ct2, 輸出m1+m2的密文ctadd.

明密文同態(tài)乘法運(yùn)算EvalMultConstevkHE(m1,ct2): 輸入m1,m2的密文ct2,輸出密文ctmult_const,且DecskHE(ctmult_const)=m1·m2.

密文同態(tài)運(yùn)算HomEval(evkHE,f,ct1,··· ,ctl): 使用同態(tài)運(yùn)算密鑰evkHE, 對函數(shù)f作用的一系列密文cti(i=1,··· ,l) 進(jìn)行算術(shù)運(yùn)算, 輸出密文ctf. 函數(shù)f表示的是包含若干個(gè)加法或乘法的運(yùn)算電路.

在密態(tài)計(jì)算協(xié)議中間值時(shí), 除了進(jìn)行上述同態(tài)基本運(yùn)算外, 部分中間值還需要進(jìn)行同態(tài)密文比較運(yùn)算.文獻(xiàn)[20] 表明, 基于CKKS 方案的同態(tài)密文比較算法實(shí)現(xiàn)效率較高, 因此在(2,n)-門限簽名的協(xié)議構(gòu)造中本文采用了CKKS 同態(tài)加密方案.

2.3 Shamir 秘密分享體制

由命題1 及文獻(xiàn)[22] 中定理2 知, 基于多項(xiàng)式環(huán)且系數(shù)mod±p意義下(t,n)-Shamir 門限方案是正確的.

由基于多項(xiàng)式環(huán)的(t,n)-Shamir 門限方案的機(jī)密性可知, 任何少于t個(gè)參與者的集合都不能得到關(guān)于秘密的任何信息, 因此敵手能得到秘密k ∈Rp的概率是可忽略的. 且有如下命題成立:

命題2 給定系統(tǒng)參數(shù), 敵手至多可以破壞t-1 個(gè)成員, 那么敵手能得到秘密ss∈Rp的概率是可忽略的.

2.4 安全性定義

數(shù)字簽名方案的安全性歸約實(shí)驗(yàn)[8]定義如下:

EXPERIMENT 2.4.1: Expt-SignS,π(1κ)

(1) (pk,sk)←KeyGen(1κ)

(2) (M*,σ*)← SSignsk(·)(pk), 其中簽名預(yù)言機(jī)的定義為: 對詢問的消息M, 生成簽名σ ←Sign(sk,M), 添加(M,σ) 到集合Q中, 然后返回(M,σ) 作為回答.

(3) 該實(shí)驗(yàn)輸出為1 當(dāng)且僅當(dāng)有(M*,σ*) /∈Q且Verifypk(M*,σ*)=1.

定義3 如果對于任意概率多項(xiàng)式時(shí)間的敵手S均存在一個(gè)和κ有關(guān)的可忽略函數(shù)λ, 使得下式成立:

我們稱數(shù)字簽名方案π=(KeyGen,Sign,Verify) 滿足在適應(yīng)性選擇消息攻擊下的強(qiáng)存在不可偽造性(strong existential unforgeability against adaptive chosen-message attack, SUF-CMA). 定義敵手優(yōu)勢為AdvSUF-CMAπ(S)=Pr[Expt-SignS,π(1κ)=1].

如果敵手通過多項(xiàng)式次適應(yīng)性選擇消息的(2,n)-門限簽名查詢, 能夠偽造出還沒被詢問消息的門限簽名, 則Expt-ThreSignA,Π(1κ)=1, 即敵手贏得了該實(shí)驗(yàn). (2,n)-門限簽名協(xié)議的安全性定義如下.

定義4如果對于任意的概率多項(xiàng)式時(shí)間的敵手A, 均存在一個(gè)和κ有關(guān)的可忽略函數(shù)λ′, 使得下式成立:

則稱基于數(shù)字簽名方案π設(shè)計(jì)的(2,n)-門限簽名協(xié)議Π 滿足適應(yīng)性選擇消息攻擊下的存在不可偽造性(existential unforgeability against adaptive chosen-message attack, EUF-CMA). 定義敵手優(yōu)勢為AdvΠ(A)=Pr[Expt-ThreSignA,Π(1κ)=1].

3 (2, n)-門限Aigis-sig 簽名協(xié)議

3.1 簽名私鑰分享協(xié)議

可信中心D 隨機(jī)選擇ρ$←-{0,1}256, 計(jì)算A= Expand(ρ)∈Rk×lq, (s1,s2)$←-Slη1×Skη2, 計(jì)算t=As1+s2, 并將公鑰(A,t) 通過公開信道發(fā)送給驗(yàn)證者. 然后中心D 通過(2,n)-門限方案產(chǎn)生簽名私鑰份額并通過保密信道分發(fā)份額.

圖1 簽名私鑰分享協(xié)議Figure 1 Secret sharing protocol

3.2 門限簽名協(xié)議

P1收到z2后計(jì)算z=(L1z1+L2z2)mod±p=y+cs1, 并進(jìn)行拒絕采樣條件的驗(yàn)證:

當(dāng)拒絕采樣條件的驗(yàn)證均通過時(shí),P1和P2生成門限簽名(z,c), 否則重新運(yùn)行門限簽名協(xié)議. 圖2 給出了在門限簽名協(xié)議中，P1和P2的交互過程。

圖2 門限簽名協(xié)議Figure 2 Threshold signing protocol

4 (2, n)-門限Aigis-sig 簽名協(xié)議分析

4.1 正確性分析

4.1.1 向量y生成方法合理性

4.1.2 向量y的隨機(jī)性

引理2 設(shè)y1和y2是Zp上兩個(gè)相互獨(dú)立的隨機(jī)變量, 且均服從Zp上均勻分布,k1,k2∈Z*p為定值, 那么(k1y1+k2y2)mod±p服從Zp上均勻分布.

證明:?z ∈Zp, 有

證明: 對y1和y2分量的每個(gè)系數(shù)應(yīng)用引理2 即證.

4.2 門限簽名的正確性

Aigis-sig 方案中使用拒絕采樣技術(shù)[8], 確保生成簽名值不泄露簽名私鑰信息. 在引入(2,n)-Shamir門限方案后, 參與者在生成門限簽名后進(jìn)行拒絕采樣條件的驗(yàn)證.

4.3 可行性分析

在簽名份額的生成過程中, 引入了全同態(tài)加密方案[19]后, 一是可以密態(tài)實(shí)現(xiàn)非線性運(yùn)算, 同時(shí)確保簽名私鑰的安全性, 二是與其他同態(tài)加密方案相比, CKKS 方案支持較快地同態(tài)密文比較運(yùn)算[20].

首先, 當(dāng)w=Ay=A((L1y1+L2y2)mod±p)時(shí), 有Az-ct=w-cs2成立, 簽名驗(yàn)證算法接受門限簽名協(xié)議生成的簽名. 在計(jì)算(L1y1+L2y2)mod±p時(shí), 由于(L1,L2) 為公開參數(shù), 為保證敵手和P2均不能在多項(xiàng)式時(shí)間內(nèi)求解隨機(jī)向量y1,P1計(jì)算ct1=Encpk1,HE(y1), 將ct1發(fā)送給P2,P2收到ct1后只能密態(tài)計(jì)算(L1y1+L2y2)mod±p. 此外, 如果P2不計(jì)算ct5而直接將ct4發(fā)送給P1, 雖然敵手不能在多項(xiàng)式時(shí)間內(nèi)求解w, 但P1可以使用sk1,HE解出w, 收到z2后, 根據(jù)等式Az-ct=w-cs2計(jì)算簽名私鑰s2.P2計(jì)算ct5發(fā)送給P1,P1解出w1= Decsk1,HE(ct5) = HighBitsq(w,2γ2),P1此時(shí)只獲得w的高位比特信息,P1不能在多項(xiàng)式時(shí)間內(nèi)求解w, 確保了簽名私鑰的安全性.

4.4 安全性分析

本節(jié)基于Aigis-sig 方案的安全性, 基于多項(xiàng)式環(huán)的(t,n)-Shamir 門限方案的安全性和CKKS 同態(tài)加密方案的安全性來證明(2,n)-門限簽名協(xié)議的安全性.

定理1 假設(shè)Aigis-Sig 方案滿足適應(yīng)性選擇消息攻擊下強(qiáng)存在不可偽造性[8], 基于多項(xiàng)式環(huán)的(t,n)-Shamir 門限方案是可證安全的, CKKS 同態(tài)加密方案是可證明選擇明文攻擊安全[19], 那么(2,n)-門限簽名協(xié)議滿足適應(yīng)性選擇消息攻擊下的存在不可偽造性.

盡管協(xié)議的兩個(gè)參與者都是誠實(shí)的, 敵手A不能控制任一參與者并參與到協(xié)議的交互過程中, 但是敵手A可以擁有兩個(gè)參與者交互運(yùn)行的視圖, 也可以獲取協(xié)議運(yùn)行中的公開信息, 并進(jìn)行多項(xiàng)式次適應(yīng)性選擇消息的門限簽名查詢. 因此對于任意攻擊方案Π 的敵手A如果能在實(shí)驗(yàn)Expt-ThreSignA,Π(1κ) 中以不可忽略的概率偽造出門限簽名, 則可能的情況為: 敵手在簽名私鑰分享協(xié)議中獲取了至少兩個(gè)參與者的秘密份額; 敵手解出同態(tài)密文, 并利用協(xié)議運(yùn)行中的公開信息計(jì)算出簽名私鑰; 敵手利用多項(xiàng)式次適應(yīng)性選擇消息的門限簽名查詢, 并利用詢問結(jié)果偽造出Aigis-sig 方案的合法簽名. 則敵手A分別以不可忽略的優(yōu)勢攻破(2,n)-門限方案, 同態(tài)加密方案或者偽造出合法的Aigis-sig 簽名. 這與本文的給出的安全性假設(shè)矛盾, 因此, 有下述公式成立:

即敵手能偽造一個(gè)新消息的門限簽名概率是可忽略的.

4.5 門限簽名協(xié)議比較

表1 給出了不同的門限簽名協(xié)議在功能性、安全性等方面的比較. Boneh 等人[10]基于門限全同態(tài)加密技術(shù)設(shè)計(jì)了一類通用的門限簽名構(gòu)造方法, 利用該方法設(shè)計(jì)的門限簽名協(xié)議的安全性基于帶錯(cuò)誤學(xué)習(xí)(learning with errors, LWE) 問題的困難性. 文獻(xiàn)[11] 中門限簽名協(xié)議是基于Dilithium-G 方案設(shè)計(jì)的,Dilithium-G 方案是CRYSTALS-Dilithium 的一個(gè)變體, 它使用離散高斯采樣生成向量y. Dilithium-G 方案安全性基于模上帶錯(cuò)誤學(xué)習(xí)問題(module learning with errors, MLWE) 問題和模上小整數(shù)解(module small integer solutions, MSIS) 問題的困難性. 根據(jù)文獻(xiàn)[11] 中定理1, 在陷門同態(tài)承諾方案是安全的前提下, 協(xié)議的安全性與MLWE 和MSIS 問題的困難性相關(guān).

表1 門限簽名協(xié)議比較Table 1 Comparison to threshold signature protocols

由于上述協(xié)議均未給出參考實(shí)現(xiàn)結(jié)果, 因而目前無法給出詳細(xì)的實(shí)現(xiàn)效率比較, 在下一步的研究中,我們將嘗試給出門限Aigis-sig 協(xié)議的參考實(shí)現(xiàn)和詳細(xì)的協(xié)議實(shí)現(xiàn)效率比較.

本文給出的(2,n)-門限簽名協(xié)議可以擴(kuò)展到(t,n)-門限簽名協(xié)議(2≤t ＜n). 在簽名私鑰分享協(xié)議中, 簽名私鑰被分割成n個(gè)秘密份額{xu,(ss1,u,ss2,u)}(1≤u ≤n), 任意t個(gè)參與者可以通過拉格朗日插值公式重構(gòu)簽名私鑰:

5 結(jié)論

本文基于Aigis-sig 方案給出了一個(gè)后量子安全的(2,n)-門限簽名協(xié)議. 該協(xié)議包含簽名私鑰分享協(xié)議和門限簽名協(xié)議, 借助(t,n)-Shamir 門限方案和同態(tài)加密方案, 實(shí)現(xiàn)了分布式簽名過程. 協(xié)議滿足正確性和不可偽造性, 當(dāng)協(xié)議交互信息進(jìn)行承諾和零知識(shí)證明時(shí), 可實(shí)現(xiàn)惡意參與者存在時(shí)適應(yīng)性選擇消息攻擊下的存在不可偽造性. 本文給出的(2,n)-門限簽名協(xié)議具有較好的擴(kuò)展性, 可以擴(kuò)展到(t,n)-門限簽名協(xié)(2≤t ＜n), 并且門限數(shù)字簽名的簽名規(guī)模和生成簽名的概率與Aigis-sig 方案基本一致. 然而由于引入全同態(tài)加密技術(shù), 增加了協(xié)議運(yùn)行過程中計(jì)算復(fù)雜度, 如何優(yōu)化方案效率, 是下一步研究工作的重點(diǎn).