后量子區(qū)塊鏈交易認證方案設計與分析

石少全王鳳和

(1.山東建筑大學 計算機科學與技術學院，山東 濟南250101；2.山東建筑大學 理學院，山東 濟南250101)

0 引言

近些年，以比特幣為代表的區(qū)塊鏈技術受到工業(yè)界和學術界的持續(xù)關注[1]。 2019 年6 月，臉書Facebook 發(fā)布了基于區(qū)塊鏈技術的數(shù)字貨幣項目Libra。 區(qū)塊鏈技術在學術界也逐漸成為熱點研究課題[2-4]。 區(qū)塊鏈使用分布式存儲、密碼學、點對點(Peer to Peer，P2P)網(wǎng)絡和共識機制等技術實現(xiàn)分布式賬本的不可篡改和不可偽造，其去中心化和不可篡改等特點使得區(qū)塊鏈在數(shù)字貨幣、支付、審計和信用體系建設等金融領域得到廣泛應用，并逐漸滲透到物聯(lián)網(wǎng)和供應鏈等多個領域[5-7]。 然而，區(qū)塊鏈在展現(xiàn)出蓬勃生命力的同時，也面臨著安全和隱私方面的嚴峻挑戰(zhàn)[8]，如區(qū)塊鏈交易中須通過認證機制來保障用戶的資金安全。

數(shù)字簽名用于確保數(shù)字貨幣的所有權及區(qū)塊鏈交易的不可偽造性和不可否認性[9]。 在區(qū)塊鏈交易認證中，用戶公鑰或公鑰的哈希值作為區(qū)分用戶的唯一標識，可作為交易地址使用。 而用戶的私鑰則作為數(shù)字貨幣所有權的唯一標識。 通常密鑰對(公私鑰對)存儲于用戶的區(qū)塊鏈錢包。 為增強匿名性，提倡每次交易使用不同的交易地址。 因此，用戶需存儲不同的密鑰對，這便增加了用戶錢包的存儲開銷。 不僅如此，由于密鑰對是一串無規(guī)律的字符串，密鑰對的增加也給用戶帶來密鑰管理不便的問題。 分層確定性錢包為此問題提供了一種可能的解決手段，其優(yōu)點在于只需備份主密鑰，降低了錢包存儲開銷的同時提升了密鑰管理效率[10]。

橢圓曲線數(shù)字簽名算法(Elliptic Curve Digital Signature Algorithm，ECDSA)已廣泛應用于區(qū)塊鏈交易認證中。 該算法具有計算效率高、密鑰和簽名尺寸小等優(yōu)點，并可為分層確定性錢包設計與使用提供強有力的技術支撐。 然而，以離散對數(shù)為代表的傳統(tǒng)困難假設無法保證量子環(huán)境下的困難性[11]，使得ECDSA 等算法不具備量子安全性。 因此，設計具備后量子安全的交易認證方案成為區(qū)塊鏈安全領域一個有意義的研究方向。 格密碼體制作為后量子密碼的重要備選之一，近些年取得豐碩成果。 與基于橢圓曲線等密碼體制設計的交易認證方案[12]比較，基于格工具設計的區(qū)塊鏈交易認證方案可為區(qū)塊鏈提供量子安全性。 YIN 等[13]提出一種后量子區(qū)塊鏈交易認證方案，將陷門生成算法和格基代理算法分別用于產(chǎn)生種子密鑰和子密鑰，從而實現(xiàn)分層確定性錢包設計。 LI 等[14]基于格工具設計了一種新的數(shù)字簽名方案，并基于該數(shù)字簽名方案提出一種后量子區(qū)塊鏈交易認證方案。 然而，上述方案存在用戶區(qū)塊鏈錢包較臃腫的缺點。 分析發(fā)現(xiàn)，格基代理算法[15]是導致區(qū)塊鏈錢包臃腫的重要原因。 事實上，格基代理算法產(chǎn)生的子密鑰的尺寸相較于種子密鑰的尺寸存在較大擴展，因而增加了用戶區(qū)塊鏈錢包的存儲開銷。

實現(xiàn)量子安全性和區(qū)塊鏈錢包空間尺寸壓縮是區(qū)塊鏈安全領域有意義的研究方向。 為此，文章基于格工具提出一種適用于分層確定性錢包的區(qū)塊鏈交易認證方案。 具體地，以AGRAWAL 等[16]提出的固定維數(shù)格基代理算法為工具生成子密鑰對，以期確保子密鑰對的尺寸與種子密鑰一致，達到縮減區(qū)塊鏈錢包存儲開銷的目的。

