石少全王鳳和
(1.山東建筑大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,山東 濟(jì)南250101;2.山東建筑大學(xué) 理學(xué)院,山東 濟(jì)南250101)
近些年,以比特幣為代表的區(qū)塊鏈技術(shù)受到工業(yè)界和學(xué)術(shù)界的持續(xù)關(guān)注[1]。 2019 年6 月,臉書Facebook 發(fā)布了基于區(qū)塊鏈技術(shù)的數(shù)字貨幣項(xiàng)目Libra。 區(qū)塊鏈技術(shù)在學(xué)術(shù)界也逐漸成為熱點(diǎn)研究課題[2-4]。 區(qū)塊鏈?zhǔn)褂梅植际酱鎯?chǔ)、密碼學(xué)、點(diǎn)對(duì)點(diǎn)(Peer to Peer,P2P)網(wǎng)絡(luò)和共識(shí)機(jī)制等技術(shù)實(shí)現(xiàn)分布式賬本的不可篡改和不可偽造,其去中心化和不可篡改等特點(diǎn)使得區(qū)塊鏈在數(shù)字貨幣、支付、審計(jì)和信用體系建設(shè)等金融領(lǐng)域得到廣泛應(yīng)用,并逐漸滲透到物聯(lián)網(wǎng)和供應(yīng)鏈等多個(gè)領(lǐng)域[5-7]。 然而,區(qū)塊鏈在展現(xiàn)出蓬勃生命力的同時(shí),也面臨著安全和隱私方面的嚴(yán)峻挑戰(zhàn)[8],如區(qū)塊鏈交易中須通過認(rèn)證機(jī)制來保障用戶的資金安全。
數(shù)字簽名用于確保數(shù)字貨幣的所有權(quán)及區(qū)塊鏈交易的不可偽造性和不可否認(rèn)性[9]。 在區(qū)塊鏈交易認(rèn)證中,用戶公鑰或公鑰的哈希值作為區(qū)分用戶的唯一標(biāo)識(shí),可作為交易地址使用。 而用戶的私鑰則作為數(shù)字貨幣所有權(quán)的唯一標(biāo)識(shí)。 通常密鑰對(duì)(公私鑰對(duì))存儲(chǔ)于用戶的區(qū)塊鏈錢包。 為增強(qiáng)匿名性,提倡每次交易使用不同的交易地址。 因此,用戶需存儲(chǔ)不同的密鑰對(duì),這便增加了用戶錢包的存儲(chǔ)開銷。 不僅如此,由于密鑰對(duì)是一串無規(guī)律的字符串,密鑰對(duì)的增加也給用戶帶來密鑰管理不便的問題。 分層確定性錢包為此問題提供了一種可能的解決手段,其優(yōu)點(diǎn)在于只需備份主密鑰,降低了錢包存儲(chǔ)開銷的同時(shí)提升了密鑰管理效率[10]。
橢圓曲線數(shù)字簽名算法(Elliptic Curve Digital Signature Algorithm,ECDSA)已廣泛應(yīng)用于區(qū)塊鏈交易認(rèn)證中。 該算法具有計(jì)算效率高、密鑰和簽名尺寸小等優(yōu)點(diǎn),并可為分層確定性錢包設(shè)計(jì)與使用提供強(qiáng)有力的技術(shù)支撐。 然而,以離散對(duì)數(shù)為代表的傳統(tǒng)困難假設(shè)無法保證量子環(huán)境下的困難性[11],使得ECDSA 等算法不具備量子安全性。 因此,設(shè)計(jì)具備后量子安全的交易認(rèn)證方案成為區(qū)塊鏈安全領(lǐng)域一個(gè)有意義的研究方向。 格密碼體制作為后量子密碼的重要備選之一,近些年取得豐碩成果。 與基于橢圓曲線等密碼體制設(shè)計(jì)的交易認(rèn)證方案[12]比較,基于格工具設(shè)計(jì)的區(qū)塊鏈交易認(rèn)證方案可為區(qū)塊鏈提供量子安全性。 YIN 等[13]提出一種后量子區(qū)塊鏈交易認(rèn)證方案,將陷門生成算法和格基代理算法分別用于產(chǎn)生種子密鑰和子密鑰,從而實(shí)現(xiàn)分層確定性錢包設(shè)計(jì)。 LI 等[14]基于格工具設(shè)計(jì)了一種新的數(shù)字簽名方案,并基于該數(shù)字簽名方案提出一種后量子區(qū)塊鏈交易認(rèn)證方案。 然而,上述方案存在用戶區(qū)塊鏈錢包較臃腫的缺點(diǎn)。 分析發(fā)現(xiàn),格基代理算法[15]是導(dǎo)致區(qū)塊鏈錢包臃腫的重要原因。 事實(shí)上,格基代理算法產(chǎn)生的子密鑰的尺寸相較于種子密鑰的尺寸存在較大擴(kuò)展,因而增加了用戶區(qū)塊鏈錢包的存儲(chǔ)開銷。
實(shí)現(xiàn)量子安全性和區(qū)塊鏈錢包空間尺寸壓縮是區(qū)塊鏈安全領(lǐng)域有意義的研究方向。 為此,文章基于格工具提出一種適用于分層確定性錢包的區(qū)塊鏈交易認(rèn)證方案。 具體地,以AGRAWAL 等[16]提出的固定維數(shù)格基代理算法為工具生成子密鑰對(duì),以期確保子密鑰對(duì)的尺寸與種子密鑰一致,達(dá)到縮減區(qū)塊鏈錢包存儲(chǔ)開銷的目的。
區(qū)塊鏈通過區(qū)塊和鏈?zhǔn)浇Y(jié)構(gòu)來存儲(chǔ)數(shù)據(jù)。 以比特幣[1]為例,區(qū)塊鏈系統(tǒng)的區(qū)塊結(jié)構(gòu)如圖1 所示。
圖1 比特幣中的區(qū)塊結(jié)構(gòu)圖
由圖1 可知,每個(gè)區(qū)塊由區(qū)塊頭和區(qū)塊體組成。其中,區(qū)塊頭通過存儲(chǔ)上一區(qū)塊的哈希值(哈希值為密碼學(xué)中安全的哈希函數(shù)的哈希值)與上一區(qū)塊相連,從而形成鏈?zhǔn)浇Y(jié)構(gòu)。 而區(qū)塊體則用于存儲(chǔ)具體交易信息。 每筆交易都包含交易發(fā)送方的數(shù)字簽名,確保數(shù)據(jù)未被偽造且不可篡改。 已完成的交易永久存儲(chǔ)于區(qū)塊體中供所有用戶查詢。
區(qū)塊鏈交易認(rèn)證過程如圖2 所示。 由圖2 可知,在交易1 中,區(qū)塊鏈用戶Alice 的公鑰(接收地址)收到來自用戶Eve 的一筆轉(zhuǎn)賬。 在交易2 中,Alice 將來自用戶Eve 的資金與Bob 產(chǎn)生交易。 具體地,Alice 利用其私鑰簽名交易2。 區(qū)塊鏈所有合法節(jié)點(diǎn)可利用Alice 的公鑰等信息驗(yàn)證交易2 合法性,同時(shí)檢測(cè)Alice 是否為雙花。 若簽名合法且無雙花,則區(qū)塊鏈節(jié)點(diǎn)認(rèn)為交易合法,最終該筆交易將被寫入?yún)^(qū)塊鏈中。
圖2 區(qū)塊鏈交易認(rèn)證過程圖
區(qū)塊鏈系統(tǒng)中,用戶的密鑰對(duì)通常存儲(chǔ)于用戶的區(qū)塊鏈錢包中。 分層確定性錢包通過種子密鑰生成多個(gè)子密鑰對(duì),在交易后,無需備份新增公鑰(交易地址)對(duì)應(yīng)的私鑰,僅備份主私鑰等信息即可。因此,分層確定性錢包可以降低用戶區(qū)塊鏈錢包的存儲(chǔ)開銷,并提升用戶管理密鑰的效率,可為用戶密鑰的高效管理提供解決手段。
假設(shè)交易發(fā)送方為Alice,交易接收方為Bob,適用于分層確定性錢包的區(qū)塊鏈交易認(rèn)證方案構(gòu)建過程如下:
(1) 系統(tǒng)建立 區(qū)塊鏈用戶Alice 輸入安全參數(shù)n,輸出主公鑰和主私鑰作為區(qū)塊鏈錢包的種子密鑰。
(2) 子密鑰對(duì)生成 當(dāng)Alice 有交易需求時(shí),通過分層確定性錢包中的種子密鑰產(chǎn)生用于交易認(rèn)證的子密鑰對(duì)(pAlice,sAlice)。
(3) 交易簽名 假設(shè)pAlice已經(jīng)在某筆交易中作為接收地址(文章中直接將公鑰作為交易地址),即該交易地址中有資金,可進(jìn)行轉(zhuǎn)賬操作。 Alice 利用自己的私鑰sAlice對(duì)轉(zhuǎn)賬交易μ=(tx,pBob)簽名,其中tx為交易信息;pBob為接收地址。 Alice 還將該筆轉(zhuǎn)賬交易通過P2P 網(wǎng)絡(luò)廣播至全網(wǎng)節(jié)點(diǎn)。
(4) 交易驗(yàn)證 區(qū)塊鏈節(jié)點(diǎn)接收到Alice 的轉(zhuǎn)賬交易后,利用pAlice等公共信息對(duì)交易的簽名進(jìn)行驗(yàn)證。 若簽名通過驗(yàn)證且無雙花,則區(qū)塊鏈節(jié)點(diǎn)將該筆交易存儲(chǔ)于新區(qū)塊中。
(5) 交易寫入?yún)^(qū)塊鏈 每個(gè)區(qū)塊鏈節(jié)點(diǎn)基于自身計(jì)算能力在區(qū)塊中找到一個(gè)具有足夠難度的工作量證明,成功找到難度值的節(jié)點(diǎn)獲得記賬權(quán),并向全網(wǎng)廣播其所存儲(chǔ)的新區(qū)塊。 其他節(jié)點(diǎn)進(jìn)行該區(qū)塊的合法性驗(yàn)證,若通過驗(yàn)證,則將該區(qū)塊寫入?yún)^(qū)塊鏈。此時(shí),發(fā)送方地址pAlice中的資金被成功轉(zhuǎn)入接收方地址pBob中,交易成功。
1.3.1 符號(hào)約定
? 和? 分別為實(shí)數(shù)域和整數(shù)域;為矩陣T的列向量施密特正交化后得到的矩陣;‖‖為歐幾里得范數(shù);poly(n)為非確定的多項(xiàng)式函數(shù)f(n)=O(nd),其中d 為常數(shù)。
1.3.2 格定義
格Λ 由式(1)表示為
式中vi為?n上一組線性無關(guān)的向量,i =1,2,…,n;向量組v1,v2,…,vn構(gòu)成格的一組基。
密碼學(xué)中常用的兩類q模格分別由式(2) 和(3) 表示為
式中A為矩陣,;x為向量,x∈?m;u為向量,為正整數(shù)。
1.3.3 格上高斯分布
高斯函數(shù)ρs,c(x) 由式(4) 表示為
式中s為實(shí)數(shù),s >0;c為中心向量,c∈?n;x為向量,x∈?n。
格上高斯分布DΛ,s,c(x) 由式(5) 表示為
事實(shí)上,格上高斯分布DΛ,s,c(x) 可以看作按照在以向量c為中心、參數(shù)為s的高斯分布中抽取格Λ中向量的條件分布。
1.3.4 格上困難問題
小整數(shù)解問題(Small Integer Solution,SIS)定義參數(shù)為(q,m,β) 的SIS 問題為給定n和一個(gè)均勻隨機(jī)的矩陣,尋找一個(gè)非零向量e,其滿足的關(guān)系可由式(6) 表示為
通常認(rèn)為求解小整數(shù)解問題是困難的,即如果對(duì)恰當(dāng)選取的參數(shù)(q,m,β),在不知陷門的情況下,任意多項(xiàng)式時(shí)間敵手成功破解SIS 問題的概率是可忽略的。
1.3.5 格上相關(guān)引理
引理1[17]設(shè)一個(gè)n維格,ηε(Λ) 為光滑參數(shù),則服從格上高斯分布的向量x滿足的關(guān)系由式(7)表示為
式中P為概率,s≥ηε(Λ);ε為實(shí)數(shù),ε∈(0,1);x~DΛ,s,c為x服從格上高斯分布DΛ,s,c。
引理2(陷門生成算法)[17]存在一個(gè)概率多項(xiàng)式時(shí)間算法TrapGen(1n),令q >3、m =O(nlbq),輸入安全參數(shù)n,該算法輸出一個(gè)統(tǒng)計(jì)接近均勻的矩陣及其格(A)的陷門基TA∈?m×m,滿足
引理3(原像抽樣算法)[17]存在一個(gè)概率多項(xiàng)式時(shí)間算法SamplePre(A,TA,s,u), 以矩陣A∈、格的陷門基TA∈?m×m、高斯參數(shù)s≥為輸入,該算法輸出一個(gè)向量e,滿足統(tǒng)計(jì)接近DΛuq(A),s,c,由引理1 可知,原像抽樣算法SamplePre 所抽取的對(duì)應(yīng)于向量的一個(gè)原像e將以壓倒性的概率滿足
引理4(固定維數(shù)格基代理算法)[16]存在一個(gè)概率多項(xiàng)式時(shí)間算法BasisDel(A,R,TA,s),以矩陣可逆矩陣R∈?m×m(如果矩陣R∈?m×m作為中的矩陣是可逆的,則稱R是?q的可逆矩陣)、格Λ⊥q(A) 的陷門基TA和參數(shù)s >為輸入,該算法輸出格的一個(gè)陷門基TB∈?m×m,滿足
假設(shè)交易發(fā)送方為Alice,交易接收方為Bob。n為安全參數(shù),m、q、β、s1、s2均為n的函數(shù)。 文章設(shè)計(jì)的后量子區(qū)塊鏈交易認(rèn)證方案為
(1) 系統(tǒng)建立 發(fā)送方Alice 輸入安全參數(shù)n,調(diào)用TrapGen 算法,生成一個(gè)統(tǒng)計(jì)接近均勻的矩陣主公鑰及其格(A)對(duì)應(yīng)的陷門基主私鑰TA,Alice 將其存儲(chǔ)在區(qū)塊鏈錢包中作為種子密鑰。
(2) 子密鑰對(duì)生成 Alice 隨機(jī)選擇1 個(gè)?q可逆矩 陣R∈?m×m并 調(diào) 用 算 法BasisDel 得 到TB←BasisDel(A,TA,R,s1),其中B =AR-1。 則pAlice=B,sAlice=TB。
(3) 交易簽名 假設(shè)pAlice已經(jīng)在某筆交易中作為接收地址,即該交易地址中有資金,可進(jìn)行轉(zhuǎn)賬操作。 Alice 隨機(jī)選擇k個(gè)均勻矩陣C1,C2,…,Ck∈,并公開公共參數(shù)PP =〈B,C1,C2,…,Ck〉。 設(shè)Alice 與Bob 之間的轉(zhuǎn)賬交易為μ =(tx,pBob) ∈{0,1}k。 Alice 按照如下方式進(jìn)行該筆轉(zhuǎn)賬交易的簽名:
①Alice 根據(jù)μi的取值決定是否選擇矩陣Ci,若μi =1,則選擇相應(yīng)的矩陣Ci,否則不選相應(yīng)的矩陣Ci。 設(shè)通過以上原則Alice 一共選擇了j個(gè)矩陣Ck1,Ck2,…,Ckj,將這j個(gè)矩陣進(jìn)行依次級(jí)聯(lián)得到一個(gè)新的矩陣Cμ =B |Ck1|…|Ckj;
②Alice 選 擇j個(gè) 小 向 量vk1,vk2,…,vkj, 且計(jì)算
③ Alice 由 原 像 抽 樣 算 法 得 到vk0, 即令向量v為j +1 個(gè)向量依次級(jí)聯(lián)得到的向量,則Alice 對(duì)于交易μ的簽名為v。 Alice 將該筆轉(zhuǎn)賬交易通過P2P 網(wǎng)絡(luò)廣播至全網(wǎng)節(jié)點(diǎn)。
(4) 交易驗(yàn)證 區(qū)塊鏈節(jié)點(diǎn)按如下方式驗(yàn)證Alice 簽名的合法性:
①區(qū)塊鏈節(jié)點(diǎn)根據(jù)μi的取值決定是否選擇矩陣Ci,若μi =1,則選擇相應(yīng)的矩陣Ci,否則不選相應(yīng)的矩陣Ci。 設(shè)通過以上原則區(qū)塊鏈節(jié)點(diǎn)一共選擇了j個(gè)矩陣Ck1,Ck2,…,Ckj,將這j個(gè)矩陣進(jìn)行依次級(jí)聯(lián)得到矩陣Cμ =B |Ck1|…|Ckj;
②區(qū)塊鏈節(jié)點(diǎn)驗(yàn)證Cμv =0(modq),v≠0,是否成立,若成立,且該交易中的資金未被花費(fèi),則區(qū)塊鏈節(jié)點(diǎn)認(rèn)為交易合法,并將該交易存儲(chǔ)進(jìn)新區(qū)塊。
(5) 交易寫入?yún)^(qū)塊鏈 每個(gè)節(jié)點(diǎn)基于自身計(jì)算能力在區(qū)塊中找到一個(gè)具有足夠難度的工作量證明,成功找到難度值的節(jié)點(diǎn)獲得記賬權(quán),并向全網(wǎng)廣播其所存儲(chǔ)的新區(qū)塊。 其他節(jié)點(diǎn)進(jìn)行該區(qū)塊的合法性驗(yàn)證,若通過驗(yàn)證,則將該區(qū)塊寫入?yún)^(qū)塊鏈。 此時(shí)Alice 的轉(zhuǎn)賬交易成功寫入?yún)^(qū)塊鏈。 即發(fā)送方地址pAlice中的資金被成功轉(zhuǎn)入接收方地址pBob中,交易成功。
2.2.1 正確性分析
為實(shí)現(xiàn)方案的完備性, 需要TrapGen 算法、BasisDel 算法和SamplePre 算法正常運(yùn)行。 為此,方案參數(shù)設(shè)置如下mω(lb2m) 。 AGRAWAL 等[16]和GENTRY 等[17]已驗(yàn)證在上述參數(shù)下TrapGen 算法、BasisDel 算法和SamplePre 算法能夠確保正常運(yùn)行。 因此,方案中系統(tǒng)建立、子密鑰對(duì)生成、交易簽名和交易驗(yàn)證可正常執(zhí)行。
由BasisDel 算法的正確性可知,每個(gè)合法的用戶擁有格及其相應(yīng)的陷門,故由簽名過程可知,向量vk0是SamplePre 算法的輸出,從而vk0滿足的等式由式(8)表示為
進(jìn)而可得v滿足的等式由式(9) 表示為
故證明該方案是正確的。
2.2.2 存在不可偽造性分析
不失一般性,假設(shè)待敵手簽名詢問的Q個(gè)交易的值 分 別 為:μ(1),μ(2),…,μ(Q)。 設(shè)p不 為μ(1),μ(2),…,μ(Q)中任何前綴的最小字符串,G為p組成的集合,即p∈G。 由文獻(xiàn)[15]可知,集合G可以在多項(xiàng)式時(shí)間內(nèi)計(jì)算得到,且集合G中最多有kQ個(gè)元素。 挑戰(zhàn)者在集合G中任意選擇一個(gè)p,令t為字符串p的漢明重量,pi表示字符串p的第i個(gè)位置的取值,挑戰(zhàn)者按如下方式生成公共參數(shù):
(1) 當(dāng)i≤| p |, 且pi =0 時(shí), 挑戰(zhàn)者調(diào)用TrapGen 算法得到一組矩陣及對(duì)應(yīng)格的陷門Ti;
(2) 當(dāng)i≤|p |,且pi =1 時(shí),令
(3) 當(dāng)i >|p |時(shí),令
挑戰(zhàn)者將公共參數(shù)(B,Ci) 發(fā)送給敵手,同時(shí)挑戰(zhàn)者在本地建立列表L 用于記錄對(duì)交易簽名的回答。
簽名詢問 當(dāng)敵手進(jìn)行關(guān)于交易μ(i)的簽名詢問時(shí),挑戰(zhàn)者首先查詢列表L 中是否有μ(i)的簽名,若有,則返回列表L 中的相應(yīng)的簽名vi給敵手;否則,因?yàn)閜不是任何μ(1),μ(2),…,μ(Q)的前綴,從而在μ(i)的前p個(gè)位置中還存在1 的概率為1-。 設(shè) 該 位 置 為i′, 而 此 時(shí) 挑 戰(zhàn) 者 擁 有Λ⊥(Ci′) 對(duì)應(yīng)的陷門Ti′,因此挑戰(zhàn)者可以利用陷門為μ(i)生成對(duì)應(yīng)的簽名vi,簽名生成過程與方案描述中的簽名過程類似,挑戰(zhàn)者將生成的簽名vi發(fā)送給敵手,并將(μ(i),vi) 存儲(chǔ)在列表L 中。
偽造 在敵手完成Q次簽名詢問并感到滿意后,敵手以ε的概率輸出一個(gè)消息μ*偽造的簽名v*,且v*滿足的關(guān)系可由式(11) 表示為
挑戰(zhàn)者檢查p是否為μ*的前綴,若不是,則挑戰(zhàn)者終止游戲,宣布失敗;若是,則可知Cμ*是由中部分矩陣級(jí)聯(lián)而成。 挑戰(zhàn)者將矩陣Cμ*擴(kuò)充成矩陣E,同時(shí)在向量v*相應(yīng)的位置上級(jí)聯(lián)零向量得到,從而滿足的關(guān)系由式(12) 表示為
因此,挑戰(zhàn)者得到SIS 問題的一個(gè)合法解。
分析規(guī)約過程:挑戰(zhàn)者模擬的所有公鑰矩陣都是統(tǒng)計(jì)接近均勻的,而對(duì)于敵手的簽名詢問,挑戰(zhàn)者給出的模擬以的概率近乎完美,從而挑戰(zhàn)者成功的概率僅取決于p是否為μ*的前綴。 又比特串p是在G中隨機(jī)選擇,從而比特串p是G的前綴的概率為1/(kQ), 故挑戰(zhàn)者成功的概率接近1/(kQ)。
2.2.3 效率分析
在基本參數(shù)(n,m,q) 相同的情況下,文章方案與利用盆景樹原理[13-14]產(chǎn)生的子密鑰對(duì)空間尺寸進(jìn)行比較,結(jié)果見表1。
表1 子密鑰對(duì)空間尺寸比較表
由表1 可知,文章提出的方案子公鑰長(zhǎng)度縮減為文獻(xiàn)[13] 和[14] 的50%,而子私鑰長(zhǎng)度縮減為文獻(xiàn)[13] 和[14] 的25%,因而減少了區(qū)塊鏈錢包存儲(chǔ)開銷,節(jié)省了區(qū)塊鏈用戶的存儲(chǔ)成本。
在基本參數(shù)(n,m,q,k) 相同的情況下,文章方案與文獻(xiàn)[13] 和[14] 方案的交易簽名過程的空間效率進(jìn)行比較,結(jié)果見表2。
表2 簽名方案空間效率比較表
由表2 可知,文章所提方案的簽名公鑰長(zhǎng)度僅為文獻(xiàn)[14] 的50%,簽名私鑰長(zhǎng)度僅為文獻(xiàn)[14]的25%;文獻(xiàn)[13] 僅實(shí)現(xiàn)隨機(jī)預(yù)言機(jī)模型下的安全性,而文章方案在標(biāo)準(zhǔn)模型下是安全的,即使如此,所提方案在簽名私鑰長(zhǎng)度依然具有優(yōu)勢(shì),僅為文獻(xiàn)[13] 的25%。
通過上述研究,可以得到如下結(jié)論:
(1) 基于分層確定性錢包技術(shù),提出一個(gè)具備后量子安全的區(qū)塊鏈交易認(rèn)證方案。 在標(biāo)準(zhǔn)模型下,基于小整數(shù)解問題(SIS)困難假設(shè),證明了方案滿足存在不可偽造性,從而實(shí)現(xiàn)了量子安全性。
(2) 文章提出的方案由于實(shí)現(xiàn)了子密鑰對(duì)尺寸與種子密鑰尺寸一致性,與文獻(xiàn)[13]和[14]比較,子公私鑰長(zhǎng)度均有所縮減,分別壓縮了50%和75%,同時(shí),文章方案交易簽名私鑰長(zhǎng)度僅為文獻(xiàn)[13]和[14]的25%。 因此,文章方案有效地減小了用戶區(qū)塊鏈錢包的存儲(chǔ)開銷,節(jié)省了區(qū)塊鏈用戶的存儲(chǔ)成本。