基于格的键值承诺方案解析

### 基于格的键值承诺方案解析 #### 1. 引言 在密码学领域，键值承诺方案是一种重要的工具，用于在不泄露具体信息的情况下对键值对进行承诺。本文将介绍基于格的键值承诺方案，特别是插入式键值承诺方案（Insert - KVC）和通用键值承诺方案（KVC），并分析它们的构造、性质和安全性。 #### 2. 基于SIS问题的基础操作 首先，我们有向量 $y = Ax \in Z^n$，可以表示为： \[ y = \begin{pmatrix} c_{11} \cdot x_1 + c_{12} \cdot x_2 + \cdots + c_{1n} \cdot x_n \\ \vdots \\ c_{m1} \cdot x_1 + c_{m2} \cdot x_2 + \cdots + c_{mn} \cdot x_n \end{pmatrix} \] 我们随机选择 $k \in Z_{\beta}$ 和 $l_{i1} \in Z_q$（$i = 1, \cdots, n$），计算对： \[ A' = \begin{pmatrix} A - \begin{pmatrix} l_{11} & 0 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ l_{m1} & 0 & \cdots & 0 \end{pmatrix}, y - \begin{pmatrix} l_{11} \cdot k \\ \vdots \\ l_{m1} \cdot k \end{pmatrix} \end{pmatrix} \] 其中 $A' = A - \begin{pmatrix} l_{11} & 0 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ l_{m1} & 0 & \cdots & 0 \end{pmatrix}$ 且 $y' = y - \begin{pmatrix} l_{11} \cdot k \\ \vdots \\ l_{m1} \cdot k \end{pmatrix}$。 如果 $k = x_1$，则 $y'$ 可以写成： \[ y' = \begin{pmatrix} (c_{11} - l_{11}) \cdot x_1 + \cdots + c_{1n} \cdot x_n \\ \vdots \\ (c_{m1} - l_{m1}) \cdot x_1 + \cdots + c_{mn} \cdot x_n \end{pmatrix} \] 因为 $y'$ 可以表示为 $y' = A'x$ 的形式，所以可以判断 $A'$ 是否属于 $SIS^{\infty}_{n,m,q,\beta}$ 分布。具体流程如下： 1. B 计算 $A'$ 并发送给 A。 2. A 根据 $k$ 与 $x_1$ 的关系判断 $A'$ 的分布： - 若 $k = x_1$，$A'$ 属于 $SIS^{\infty}_{n,m,q,\beta}$ 分布。 - 若 $k \neq x_1$，$A'$ 属于均匀分布。 3. A 将结果发送给 B，B 可以得到 $x_1$ 的值。 4. 对 $[x_2, \cdots, x_m]$ 重复上述过程，B 可以得到 $x$ 的值。 B 最多经过 $\beta$ 次尝试可以得到 $x_1$ 的值，因此得到所有 $x$ 的值最多需要 $\beta m$ 次迭代，这是一个多项式数量。从定理 1 的逆否命题可知，Decisional - SIS$^{\infty}_{n,m,q,\beta}$ 问题和 One - Way - SIS$^{\infty}_{n,m,q,\beta}$ 问题具有相同的安全性。 #### 3. 基于SIS的插入式键值承诺方案（Insert - KVC$_{m/2,n,q,\beta}$） ##### 3.1 方案构造 Insert - KVC$_{m/2,n,q,\beta}$ 方案包含四个函数：Keygen、Insert、ProofUpdate 和 Ver。 - **Keygen(1$^{\lambda}$) → (pp, CM)**： - 采样描述 $q, m, n, \beta$，满足 $m, \beta = poly(n)$ 且 $q > \beta \cdot \tilde{O}(\sqrt{n})$。 - 采样均匀随机矩阵 $A \in Z_q^{n \times m}$ 作为公共参数 $pp$。 - 设置 $V = Z^m$ 和 $K = Z^m$，选择单位矩阵 $E$ 和 $u \in V$。 - 输出 $(pp, C) = ((q, m, n, \beta, u), (E \cdot u, A \cdot u))$。 - **Insert(C, (k_i, v_i)) → (C, \Lambda_{k_i}, upd)**： - 解析 $C$ 为 $(C_1, C_2)$，解析 $\Lambda_{k_i}$ 为 $(\Lambda_{k_i,1}, \Lambda_{k_i,2})$。 - 计算 $z_i = H(k_i)$，其中 $H$ 是哈希函数 $H : Z^{\ell} \to Z_{\beta/2}^{m/2}$。 - 计算 $x_i = (z_i || v_i)^v$。 - 插入承诺值和证明： \[ \Lambda_{k_i}' = (C_1, C_2) \] \[ C' = (C_1 + A \cdot x_i, C_2 + A \cdot x_i) \] \[ upd = (z_i, v_i) \] - 更新 $\Lambda_{k_i}$ 和 $C$： \[ \Lambda_{k_i,1} \leftarrow \Lambda_{k_i,1}' \] \[ \Lambda_{k_i,2} \leftarrow \Lambda_{k_i,2}' \] \[ C_1 \leftarrow C_1' \] \[ C_2 \leftarrow C_2' \] - 输出 $(C, \Lambda_{k_i}, upd)$。 - **ProofUpdate(k_i, \Lambda_{k_i}, upd) → \Lambda_{k_i}'$**： - 解析 $upd$ 为 $(upd_1, upd_2)$。 - 计算 $z = H(upd_1)$，$x = (z || upd_2)$。 - 更新 $\Lambda_{k_i}$： \[ \Lambda_{k_i,1} = \Lambda_{k_i} + A \cdot x \] \[ \Lambda_{k_i,2} = \Lambda_{k_i} + A \cdot x \] - 输出 $\Lambda_{k_i}$。 - **Ver(C, (k_i, v_i), \Lambda_{k_i}) → 1 / \perp$**： - 解析 $C$ 为 $(C_1, C_2)$，解析 $\Lambda_{k_i}$ 为 $(\Lambda_{k_i,1}, \Lambda_{k_i,2})$。 - 计算 $z = H(k_i)$，$x_i = (z || v_i)$。 - 验证以下条件： - $v_i \in V$ 且 $k_i \in K$。 - $\Lambda_{k_i,1} + A \cdot x_i = C_1$。 - $\Lambda_{k_i,2} + A \cdot x_i = C_2$。 - $\Lambda_{k_i,2} - \Lambda_{k_i,1} = u \cdot (A - E)$。 - 若条件满足，输出 1；否则输出 $\perp$。 ##### 3.2 复杂度分析 | 函数 | 哈希计算次数 | 乘法成本 | 加法成本 | | ---- | ---- | ---- | ---- | | Insert | 1 | 2mn | 4n | | ProofUpdate | 1 | 2mn | 4n | | Ver | 1 | 2mn | 3n | 假设只有一个用户，每个函数执行一次，且键值承诺的大小是常数