1 區(qū)塊鏈交易認證模型與相關理論概述

1.1 區(qū)塊鏈定義

區(qū)塊鏈通過區(qū)塊和鏈式結構來存儲數(shù)據(jù)。 以比特幣[1]為例，區(qū)塊鏈系統(tǒng)的區(qū)塊結構如圖1 所示。

圖1 比特幣中的區(qū)塊結構圖

由圖1 可知，每個區(qū)塊由區(qū)塊頭和區(qū)塊體組成。其中，區(qū)塊頭通過存儲上一區(qū)塊的哈希值(哈希值為密碼學中安全的哈希函數(shù)的哈希值)與上一區(qū)塊相連，從而形成鏈式結構。 而區(qū)塊體則用于存儲具體交易信息。 每筆交易都包含交易發(fā)送方的數(shù)字簽名，確保數(shù)據(jù)未被偽造且不可篡改。 已完成的交易永久存儲于區(qū)塊體中供所有用戶查詢。

區(qū)塊鏈交易認證過程如圖2 所示。 由圖2 可知，在交易1 中，區(qū)塊鏈用戶Alice 的公鑰(接收地址)收到來自用戶Eve 的一筆轉賬。 在交易2 中，Alice 將來自用戶Eve 的資金與Bob 產(chǎn)生交易。 具體地，Alice 利用其私鑰簽名交易2。 區(qū)塊鏈所有合法節(jié)點可利用Alice 的公鑰等信息驗證交易2 合法性，同時檢測Alice 是否為雙花。 若簽名合法且無雙花，則區(qū)塊鏈節(jié)點認為交易合法，最終該筆交易將被寫入?yún)^(qū)塊鏈中。

圖2 區(qū)塊鏈交易認證過程圖

區(qū)塊鏈系統(tǒng)中，用戶的密鑰對通常存儲于用戶的區(qū)塊鏈錢包中。 分層確定性錢包通過種子密鑰生成多個子密鑰對，在交易后，無需備份新增公鑰(交易地址)對應的私鑰，僅備份主私鑰等信息即可。因此，分層確定性錢包可以降低用戶區(qū)塊鏈錢包的存儲開銷，并提升用戶管理密鑰的效率，可為用戶密鑰的高效管理提供解決手段。

1.2 交易認證模型構建

假設交易發(fā)送方為Alice，交易接收方為Bob，適用于分層確定性錢包的區(qū)塊鏈交易認證方案構建過程如下:

(1) 系統(tǒng)建立 區(qū)塊鏈用戶Alice 輸入安全參數(shù)n，輸出主公鑰和主私鑰作為區(qū)塊鏈錢包的種子密鑰。

(2) 子密鑰對生成 當Alice 有交易需求時，通過分層確定性錢包中的種子密鑰產(chǎn)生用于交易認證的子密鑰對(pAlice，sAlice)。

(3) 交易簽名 假設pAlice已經(jīng)在某筆交易中作為接收地址(文章中直接將公鑰作為交易地址)，即該交易地址中有資金，可進行轉賬操作。 Alice 利用自己的私鑰sAlice對轉賬交易μ＝(tx，pBob)簽名，其中tx為交易信息；pBob為接收地址。 Alice 還將該筆轉賬交易通過P2P 網(wǎng)絡廣播至全網(wǎng)節(jié)點。

(4) 交易驗證 區(qū)塊鏈節(jié)點接收到Alice 的轉賬交易后，利用pAlice等公共信息對交易的簽名進行驗證。 若簽名通過驗證且無雙花，則區(qū)塊鏈節(jié)點將該筆交易存儲于新區(qū)塊中。

(5) 交易寫入?yún)^(qū)塊鏈 每個區(qū)塊鏈節(jié)點基于自身計算能力在區(qū)塊中找到一個具有足夠難度的工作量證明，成功找到難度值的節(jié)點獲得記賬權，并向全網(wǎng)廣播其所存儲的新區(qū)塊。 其他節(jié)點進行該區(qū)塊的合法性驗證，若通過驗證，則將該區(qū)塊寫入?yún)^(qū)塊鏈。此時，發(fā)送方地址pAlice中的資金被成功轉入接收方地址pBob中，交易成功。

