公钥加密的代数方法与量子不可区分性研究

### 公钥加密的代数方法与量子不可区分性研究 #### 1. 秩支持学习问题的代数方法 在秩支持学习问题的研究中，对于不同的参数情况，存在着不同的实验结论。当 \(b \geq w + 2\) 时，实验发现存在一定程度的下降以及归零现象。具体而言： - 当 \(b \geq w + 2\) 时，有 \(N_{F_2}^b \leq \sum_{d = 1}^{w + 1} \sum_{j_d = 1}^{n - k} \binom{j_d - 1}{d - 1} \binom{n - k - j_d}{w + 1 - d} \binom{N - j_d}{b - d} + \sum_{j = 1}^{n - k} \binom{j - 1}{w} \binom{N - j}{b - w - 2}\)； - 当 \(b \leq w + 1\) 时，有 \(N_{F_2}^b = \sum_{d = 1}^{b} (-1)^{d + 1} \binom{n - k}{w + d} \binom{N}{b - d}\)。 在 Durandal 签名方案中，对于对应私钥的 RSL 实例，假设 \(m\) 和 \(k = n/2\) 均为素数。存在引理表明，对于来自 Durandal RSL 实例的 \(S = [s_1^T \cdots s_N^T] \in F_{q^m}^{(n - k) \times N}\)，存在可逆矩阵 \(U \in F_{q^m}^{k \times k}\) 使得 \(US = [I_k \quad *]\)。其证明过程如下： 1. 对 \(S\) 的列进行置换后，可假设前 \(k\) 个综合征 \(s_1^T, \cdots, s_k^T\) 对应于唯一的 \(\sigma^T\) 的理想移位。此时，\(S\) 中左边的 \(k \times k\) 块等于理想矩阵 \(IM(\sigma)^T\)。 2. 由于 Durandal 中的双循环理想矩阵 \(H\) 是随机生成的，所以 \(\sigma \neq 0\) 的概率极大。 3. 因为 \(P\) 在 \(F_q\) 上不可约，且 \(m\) 和 \(k\) 均为素数，存在向量 \(u \in F_{q^m}^k\) 使得 \(\sigma u = 1 \mod P\)，这意味着 \(IM(\sigma)IM(u) = I_k\)，令 \(U := IM(u)^T\) 即可得证。 在低权重码字数量的研究方面，通过对命题 1 的证明，给出了 \(C'\) 中权重 \(\leq r\) 的码字数量的公式。设 \(D\) 是由右因子 \(R_i\) 生成的 \([r \times n, N]_q\) - 矩阵码，其中 \(e_i := (\beta_1, \cdots, \beta_m)CR_i\) （\(i \in \{1..N\}\)），假设 \(D\) 是随机的 \(F_q\) - 线性码。矩阵 \(C\) 的秩恰好为 \(r\)，所以对于所有 \(w \leq r\)，有 \(X_{C', w} = X_{D, w}\)。 - 对于 \(c \in F_q^{r \times n}\)，用 \(1_{c \in D}\) 表示随机变量，若 \(c \in D\) 则其值为 1，否则为 0，那么 \(X_{D, w} = \sum_{\omega(c) = w} 1_{c \in D}\)。 - 根据期望的线性性质，\(E[X_{D, w}] = \sum_{\omega(c) = w} E[1_{c \in D}] = \sum_{\omega(c) = w} P(c \in D)\)。 - 由于 \(c \in D\) 的概率是满足 \(r \times n - N\) 个独立奇偶校验方程 \(\langle h, c \rangle