三元LWE的量子密钥搜索

# 三元LWE的量子密钥搜索 ## 1. 预备知识 ### 1.1 LWE密钥 我们仅考虑三元LWE密钥，其定义如下： - **定义1（三元LWE密钥）**：LWE密钥由三个公共参数 $q$、$A \in Z_q^{m\times n}$、$b \in Z_q^m$ 以及两个秘密参数 $s \in Z_q^n$ 和（误差）$e \in Z_q^m$ 组成，满足等式 $As = b + e \mod q$。若 $\|s\|_{\infty} = \|e\|_{\infty} = 1$，则称 $s$ 和 $e$ 为三元密钥。用 $T^n$ 表示 $n$ 维三元密钥的集合。在本文中，我们仅考虑三元密钥 $s$、$e$ 以及 $m = n$ 的方阵 $A$。 - **定义2（权重）**：设 $s = (s_1, ..., s_n)$ 是 $F^n$ 中的向量，该向量 $s$ 的权重 $w$ 定义为其汉明权重 $w = \sum_{s_i \neq 0} 1$。相对于 $n$，我们还定义相对权重 $\omega = w/n$，其中 $0 \leq \omega \leq 1$。具有偶数个 $\pm1$ 元素（各为 $w/2$ 个）的三元权重 - $w$ 密钥集合记为 $T^n(w/2)$。 当前的安全分析表明，最优相对权重范围为 $\omega \in [1/3, 2/3]$，对于NTRU类型的方案，$\omega = 3/8$ 和 $\omega = 1/2$ 是突出的选择。 我们使用以下标准公式来近似三元密钥的搜索空间 $S$，该公式在一个小多项式因子 $1/\sqrt{n}$ 内成立，一般在本文中我们忽略小多项式因子。 - **引理1（多项式近似）**：设 $D = \{d_1, ..., d_k\} \subset Z_q$ 是一个基数为 $k$ 的数字集。$Z_q^n \cap D^n$ 中恰好有 $c_in$ 个 $d_i$ 元素（$\sum_{i = 1}^k c_i = 1$）的向量 $s$ 的数量为： \[ \begin{pmatrix} n \\ c_1n, ..., c_kn \end{pmatrix} \approx 2^{H(c_1, ..., c_k)n} \] 其中熵 $H(c_1, ..., c_k) = \sum_{i = 1}^k c_i \log_2(1/c_i)$。 ### 1.2 量子行走 为了将经典的Meet - LWE算法转换到量子环境中，我们利用了Magniez - Nayak - Roland - Santha的量子行走框架。 #### 1.2.1 经典随机行走 经典随机行走在图中搜索标记顶点分3步： 1. 在设置时间 $T_S$ 内设置一个明确的顶点 $v$。 2. 将 $v$ 更新为随机相邻顶点，更新 $1/\delta$ 次，每次更新耗时 $T_U$。 3. 在检查时间 $T_C$ 内检查得到的顶点是否被标记。若未标记，则返回步骤2。 这里图的谱隙 $\delta$ 告诉我们需要执行多少步才能到达一个（几乎）均匀随机的顶点进行检查。若有 $\epsilon$ 比例的顶点被标记，则总时间复杂度为： \[ T_{RW} = T_S + \frac{1}{\epsilon}(T_C + \frac{1}{\delta}T_U) \] #### 1.2.2 量子行走 与经典随机行走不同，量子行走可以走到所有相邻顶点的叠加态，只需重复 $1/\sqrt{\delta}$ 次。并且，我们可以改变具有标记顶点的状态的相位，重复 $1/\sqrt{\epsilon}$ 次后，在量子时间复杂度内测量到一个标记节点： \[ T_{QW} = T_S + \frac{1}{\sqrt{\epsilon}}(T_C + \frac{1}{\sqrt{\delta}} \cdot T_U) \] Johnson图有助于最小化更新成本。 - **定义3（Johnson图）**：设 $L$ 是一个大小为 $N$ 的集合。对于某个 $r \leq N$，Johnson图 $J(N, r)$ 是一个无向图 $G_J = (V_J, E_J)$，其中 $|V_J| = \binom{N}{r}$ 个顶点表示 $L$ 的大小为 $r$ 的子集。若 $v, v' \in V_J$ 表示的子集 $S, S'$ 相差一个元素，即 $|S \cap S'| = r - 1$，则 $\{v, v'\} \in E_J$。 - **定义4**：给定图 $G_1 = (V_1, E_1)$、$G_2 = (V_2, E_2)$，定义笛卡尔积 $G_1 \times G_2 = (V, E)$ 为：$V = V_1 \times V_2 = \{v_1v_2 | v_1 \in V_1, v_2 \in V_2\}$，$E = \{v_1v_2, v_1'v_2' | (v_1 = v_1', (v_2, v_2') \in E_2) 或 ((v_1, v_1') \in E_1, v_2 = v_2')\}$。 $m$ 个Johnson图的笛卡尔积 $J^m(N, r) = \times_{i = 1}^m J(N, r)$ 的谱隙可以用以下公式近似： \[ \delta(J^m(N, r)) \geq \frac{1}{m\delta(J(N, r))} = \Omega(\frac{1}{r}) \] ## 2. 量子Meet - LWE - 高层思路 ### 2.1 经典Meet - LWE 经典Meet - LWE算法的高层思路如下： 设 $s$ 是一个三元权重 - $w$ 的LWE秘密密钥，且 $\pm1$ 的数量为偶数。令 $w(0) = w/2$，则 $s \in T^n(w(0))$。我们将 $s$ 写为 $s = s_1^{(1)} + s_2^{(1)}$，其中 $s_1^{(1)}, s_2^{(1)} \in T^n(w^{(1)})$，且 $w^{(1)} \geq w^{(0)}/2$。 将LWE等式 $As = b + e \mod q$ 重写为： \[ As_1^{(1)} + e_1 = b - As_1^{(1)} + e_2 \mod q \] 其中 $e_1, e_2 \in \{0, 1\}^n$。 Meet - LWE算法构建满足上述等式在 $r$ 个坐标上的候选解 $s_1^{(1)}, s_2^{(1)}$。设 $R^{(1)}$ 是将 $s$ 写为 $s_1^{(1)} + s_2^{(1)}$ 的表示数量，令 $r = \lfloor \log_q(R^{(1)}) \rfloor$，并固定一个随机目标 $t \in Z_q^r$。用 $\pi_r : Z_q^n \to Z_q^r$ 表示投影到前 $r$ 个坐标。则期望至少有一个 $s$ 的表示满足： \[ \pi_r(As_1^{(1)} + e_1) = t = \pi_r(b - As_1^{(1)} + e_2) \mod q \] 该算法的步骤如下： ```plaintext 算法1. 经典Meet - LWE 输入: LWE公钥 $(A, b) \in Z_q^{n\times n} \times Z_q^n$，权重 $w \in N$ 输出: 满足 $e = As - b \mod q \in T^n$ 的三元权重 - $w$ 的 $s$ 1: 设 $R^{(1)}$ 是 $s = s_1 + s_2$ 的表示数量，令 $r = \lfloor \log_q(R^{(1)}) \rfloor$。 2: 对于所有 $\pi_r(e) \in T^r$ 执行以下操作 3: 使用基于树的列表构造方法构造 $L_1^{(1)}, L_2^{(1)}$。 4: 通过Odlyzko哈希找到 $s_1, s_2$，使得 $s_1 + s_2 \in T^n(w/2)$ 且 $A(s_1 + s_2) - b \in T^n$。 5: 结束循环 6: 返回 $s = s_1 + s_2$ ``` ### 2.2 量子Meet - LWE（QMEET - LWE） 为了将Meet - LWE转换为量子随机行走QMeet - LWE，我们使用了在子集和问