基于格的具有密钥绑定和密钥隐藏属性的键值承诺方案

### 基于格的具有密钥绑定和密钥隐藏属性的键值承诺方案 #### 1. 引言 近年来，随着加密货币的迅速发展，区块链成为了一个广泛研究的领域。区块链主要应用于加密货币，如以太坊和比特币，拥有大量用户。为了让区块链更加便捷，人们开展了许多研究。承诺方案在其中发挥了重要作用，例如用于跨链通信，而键值承诺方案则用于压缩和验证区块链中的数据。 ##### 1.1 承诺方案和键值承诺方案 承诺方案由Blum在1982年提出，键值承诺方案于2020年由Agrawal等人正式提出。承诺方案在密码学中至关重要，涉及发送者和接收者两方，包含承诺阶段和解除承诺阶段。其安全性基于隐藏和绑定两个属性，隐藏属性确保接收者在解除承诺阶段前无法从承诺字符串中获取消息的部分信息，绑定属性保证发送者不能为给定的承诺字符串生成两个以上有效的解除承诺字符串。 键值承诺方案继承了承诺方案的特性，需要满足密钥隐藏和密钥绑定以防止恶意用户行为。与一般承诺方案每个用户有一个承诺值不同，键值承诺方案每n个用户有一个承诺值，多个用户通过输入“键”和“值”创建一个承诺值，可减少空间占用，因此更适用于区块链。 除了键值承诺方案，适用于区块链的协议还包括向量承诺方案和累加器。但大多数现有的向量承诺方案和累加器需要可信设置，这通常是不可取的。 ##### 1.2 基于格假设且无可信设置的构建 键值承诺方案可以在无可信设置的情况下构建，因此可应用于其他协议。Agrawal基于RSA构建了键值承诺方案，满足密钥绑定，但该方案需要可信设置，且未证明密钥隐藏属性。为了将键值承诺方案应用于区块链，必须证明其密钥隐藏属性。 此外，量子计算的出现对区块链协议和其他密码学构成威胁，因此提出使用后量子密码学的方案至关重要。Agrawal等人构建的键值承诺方案基于RSA，并非使用后量子密码学，所以构建基于后量子密码学的键值承诺方案十分必要。 ##### 1.3 贡献 本文提出了两种基于格的键值承诺方案：Insert - KVCm/2,n,q,β和KVCm,n,q,β，它们具有以下特点： - 在承诺阶段，用户无需可信设置即可创建承诺值C。 - 都满足密钥隐藏和密钥绑定属性。 - 密钥绑定属性基于SIS∞n,m,q,β问题证明，密钥隐藏属性基于新提出的Decisional - SIS∞n,m,q,β形式问题证明。 Insert - KVCm/2,n,q,β包含四个函数：Keygen、Insert、ProofUpdate和Ver；KVCm,n,q,β通过添加Update函数，包含五个函数。Insert - KVCm/2,n,q,β由于排除了Update函数，构建更简单，计算复杂度降低到KVCm,n,q,β的一半。 为了证明所提出方案的密钥隐藏属性，本文新定义了Decisional - SIS∞n,m,q,β形式问题，并讨论了其难度。还提出了One - Way - SIS∞n,m,q,β问题，证明了当One - Way - SIS∞n,m,q,β问题安全时，Decisional - SIS∞n,m,q,β形式问题是安全的。 ##### 1.4 内容组织 后续内容安排如下：第2节总结了本文使用的符号和安全假设；第3节给出新定义并讨论其难度；第4节描述Insert - KVCm/2,n,q,β及其密钥绑定和密钥隐藏属性；第5节描述KVCm,n,q,β及其密钥绑定和密钥隐藏属性；第6节比较两个提出的键值承诺方案；最后在第7节进行总结。 #### 2. 预备知识 本节介绍本文使用的符号和定义： |符号|含义| | ---- | ---- | |λ|安全参数| |N|正整数| |q|质数| |Zq|集合{0, ..., q - 1}| |[a||b]|a和b的连接| |ε(n)|关于n的可忽略函数| |poly(n)|关于n的多项式函数| |pp|公共参数| ||f||∞|f的ℓ∞ - 范数| ||f||2|f的ℓ2 - 范数| |C|提出的键值承诺值| |H|哈希函数| |M|消息映射| |C|承诺映射| |verifier|验证承诺值的人| 以下是一些问题的定义： - **最短独立向量问题（SIVPγ）**：给定n维格B的满秩基B，找到一组n个线性独立的向量S ⊂ L(B)，使得||S||2 <= γ(n) · λn(L(B))，其中λn(L(B))是格L(B)中第n个具有ℓ2 - 范数的向量。 - **短整数解问题（SIS∞n,m,q,β）**：给定均匀随机矩阵A ∈ Zn×m q，找到一个非零向量x ∈ Zm，使得A · x = 0 (mod q)且||x||∞ ≤ β。如果m, β = poly(n)且q > β · O(√n)，则SIS∞n,m,q,β至少和SIVPγ一样难，其中γ = β · O(√mn)。 键值承诺方案定义为一个非交互式原语，通过以下算法描述： - **Keygen(1λ) → (pp, C)**：输入安全参数λ，输出公共参数pp和空键值映射的初始承诺C。 - **Insert(C, (k, v)) → (C, Λk, upd)**：输入承诺字符串C和键值对(k, v)，输出新的承诺字符串C、证明Λk和更新信息upd。 - **U