简洁的可变承诺向量：原理、构造与应用

### 简洁的可变承诺向量：原理、构造与应用 在密码学和分布式系统中，承诺方案是一种重要的工具，用于确保数据的完整性和隐私性。本文将详细介绍一种名为 Mercurial Subvector Commitments（MSVC）的承诺方案，包括其基本原理、详细构造、正确性证明以及在实际应用中的表现。 #### 1. 模拟游戏与安全性 模拟游戏是验证承诺方案安全性的重要方法。在这个游戏中，模拟器 C 执行 Setup*(λ, N) 获取安全参数 param 和陷门 tk。对手 A 与 C 交互，试图区分是真实世界的设置还是理想设置。具体通过抛硬币 b ∈{0, 1} 来决定游戏设置： - **HHEquivocation**：A 选择消息元组 (m1, · · ·, mN)，C 抛硬币 b。若 b = 0，C 计算 (C, aux) ←HCommit(m, param)；若 b = 1，(C, aux) ←Commit*(param, tk)。A 可对 S ∈[N] 进行查询，b = 0 时 C 返回 πi ←HProve(i, m[−i], aux)，b = 1 时 C 回复 πi ←HProve*(i, m, aux)。 - **HSEquivocation**：类似 HHEquivocation，只是在查询回复时，b = 0 时 C 返回 πi ←SProve(i, mi, H, aux)，b = 1 时 C 回复 πi ←SProve*(i, mi, aux)。 - **SSEquivocation**：C 抛硬币 b。若 b = 0，C 计算 (C, aux) ←SCommit(param)；若 b = 1，(C, aux) ←Commit*(param, tk)。A 可查询，b = 0 时 C 返回 πi ←SProve(i, mi, S, aux)，b = 1 时 C 回复 πi ←SProve*(i, mi, aux)。 这个过程的流程图如下： ```mermaid graph TD; A[模拟器 C] -->|Setup*(λ, N)| B(获取 param 和 tk); B -->|抛硬币 b| C{b = 0 或 1}; C -->|b = 0| D(真实承诺和证明); C -->|b = 1| E(伪造承诺和证明); F[对手 A] -->|选择消息元组| G(与 C 交互); G -->|查询 S ∈[N]| H(接收 C 回复); ``` #### 2. MSVC 的详细构造 为了实现 MSVC，我们借鉴了 mercurial commitments 和 subvector commitments 的思想，具体构造如下： - **Setup(λ, N) →(param)**：输入安全参数 λ，生成 G = (p, G1, G2, GT, e)，其中 G1, G2, GT 是素数阶 p 的循环乘法群。选择随机 α ←Z∗p 计算 a = (α1, · · ·, αN)，并计算 ga1, ga2, ga[−1]·αN1。公共参数 param = (G, H, ga1, ga2, ga[−1]·αN1)，α 在系统初始化后丢弃。 - **HCommit(m, param) →((C, V), aux)**：输入消息集 m，生成承诺对 (C, V) 和辅助信息 aux。 - \(V = g_1^{\gamma} \cdot \prod_{j=1}^{N} g_1^{m_j \alpha_j}\) - \(C = g_1^{\theta}\) - 辅助信息 aux = (m1, · · ·, mN, γ, θ) - **HProve(i, m[−i], aux) →(πi)**：输入消息和辅助信息，生成位置 i 的证明 πi。 - \(W_i = \left(g_2^{\gamma} \cdot \prod_{j=1,j\neq i}^{N} g_2^{m_j \alpha_j}\right)^{\frac{\alpha_{N+1-i}}{\theta}}\) - 证明 πi = (Wi, θ) - **HVerify((C, V), i, mi, πi) →(0/1)**：验证打开证明，检查以下方程是否成立： - \(e(V, g_2^{\alpha_{N+1-i}}) = e(C, W_i) \cdot e(g_1, g_2)^{\alpha_{N+1} m_i}\) - 成立输出 1，否则输出 0 - **HUpdate(C, V, S, m[S], m′[S], aux) →((C′, V′), aux′)**：更新承诺中位置集 S 的消息。 - \(V' = V \cdot \prod_{i\in S} g_1^{(m'_i - m_i) \alpha_i}\) - \(C' = C\) - 辅助信息 aux′ = (m′, γ, θ) - **SCommit(param) →(C, aux)**：输入安全参数 param，生成软承诺对 (C, V) 和辅助信息 aux。 - \(V = (g_1^{\alpha})^{\gamma}\) - \(C = (g_1^{\alpha})^{\theta}\) - 辅助信息 aux = (θ, γ) - **SProve(i, mi, F, aux) →(πi)**：根据标志位 F