1.3 格理論相關知識

1.3.1 符號約定

? 和? 分別為實數(shù)域和整數(shù)域；為矩陣T的列向量施密特正交化后得到的矩陣；‖‖為歐幾里得范數(shù)；poly(n)為非確定的多項式函數(shù)f(n)＝O(nd)，其中d 為常數(shù)。

1.3.2 格定義

格Λ 由式(1)表示為

式中vi為?n上一組線性無關的向量，i ＝1，2，…，n；向量組v1，v2，…，vn構成格的一組基。

密碼學中常用的兩類q模格分別由式(2) 和(3) 表示為

式中A為矩陣，；x為向量，x∈?m；u為向量，為正整數(shù)。

1.3.3 格上高斯分布

高斯函數(shù)ρs，c(x) 由式(4) 表示為

式中s為實數(shù)，s ＞0；c為中心向量，c∈?n；x為向量，x∈?n。

格上高斯分布DΛ，s，c(x) 由式(5) 表示為

事實上，格上高斯分布DΛ，s，c(x) 可以看作按照在以向量c為中心、參數(shù)為s的高斯分布中抽取格Λ中向量的條件分布。

1.3.4 格上困難問題

小整數(shù)解問題(Small Integer Solution，SIS)定義參數(shù)為(q，m，β) 的SIS 問題為給定n和一個均勻隨機的矩陣，尋找一個非零向量e，其滿足的關系可由式(6) 表示為

通常認為求解小整數(shù)解問題是困難的，即如果對恰當選取的參數(shù)(q，m，β)，在不知陷門的情況下，任意多項式時間敵手成功破解SIS 問題的概率是可忽略的。

1.3.5 格上相關引理

引理1[17]設一個n維格，ηε(Λ) 為光滑參數(shù)，則服從格上高斯分布的向量x滿足的關系由式(7)表示為

式中P為概率，s≥ηε(Λ)；ε為實數(shù)，ε∈(0，1)；x～DΛ，s，c為x服從格上高斯分布DΛ，s，c。

引理2(陷門生成算法)[17]存在一個概率多項式時間算法TrapGen(1n)，令q ＞3、m ＝O(nlbq)，輸入安全參數(shù)n，該算法輸出一個統(tǒng)計接近均勻的矩陣及其格(A)的陷門基TA∈?m×m，滿足

引理3(原像抽樣算法)[17]存在一個概率多項式時間算法SamplePre(A，TA，s，u)， 以矩陣A∈、格的陷門基TA∈?m×m、高斯參數(shù)s≥為輸入，該算法輸出一個向量e，滿足統(tǒng)計接近DΛuq(A)，s，c，由引理1 可知，原像抽樣算法SamplePre 所抽取的對應于向量的一個原像e將以壓倒性的概率滿足

引理4(固定維數(shù)格基代理算法)[16]存在一個概率多項式時間算法BasisDel(A，R，TA，s)，以矩陣可逆矩陣R∈?m×m(如果矩陣R∈?m×m作為中的矩陣是可逆的，則稱R是?q的可逆矩陣)、格Λ⊥q(A) 的陷門基TA和參數(shù)s ＞為輸入，該算法輸出格的一個陷門基TB∈?m×m，滿足

2 后量子區(qū)塊鏈交易認證方案設計與分析

2.1 交易認證方案設計

假設交易發(fā)送方為Alice，交易接收方為Bob。n為安全參數(shù)，m、q、β、s1、s2均為n的函數(shù)。 文章設計的后量子區(qū)塊鏈交易認證方案為

(1) 系統(tǒng)建立 發(fā)送方Alice 輸入安全參數(shù)n，調用TrapGen 算法，生成一個統(tǒng)計接近均勻的矩陣主公鑰及其格(A)對應的陷門基主私鑰TA，Alice 將其存儲在區(qū)塊鏈錢包中作為種子密鑰。

(2) 子密鑰對生成 Alice 隨機選擇1 個?q可逆矩 陣R∈?m×m并 調 用 算 法BasisDel 得 到TB←BasisDel(A，TA，R，s1)，其中B ＝AR-1。 則pAlice＝B，sAlice＝TB。

