超奇异同构签名方案（SQISign）及Deuring对应新算法解析

### 超奇异同构签名方案（SQISign）及Deuring对应新算法解析 #### 1. SQISign概述与效率分析 SQISign签名方案是基于交互识别协议，通过经典的Fiat - Shamir变换实现非交互性的签名方案。其整体效率受多个因素制约，当存在约束条件$\ell fT|(p^{2d} - 1)$（为追求最大效率，通常$d = 1$）时，找到使得$p^{2} - 1$有大光滑因子的素数$p$极为困难。 从效率提升角度看，将$T$从约$p^{3/2}$调整到约$p^{5/4}$是显著的改进。因为这样更有希望找到更适合SQISign的素数，即使使用相同的素数$p$，新算法也能带来一定程度的效率提升，原因在于可以忽略$T$的部分因子，并使用较小的自同态度$T'|T$。 #### 2. SQISign的安全性问题 在安全性方面，虽然容易证明识别方案是自同态知识的2 - 特殊可靠证明，但证明零知识属性却困难得多。De Feo等人不得不借助计算假设，即四元数路径查找算法SigningKLPT输出的理想与相同范数的均匀随机理想无法区分。 然而，研究发现该假设并不成立。因为构成响应同构的2 - 同构步的第一步在所有可能的第一步中并非均匀分布，SigningKLPT输出的理想$I$包含在一个范数为2且分布不均匀的理想中。这意味着可以以不可忽略的优势将SQISign签名与固定长度的随机2 - 同构步区分开来。这种偏差源于SigningKLPT的子算法RepresentInteger在特殊极大序$O_0$的子序中求解范数方程。 #### 3. 预备知识 - **基本定义**：在整个研究中，$p$是素数，$F_{p^2}$是大小为$p^2$的有限域。可忽略函数$f: Z_{>0} \to R_{>0}$的增长被$O(x^{-n})$（对所有$n > 0$）所界定。在概率算法分析中，若事件失败的概率是输入长度的可忽略函数，则称该事件以压倒性概率发生。 - **区分问题与计算不可区分性**：当任何概率多项式时间区分器相对于实例长度的优势可忽略时，称区分问题是困难的。若两个分布对应的区分问题困难，则称这两个分布在计算上不可区分。 #### 4. Deuring对应数学背景 - **椭圆曲线、同构与自同态**：椭圆曲线是维度为1的阿贝尔簇，同构是它们之间的非恒定态射。同构的度是其作为有理映射的度，若度等于其核的大小，则同构是可分的。对于椭圆曲线$E$的有限子群$G$，可关联一个核为$G$的可分同构$\phi: E \to E/G$，且该同构在目标的同构意义下是唯一的，可通过Vélu公式从核计算同构。从曲线$E$到自身的同构是$E$的自同态，与常数零映射一起构成环$End(E)$。在正特征下，$End(E)$要么同构于二次虚数域中的一个序，要么同构于四元数代数中的一个极大序。本文主要关注超奇异情况。 - **四元数代数、序与理想**：超奇异椭圆曲线在$F_{p^2}$上的自同态环同构于在$p$和$\infty$分歧的四元数代数$B_{p,\infty}$的极大序。固定$B_{p,\infty}$的一组基$1, i, j, k$，满足$i^{2} = -q$，$j^{2} = -p$，$k = ij = -ji$（$q$为正整数）。分数理想$I$是$B_{p,\infty}$内秩为四的$Z$ - 格，其范数$n(I)$定义为最大的有理数，使得对于任何$\alpha \in I$，$n(\alpha) \in n(I)Z$。序$O$是$B_{p,\infty}$的子环且为分数理想，当不包含在任何更大的序中时，称为极大序。 - **Deuring对应**：Deuring建立了椭圆曲线与四元数代数之间的联系，表明定义在$F_{p^2}$上的超奇异椭圆曲线$E$的自同态环同构于$B_{p,\infty}$中的一个极大序。固定超奇异椭圆曲线$E_0$和序$O_0 \simeq End(E_0)$，每个从$E_0$出发的同构$\phi: E_0 \to E_1$可关联一个整左$O_0$ - 理想，反之亦然。具体对应关系如下表所示： |超奇异$j$ - 不变量（$F_{p^2}$）|$B_{p,\infty}$中的极大序| | ---- | ---- | |$j(E)$（伽罗瓦共轭意义下）|$O \sim = End(E)$（同构意义下）| |$(E_1, \phi)$（$\phi: E \to E_1$）|$I_{\phi}$（整左$O$ - 理想且右$O_1$ - 理想）| |$\theta \in End(E_0)$|主理想$O\theta$| |$deg(\phi)$|$n(I_{\phi})$| |$\hat{\phi}$|$I_{\hat{\phi}}$| |$\phi: E \to E_1$，$\psi: E \to E_1$|等价理想$I_{\phi} \sim I_{\psi}$| |超奇异$j$ - 不变量（$F_{p^2}$）|$Cl(O)$| |$\tau \circ \rho: E \to E_1 \to E_2$|$I_{\tau \circ \rho} = I_{\rho} \cdot I_{\tau}$| |$N$ - 同构（同构意义下）|$Cl(O)$（$O$为水平为$N$的Eichler序）| #### 5. SQISign协议流程 - **初始化与密钥生成** - **setup**：选择素数$p$和定义在$F_{p^2}$上的超奇异椭圆曲线$E_0$，已知其特殊极值自同态环$O_0$。选择$\lambda$位的奇光滑数$D_c$和$D = 2^e$（$e$大于超奇异2 - 同构图的直径）。 - **keygen**：随机选择同构步$\tau: E_0 \to E_A$，得到随机椭圆曲线$E_A$。公钥为$E_A$，私钥为同构$\tau$。 - **交互协议流程** - **承诺阶段**：证明者生成随机（秘密）同构步$\psi: E_0 \to E_1$，并将$E_1$发送给验证者。 - **挑战阶段**：验证者向证明者发送度为$D_c$的循环同构$\phi: E_1 \to E_2$的描述。 - **响应阶段**：证明者从同构$\phi \circ \psi \circ \hat{\tau}: E_A \to E_2$构造一个度为$D$的新同构$\sigma: E_A \to E_2$，使得$\hat{