探索基于SIDH的签名参数

### 探索基于SIDH的签名参数 #### 1. 路径长度与时间复杂度 在某些方法中，返回的最短路径长度为 $\frac{3}{2} \log p$，所需时间为 $\tilde{O}(p)$。这里的 $p$ 略小于 $2^{2\lambda}$。生成长度为 $\frac{3}{2} \log p$ 的路径的攻击成本远大于安全参数。若将运行时间设为 $\sqrt{p} \approx 2^{\lambda}$，则该方法输出的路径长度为 $2 \log p$。 #### 2. 非极端阶的KLPT算法 设 $E$ 和 $E_1$ 是定义在 $\mathbb{F}_{p^2}$ 上的两个超奇异椭圆曲线，已知它们的自同态环分别为 $O$ 和 $O_1$，$I$ 是 $O$ 和 $O_1$ 的连接理想，$O_0$ 是特殊的极端阶，$I_0 = I(O_0, O)$。问题是找到一个与 $I$ 等价的具有光滑范数的 $O$-左理想。 ##### 2.1 [42]中的方法 步骤如下： 1. 计算 $I_1 = I_0 \frac{\overline{\gamma_1}}{\text{Nrd}(I_0)}$，其中 $\text{Nrd}(\gamma_1) = n_1 \text{Nrd}(I_0)$； 2. 计算 $I_2 = I_0I \frac{\overline{\gamma_2}}{\text{Nrd}(I_0I)}$，其中 $\text{Nrd}(\gamma_2) = n_2 \text{Nrd}(I_0I)$； 3. 返回 $\frac{I\overline{\gamma}}{\text{Nrd}(I)}$，其中 $\gamma = \overline{\gamma_1}\gamma_2$。 使用此方法，最短路径长度大于 $4 \log(p)$。 ##### 2.2 SQISign方法 该方法通过 $I_0$ 进行拉回和前推来处理特殊情况。对于 $n = \ell^e$，算法步骤如下： 假设 $\text{Nrd}(I_0) = N_0$ 在 $R$ 中是惰性素数，使得 $\ell$ 是模 $N_0$ 的二次非剩余。 1. 计算 $K = [I_0]^*I$； 2. 计算一个与 $K$ 等价的素范数为 $N$ 的理想 $L$，使得 $\ell$ 是模 $N$ 的二次非剩余。设 $\delta$ 使得 $L = \chi_K(\delta)$； 3. 找到一个范数为 $N\ell^{e_1}$ 的元素 $\gamma \in O$，其中 $e_1 \in \mathbb{N}$； 4. 找到一个元素 $\alpha \in O$ 使得 $L = O\alpha + NO$； 5. 计算 $\mu_0 = (C_0 + \omega D_0)j \in Rj$ 使得 $\gamma\mu_0 \equiv \alpha \pmod{NO}$； 6. 计算 $\mu_1 = (C_1 + \omega D_1)j \in Rj$ 使得 $\gamma\mu_0\delta \in O \cap O_0$； 7. 计算 $C = \text{CRT}_{N_0,N}(C_0, C_1)$ 和 $D = \text{CRT}_{N_0,N}(D_0, D_1)$，并设 $\mu' = (C + \omega D)j$； 8. 计算 $\lambda \in \mathbb{Z}/NN_0\mathbb{Z}^*$ 和 $\mu_1' \in O_0$ 使得 $\mu = \lambda\mu' + NN_0\mu_1'$ 的范数为 $\ell^{e_2}$，其中 $e_2 \in \mathbb{N}$； 9. 返回 $\chi_L(\beta)$，其中 $\beta = \gamma\mu$。 该算法与[42]中算法的主要区别在于步骤8，这里的近似是模 $NN_0$ 进行的，$\lambda$ 的计算比[42]中步骤5更复杂。 ##### 2.3 相关引理 设 $O$ 和 $O_1$ 是 $B_{p,\infty}$ 中的两个非极端极大阶，其中 $p \equiv 3 \pmod{4}$ 或 $p \equiv 5 \p