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

石少全王鳳和

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

0 引言

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

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

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

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

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

1.1 區塊鏈定義

區塊鏈通過區塊和鏈式結構來存儲數據。 以比特幣[1]為例，區塊鏈系統的區塊結構如圖1 所示。

圖1 比特幣中的區塊結構圖

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

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

圖2 區塊鏈交易認證過程圖

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

1.2 交易認證模型構建

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

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

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

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

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

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

1.3 格理論相關知識

1.3.1 符號約定

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

1.3.2 格定義

格Λ 由式(1)表示為

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

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

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

1.3.3 格上高斯分布

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

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

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

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

1.3.4 格上困難問題

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

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

1.3.5 格上相關引理

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

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

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

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

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

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

2.1 交易認證方案設計

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

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

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

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

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

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

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

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

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

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

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

2.2 交易認證方案分析

2.2.1 正確性分析

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

由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個元素。 挑戰者在集合G中任意選擇一個p，令t為字符串p的漢明重量，pi表示字符串p的第i個位置的取值，挑戰者按如下方式生成公共參數:

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

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

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

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

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

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

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

因此，挑戰者得到SIS 問題的一個合法解。

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

2.2.3 效率分析

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

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

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

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

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

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

3 結論

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

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

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