后量子数字签名技术解析

# 后量子数字签名技术解析 ## 1. 引言 随着量子计算技术的发展，传统数字签名方案面临着新的挑战。后量子数字签名技术旨在提供能够抵抗量子攻击的签名方案，保障信息安全。本文将介绍多种后量子数字签名方案，包括基于多变量二次（MQ）问题的签名方案、基于对称密钥技术的签名方案以及基于超奇异同源的签名方案。 ## 2. 基于MQ问题的签名方案 ### 2.1 Rainbow签名方案 Rainbow签名方案是一种多层油醋（UOV）签名方案，是NIST PQC竞赛第三轮的三个决赛方案之一。 - **变量分层**：将变量分为两层，每层包含醋变量和油变量。 - **密钥生成**： - 秘密密钥由两个可逆仿射映射 $\Sigma: \mathbb{F}_q^m \to \mathbb{F}_q^m$、$\mathrm{T}: \mathbb{F}_q^n \to \mathbb{F}_q^n$ 和中央二次映射 $\mathrm{F}: \mathbb{F}_q^n \to \mathbb{F}_q^m$ 组成，其中 $\mathrm{F}$ 由 $m$ 个多元多项式构成。 - 公共密钥是复合映射 $\mathrm{P} = \Sigma \circ \mathrm{F} \circ \mathrm{T}$，由 $m$ 个二次多项式组成。 - **签名过程**： 1. 计算消息 $d$ 的哈希值 $h = \mathrm{H}(d)$。 2. 计算 $x = \Sigma^{-1}(h)$。 3. 计算 $y = \mathrm{F}^{-1}(x)$。 4. 计算签名 $z = \mathrm{T}^{-1}(y)$。 - **验证过程**： 1. 计算消息 $d$ 的哈希值 $h = \mathrm{H}(d)$。 2. 计算 $h' = \mathrm{P}(z)$。 3. 如果 $h = h'$，则接受签名。 ### 2.2 LUOV签名方案 LUOV签名方案是从UOV派生的另一种MQ签名方案。它与标准UOV有以下三点不同： 1. 可以选择大部分公共密钥作为伪随机数生成器（PRNG）的输出，这部分可以用PRNG的种子表示。 2. 公共密钥 $\mathrm{P}: \mathbb{F}_q^n \to \mathbb{F}_q^m$ 被提升到扩展域 $\mathrm{P}^r: \mathbb{F}_q^n \to \mathbb{F}_q^m$。 3. 秘密映射 $\mathrm{T}$ 具有矩阵表示 $\begin{pmatrix} \mathrm{T}_v & \mathrm{m} \\ \mathrm{0} & \mathrm{1} \end{pmatrix}$，其中 $\mathrm{T}_v$ 是 $v \times m$ 矩阵。 由于该方案面临多种攻击，在NIST竞赛第二轮被淘汰。 ### 2.3 HFE签名方案 HFE签名方案基于MQ问题的陷门。其核心是Dembrowski - Ostrom多项式，定义如下： 设 $D > 0$ 为整数，多项式 $F(X) \in \mathbb{F}_{q^n}[X]$ 具有HFE形状，如果它的形式为： $F(X) = \sum_{0 \leq i < j \leq n, q^i + q^j \leq D} A_{ij} X^{q^i + q^j} + \sum_{0 \leq i \leq n, q^i \leq D} B_i X^{q^i} + C$ - **密钥生成**： - 选择一元多项式 $F$ 并设置扩展域算术的基。 - 选择混合方程和变量的 $S$ 和 $T$ 矩阵。 - 秘密密钥是 $(F, S, T)$，公共密钥是 $(f_1(x), \cdots, f_n(x)) \circ T \circ S$。 - **签名过程**： 1. 签名者对消息签名时，将哈希摘要在 $S^{-1}$ 下的原像（基域的 $n$ 元组）与扩展域中的元素进行标识。 2. 公共密钥系统重构为扩展域上的一元多项式，可在多项式时间内求解，该多项式的任何零点在应用 $T^{-1}$ 后用于获得签名。 - **验证过程**：在签名坐标处评估公共密钥系统，并检查是否与哈希摘要相等。 ### 2.4 GeMSS签名方案 GeMSS是HFE范式中的一种签名方案，特别是其“v - minus变体”。 - **参数设置**：包括秘密多项式的度数 $D$、醋变量的数量 $v$、公共密钥中的方程数量 $m$、哈希摘要的大小 $K$、有限域的扩展度数 $n$ 等。 - **密钥生成**：输入安全参数 $\lambda$，秘密密钥是 $(F, S, T)$，公共密钥是 $p$。 - **签名过程**： 1. 使用SHA3计算消息的摘要。 2. 重复以下步骤直到找到根： - 计算 $H = \mathrm{SHA3}(M)$。 - 随机选择 $r \in \mathbb{F}_2^{n - m}$，$S_0 = \mathrm{0} \in \mathbb{F}_2^m$，$d' = d || r$。