基于Weil配对的短签名方案解析

### 基于 Weil 对的短签名方案详解 #### 1. 具体短签名方案 我们采用从曲线 \(E/F_{3l}\)（由 \(y^2 = x^3 + 2x \pm 1\) 定义）导出的 GDH 组来构建具体的签名方案。为避免 Weil - 下降攻击，我们将 \(l\) 限制为素数。下面是一些有用的曲线实例： | 曲线 | \(l\) | 签名大小 \(\lceil\lg_2 m\rceil\) | DLog 安全 \(\lceil\lg_2 q\rceil\) | 安全乘数 \(\alpha\) | MOV 安全 \(\lceil\lg_2 x\rceil\) | | ---- | ---- | ---- | ---- | ---- | ---- | | \(E^-\) | 79 | 126 | 126 | 6 | 752 | | \(E^+\) | 97 | 154 | 151 | 6 | 923 | | \(E^+\) | 149 | 237 | 220 | 6 | 1417 | | \(E^+\) | 163 | 259 | 256 | 6 | 1551 | | \(E^-\) | 163 | 259 | 259 | 6 | 1551 | | \(E^+\) | 167 | 265 | 262 | 6 | 1589 | 该签名方案的具体步骤如下： - **密钥生成**： 1. 从表中选取一个 \(l\) 值，确定对应的曲线 \(E/F_{3l}\)。 2. 找到曲线阶的最大素因子 \(q\)。 3. 选取一个阶为 \(q\) 的点 \(P \in E/F_{3l}\)。 4. 随机选取 \(x \in Z_q^*\)，计算 \(R \leftarrow xP\)。 5. 公钥为 \((l, q, P, R)\)，私钥为 \(x\)。 - **签名**： 1. 对于消息 \(M \in \{0, 1\}^*\)，使用算法 \(MapToGroup_{h'}\) 将 \(M\) 映射到点 \(P_M \in \langle P \rangle\)。 2. 计算 \(S_M \leftarrow xP_M\)。 3. 签名 \(\sigma\) 为 \(S_M\) 的 \(x\) 坐标，即 \(\sigma \in F_{3l}\)。 - **验证**： 1. 找到阶为 \(q\) 且 \(x\) 坐标为 \(\sigma\) 的点 \(S \in E/F_{3l}\)，若不存在则拒绝签名。 2. 计算 \(u \leftarrow e(P, \varphi(S))\) 和 \(v \leftarrow e(R, \varphi(h(M)))\)，其中 \(e\) 是曲线 \(E/F_{3^{6l}}\) 上的 Weil 对，\(\varphi : E \to E\) 是曲线的自同构。 3. 若 \(u = v\) 或 \(u^{-1} = v\)，则接受签名，否则拒绝。 下面是该签名过程的 mermaid 流程图： ```mermaid graph TD; A[开始] --> B[密钥生成]; B --> C[签名]; C --> D[验证]; D --> E[结束]; ``` #### 2. 安全性分析 引理表明，如果没有算法能 \((t_0, \epsilon_0)\) - 破解 \(G = \langle P \rangle\) 上的计算 Diffie - Hellman 问题，那么上述具体签名方案在随机预言模型下对自适应选择消息攻击的存在性伪造是 \((t, q_H, q_S, \epsilon)\) - 安全的，其中： - \(t \leq t_0 - 2c_A(\lg q)(q_H + q_S) - 2Iq_H \lg m - 2\tau\) - \(\epsilon \geq 2e \cdot q_S\epsilon_0\) 证明过程通过将具体签名方案与通用 GDH 签名方案进行关联，并考虑了哈希函数的构造和模拟过程，最终得出所需的安全性约简。 #### 3. 高安全性短签名的开放问题 前面提出使用 \(F_{3l}^*\) 上的超奇异曲线构建短签名方案，其安全性与 \(F_{3^{6l}}^*\) 中的离散对数