后量子区块链交易认证方案设计与分析

石少全王凤和

(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%。 因此，文章方案有效地减小了用户区块链钱包的存储开销，节省了区块链用户的存储成本。