(3) 交易簽名 假設pAlice已經(jīng)在某筆交易中作為接收地址，即該交易地址中有資金，可進行轉賬操作。 Alice 隨機選擇k個均勻矩陣C1，C2，…，Ck∈，并公開公共參數(shù)PP ＝〈B，C1，C2，…，Ck〉。 設Alice 與Bob 之間的轉賬交易為μ ＝(tx，pBob) ∈{0，1}k。 Alice 按照如下方式進行該筆轉賬交易的簽名:

①Alice 根據(jù)μi的取值決定是否選擇矩陣Ci，若μi ＝1，則選擇相應的矩陣Ci，否則不選相應的矩陣Ci。 設通過以上原則Alice 一共選擇了j個矩陣Ck1，Ck2，…，Ckj，將這j個矩陣進行依次級聯(lián)得到一個新的矩陣Cμ ＝B ｜Ck1｜…｜Ckj；

②Alice 選 擇j個 小 向 量vk1，vk2，…，vkj， 且計算

③ Alice 由 原 像 抽 樣 算 法 得 到vk0， 即令向量v為j ＋1 個向量依次級聯(lián)得到的向量，則Alice 對于交易μ的簽名為v。 Alice 將該筆轉賬交易通過P2P 網(wǎng)絡廣播至全網(wǎng)節(jié)點。

(4) 交易驗證 區(qū)塊鏈節(jié)點按如下方式驗證Alice 簽名的合法性:

①區(qū)塊鏈節(jié)點根據(jù)μi的取值決定是否選擇矩陣Ci，若μi ＝1，則選擇相應的矩陣Ci，否則不選相應的矩陣Ci。 設通過以上原則區(qū)塊鏈節(jié)點一共選擇了j個矩陣Ck1，Ck2，…，Ckj，將這j個矩陣進行依次級聯(lián)得到矩陣Cμ ＝B ｜Ck1｜…｜Ckj；

②區(qū)塊鏈節(jié)點驗證Cμv ＝0(modq)，v≠0，是否成立，若成立，且該交易中的資金未被花費，則區(qū)塊鏈節(jié)點認為交易合法，并將該交易存儲進新區(qū)塊。

(5) 交易寫入?yún)^(qū)塊鏈 每個節(jié)點基于自身計算能力在區(qū)塊中找到一個具有足夠難度的工作量證明，成功找到難度值的節(jié)點獲得記賬權，并向全網(wǎng)廣播其所存儲的新區(qū)塊。 其他節(jié)點進行該區(qū)塊的合法性驗證，若通過驗證，則將該區(qū)塊寫入?yún)^(qū)塊鏈。 此時Alice 的轉賬交易成功寫入?yún)^(qū)塊鏈。 即發(fā)送方地址pAlice中的資金被成功轉入接收方地址pBob中，交易成功。

2.2 交易認證方案分析

2.2.1 正確性分析

為實現(xiàn)方案的完備性， 需要TrapGen 算法、BasisDel 算法和SamplePre 算法正常運行。 為此，方案參數(shù)設置如下mω(lb2m) 。 AGRAWAL 等[16]和GENTRY 等[17]已驗證在上述參數(shù)下TrapGen 算法、BasisDel 算法和SamplePre 算法能夠確保正常運行。 因此，方案中系統(tǒng)建立、子密鑰對生成、交易簽名和交易驗證可正常執(zhí)行。

由BasisDel 算法的正確性可知，每個合法的用戶擁有格及其相應的陷門，故由簽名過程可知，向量vk0是SamplePre 算法的輸出，從而vk0滿足的等式由式(8)表示為

進而可得v滿足的等式由式(9) 表示為

故證明該方案是正確的。

2.2.2 存在不可偽造性分析

不失一般性，假設待敵手簽名詢問的Q個交易的值 分 別 為:μ(1)，μ(2)，…，μ(Q)。 設p不 為μ(1)，μ(2)，…，μ(Q)中任何前綴的最小字符串，G為p組成的集合，即p∈G。 由文獻[15]可知，集合G可以在多項式時間內計算得到，且集合G中最多有kQ個元素。 挑戰(zhàn)者在集合G中任意選擇一個p，令t為字符串p的漢明重量，pi表示字符串p的第i個位置的取值，挑戰(zhàn)者按如下方式生成公共參數(shù):

(1) 當i≤｜ p ｜， 且pi ＝0 時， 挑戰(zhàn)者調用TrapGen 算法得到一組矩陣及對應格的陷門Ti；

