密码数学竞赛笔记

密码数学赛题2：前往下载

一. 题目解析

文档涉及的数学概念解释如下：

1. 整数模 $ m $ 剩余类环 $\mathbb{Z}_m$

  • 定义：由整数模 $ m $ 的剩余类构成，即 $ \mathbb{Z}_m = {0, 1, \dots, m-1} $。
  • 运算：加法和乘法均在模 $ m $ 下进行。例如，在 $ \mathbb{Z}_5 $ 中，$ 3 + 4 = 2 $（因为 $ 7 \mod 5 = 2 $）。
  • 用途：密码学中常用于限制数值范围，确保计算在有限域内进行。

2. 多项式环 $ \mathbb{Z}_m[X] $

  • 定义：系数属于 $ \mathbb{Z}m $ 的多项式集合，例如 $ a(X) = a_0 + a_1X + \cdots + a{n-1}X^{n-1} $，其中 $ a_i \in \mathbb{Z}_m $。
  • 运算：多项式加法和乘法，系数运算遵循模 $ m $ 规则。

3. 商环 $ R_{m,f} = \mathbb{Z}_m[X]/(f(X)) $

  • 生成方式：取 $ \mathbb{Z}_m[X] $ 模去一个首一多项式 $ f(X) $ 生成的主理想 $ (f(X)) $。
  • 元素表示：每个剩余类是次数小于 $ n $ 的多项式，例如 $ R{m,f} $ 中的元素可表示为 $ a_0 + a_1X + \cdots + a{n-1}X^{n-1} $。
  • 同构映射 $ \Phi $：将多项式映射到其系数向量 $ (a0, a_1, \dots, a{n-1}) $，保持加法结构（Abel 群同构）。

4. 2-范数与 ∞-范数

  • 定义：
    • 2-范数：对 $ a \in \mathbb{Z}_m^n $，找到整数向量 $ b $ 满足 $ \Pi(b) = a $，取 $ |b|_2 = \sqrt{\sum b_i^2} $ 的最小值。
    • ∞-范数：类似地，取 $ |b|_\infty = \max |b_i| $ 的最小值。
  • 短多项式：范数较小的多项式，对应格密码中的“小错误”或“小密钥”，是安全性的核心。

5. RLWE问题

  • 问题描述：给定环 $ R_{m,f} $、随机多项式 $ a(X) $ 和目标 $ t(X) $，求解 $ s(X) \in C $ 和短错误 $ e(X) $，使得：
    [ t(X) = a(X) \cdot s(X) + e(X) \mod (f(X), m). ]
  • 条件子集 $ C $：限制 $ s(X) $ 的范数或汉明权重（如 $ |s(X)|_2 < 10 $ 或 $ wt(s(X)) \leq 3 $），增加问题难度。

6. MLWE问题

  • 推广形式：使用矩阵和向量推广 RLWE。给定矩阵 $ A(X) \in R_{m,f}^{k \times l} $ 和目标向量 $ t(X) $，求解私密向量 $ s(X) \in C $ 和错误向量 $ e(X) $，使得：
    [ t(X)^T = A(X) \cdot s(X)^T + e(X)^T \mod (f(X), m). ]
  • 参数 $ (k, l) $：例如 Kyber 中 $ (k,l) = (2,2) $，不同安全级别对应不同维度。

7. NIST 后量子密码标准

  • Kyber：基于 MLWE，参数为 $ q = 3329 $、$ n = 256 $、$ f(X) = X^{256} + 1 $。
  • Dilithium：基于 MLWE，模数更大（$ q = 8380417 $），适用于数字签名。
  • 中心二项分布：生成短多项式（私钥和错误项），保证问题困难性。

8. 主理想 $ (a(X)) = R_q $ 的概率

  • 条件：当且仅当 $ a(X) $ 在 $ R_q $ 中可逆。
  • 计算：概率 $ p $ 取决于 $ R_q $ 中可逆元素的比例。对于 $ R_q = \mathbb{Z}_q[X]/(X^n + 1) $，若 $ q $ 为素数且 $ X^n + 1 $ 在 $ \mathbb{Z}_q $ 上可分解为不同不可约因子，则概率为 $ \phi(q^n)/q^n $，其中 $ \phi $ 为欧拉函数。

9. 格密码与安全性

  • 困难假设：RLWE/MLWE 的困难性基于格中最短向量问题（SVP）的难解性。
  • 实际应用：短错误和私钥使得攻击者难以从 $ t(X) $ 中分离出 $ s(X) $ 和 $ e(X) $，保障后量子密码方案（如 Kyber、Dilithium）的安全性。

小结

考题结合了抽象代数（环、理想、范数）与密码学（LWE 问题变种、后量子密码设计），核心是通过短多项式在环结构中的运算困难性构建安全方案。参赛者需深入理解这些概念，并设计算法求解特定条件下的 RLWE/MLWE 实例。