(2) 當i≤｜p ｜，且pi ＝1 時，令

(3) 當i ＞｜p ｜時，令

挑戰(zhàn)者將公共參數(shù)(B，Ci) 發(fā)送給敵手，同時挑戰(zhàn)者在本地建立列表L 用于記錄對交易簽名的回答。

簽名詢問 當敵手進行關于交易μ(i)的簽名詢問時，挑戰(zhàn)者首先查詢列表L 中是否有μ(i)的簽名，若有，則返回列表L 中的相應的簽名vi給敵手；否則，因為p不是任何μ(1)，μ(2)，…，μ(Q)的前綴，從而在μ(i)的前p個位置中還存在1 的概率為1-。 設 該 位 置 為i′， 而 此 時 挑 戰(zhàn) 者 擁 有Λ⊥(Ci′) 對應的陷門Ti′，因此挑戰(zhàn)者可以利用陷門為μ(i)生成對應的簽名vi，簽名生成過程與方案描述中的簽名過程類似，挑戰(zhàn)者將生成的簽名vi發(fā)送給敵手，并將(μ(i)，vi) 存儲在列表L 中。

偽造 在敵手完成Q次簽名詢問并感到滿意后，敵手以ε的概率輸出一個消息μ*偽造的簽名v*，且v*滿足的關系可由式(11) 表示為

挑戰(zhàn)者檢查p是否為μ*的前綴，若不是，則挑戰(zhàn)者終止游戲，宣布失??；若是，則可知Cμ*是由中部分矩陣級聯(lián)而成。 挑戰(zhàn)者將矩陣Cμ*擴充成矩陣E，同時在向量v*相應的位置上級聯(lián)零向量得到，從而滿足的關系由式(12) 表示為

因此，挑戰(zhàn)者得到SIS 問題的一個合法解。

分析規(guī)約過程:挑戰(zhàn)者模擬的所有公鑰矩陣都是統(tǒng)計接近均勻的，而對于敵手的簽名詢問，挑戰(zhàn)者給出的模擬以的概率近乎完美，從而挑戰(zhàn)者成功的概率僅取決于p是否為μ*的前綴。 又比特串p是在G中隨機選擇，從而比特串p是G的前綴的概率為1/(kQ)， 故挑戰(zhàn)者成功的概率接近1/(kQ)。

2.2.3 效率分析

在基本參數(shù)(n，m，q) 相同的情況下，文章方案與利用盆景樹原理[13-14]產(chǎn)生的子密鑰對空間尺寸進行比較，結果見表1。

表1 子密鑰對空間尺寸比較表

由表1 可知，文章提出的方案子公鑰長度縮減為文獻[13] 和[14] 的50%，而子私鑰長度縮減為文獻[13] 和[14] 的25%，因而減少了區(qū)塊鏈錢包存儲開銷，節(jié)省了區(qū)塊鏈用戶的存儲成本。

在基本參數(shù)(n，m，q，k) 相同的情況下，文章方案與文獻[13] 和[14] 方案的交易簽名過程的空間效率進行比較，結果見表2。

表2 簽名方案空間效率比較表

由表2 可知，文章所提方案的簽名公鑰長度僅為文獻[14] 的50%，簽名私鑰長度僅為文獻[14]的25%；文獻[13] 僅實現(xiàn)隨機預言機模型下的安全性，而文章方案在標準模型下是安全的，即使如此，所提方案在簽名私鑰長度依然具有優(yōu)勢，僅為文獻[13] 的25%。

3 結論

通過上述研究，可以得到如下結論:

(1) 基于分層確定性錢包技術，提出一個具備后量子安全的區(qū)塊鏈交易認證方案。 在標準模型下，基于小整數(shù)解問題(SIS)困難假設，證明了方案滿足存在不可偽造性，從而實現(xiàn)了量子安全性。

(2) 文章提出的方案由于實現(xiàn)了子密鑰對尺寸與種子密鑰尺寸一致性，與文獻[13]和[14]比較，子公私鑰長度均有所縮減，分別壓縮了50%和75%，同時，文章方案交易簽名私鑰長度僅為文獻[13]和[14]的25%。 因此，文章方案有效地減小了用戶區(qū)塊鏈錢包的存儲開銷，節(jié)省了區(qū)塊鏈用戶的存儲成本。