赛题文档的 markdown 格式
假设$m, n$是正整数，
是整数模$m$剩余类环，$Z_m[X]$是$Z_m$上单变元多项式环。
取定$Z_m[X]$中一个$n$次首一多项式$f(X)$，记$(f(X))$是由$f(X)$生成的$Z_m[X]$的主理想。定义环
这样，我们可以构造一个双射
显然，$\Phi$是一个Abel群同构。
设$\Pi$是下面的自然映射
定义$Z_m^n$中元素$a = (a_0, \cdots, a_{n-1})$的$2$-范数和$\infty$-范数分别为
$$ |a|_2 = \min \left{ |b|2 = \sqrt{\sum{i=0}^{n-1} b_i^2} \mid b \in \mathbb{Z}^n, \Pi(b) = a \right}, $$
$$ |a|\infty = \min{|b|\infty = \max{|b_i| \mid 0 \leq i \leq n-1} \mid b \in \mathbb{Z}^n, \Pi(b) = a}. $$
利用同构$\Phi$，对$R_{m,f}$中多项式$a(X)$，定义其$2$-范数和$\infty$-范数分别为
$$ |a(X)|2 = |\Phi(a(X))|2, \quad |a(X)|\infty = |\Phi(a(X))|\infty. $$
我们称$R_{m,f}$中$2$-范数或$\infty$-范数较小的多项式为短多项式。
对$a = (a_0, \cdots, a_{n-1}) \in Z_m^n$，定义
相应的，对$a(X) \in R_{m,f}$，定义
定义1（条件RLWE问题）给定环$R_{m,f}$和$R_{m,f}$的一个(条件)子集$\mathcal{C}$。在$R_{m,f}$中随机选取元素$a(X)$，给定目标多项式$t(X) \in R_{m,f}$，求取私密多项式$s(X) \in \mathcal{C}$和短的错误多项式$e(X) \in R_{m,f}$，使得
定义2（条件MLWE问题）给定环$R_{m,f}$，正整数对$(k, l)$和$(R_{m,f})^l$的(条件)子集$\mathcal{C}$。随机选取系数为$R_{m,f}$中元素的$(k \times l)$阶矩阵$A(X) = (A_{ij}(X)){0 \leq i \leq k-1, 0 \leq j \leq l-1}$，给定目标多项式向量$t(X) = (t_0(X), \cdots, t{k-1}(X)) \in (R_{m,f})^k$，求取私密多项式组$s(X) = (s_0(X), \cdots, s_{l-1}(X)) \in \mathcal{C}$，
和短的错误多项式组$e(X) = (e_0(X), \cdots, e_{k-1}(X)) \in (R_{m,f})^k$，使得
其中$T$表示坐标分量为$R_{m,f}$的行向量的转置。
RLWE和MLWE问题是格中LWE问题在与环$R_{m,f}$相关的格上的一种推广。2024年美国国家标准与技术研究院(NIST)颁布的后量子密码标准中，多个算法都采用了这两个问题或其变形作为基础困难性问题。例如：
- 在NIST后量子密码标准Crystals系列算法中，固定选取$n = 256$，首一多项式$f(X) = X^{256} + 1$。相应的，私密多项式(组)和错误多项式(组)的系数由不同参数的中心二项分布/期望为$0$的二项分布中随机采样得到。
- 在Kyber中，模数$m$取素数$q = 2^8 \cdot 13 + 1 = 3329$，对应的MLWE问题，不同安全级别参数选取为$(k, l) \in {(2, 2), (3, 3), (4, 4)}$。
- 在Dilithium中，模数$m$取素数$q = 2^{23}-2^{13}+1 = 8380417$，对应的MLWE问题，不同安全级别参数选取为$(k, l) \in {(4, 4), (6, 5), (8, 7)}$。
本赛题评分分为下面三个部分：
-
(20分) 固定$n = 256$,
$q = 3329$ , 环$R_q = \mathbb{Z}_q[X]/(X^n + 1)$。在$R_q$中按均匀分布随机选取元素$a(X)$，给出主理想$(a(X))$等于$R_q$的概率$$ p = \text{Prob}{(a(X)) = R_q}. $$
-
构建求解RLWE和MLWE问题的模型，尝试求解下面给出的条件RLWE问题(1)-(7)和条件MLWE问题(8)中的私密多项式(组)$s(X)$和错误多项式(组)$e(X)$。如没有求解出答案，可以尝试分析的求解所需的计算复杂度(数据见赛题后附录)。
(1)
$R_{q,f}$ 上条件RLWE问题(15分) 参数$n = 64$,$q = 3329$ ,$f(X) = X^n + 1$ 。私密多项式$s(X)$满足的条件$$ \mathcal{C} = {s(X) \in R_{q,f} \mid |s(X)|_2 < 10}. $$
(2)
$R_{q,f}$ 上条件RLWE问题(15分) 参数$n = 64$,$q = 3329$ ,$f(X) = X^n + 1$ 。私密多项式$s(X)$满足的条件$$ \mathcal{C} = {s(X) \in R_{q,f} \mid \text{wt}(s(X)) \leq 3}. $$
(3)
$R_{q,f}$ 上条件RLWE问题(20分) 参数$n = 96$,$q = 3329$ ,$f(X) = X^n + 1$ 。私密多项式$s(X)$满足的条件$$ \mathcal{C} = {s(X) \in R_{q,f} \mid |s(X)|_2 < 10}. $$
(4)
$R_{q,f}$ 上条件RLWE问题(20分) 参数$n = 128$,$q = 3329$ ,$f(X) = X^n + 1$ 。私密多项式$s(X)$满足的条件$$ \mathcal{C} = {s(X) \in R_{q,f} \mid |s(X)|_2 < 12}. $$
(5)
$R_{q,f}$ 上条件RLWE问题(20分) 参数$n = 128$,$q = 3329$ ,$f(X) = X^n + 1$ 。私密多项式$s(X)$满足的条件$$ \mathcal{C} = {s(X) \in R_{q,f} \mid |s(X)|_2 < 14}, $$
而错误多项式$e(X)$满足$|e(X)|_2 < 3$。
(6)
$R_{q,f}$ 上条件RLWE问题(25分) 参数$n = 256$,$q = 3329$ ,$f(X) = X^n + 1$ 。私密多项式$s(X)$满足的条件$$ \mathcal{C} = {s(X) \in R_{q,f} \mid |s(X)|_2 < 16}. $$
(7)
$R_{q,f}$ 上条件RLWE问题(25分) 参数$n = 256$,$q = 3329$ ,$f(X) = X^n + 1$ 。私密多项式$s(X)$满足的条件$$ \mathcal{C} = {s(X) \in R_{q,f} \mid |s(X)|2 < 11, |s(X)|\infty \leq 1}. $$
(8)
$R_{q,f}$ 上条件MLWE问题(25分) 参数$n = 256$,$q = 3329$ ,$f(X) = X^n + 1$ 。$(k, l) = (2, 2)$私密多项式$s(X) = (s_1(X), s_2(X))$满足的条件
$$ \mathcal{C} = {s(X) \in (R_{q,f})^2 \mid |s_i(X)|_2 < 25, i = 0, 1}. $$
-
创新性(40分)：该部分得分主要依据参赛选手是否采用了有别于现有求解RLWE问题和MLWE问题方法的创新思维和技巧，或对现有方法在性能方面的有所提升。
为了应对大尺度量子计算机对传统公钥密码安全性带来的威胁，密码学家设计了基于量子计算下困难问题的后量子密码体制，用以替代基于传统公钥密码的对称密钥封装、数字签名等功能。
美国国家标准与技术研究院(NIST)从2016年开始面向全球征集后量子密码标准。经过几个轮次的筛选后，2024年8月，NIST公布了联邦信息处理标准(FIPS) 203[1], 204[2], 205，作为首批后量子密码体制的标准。其中基于格格问题的密钥封装和数字签名标准FIPS 203和FIPS 204 分别是基于MLWE问题的公钥密码体制Crystals-Kyber和Crystals-Dilithium。
上面NIST基于格的后量子密码标准化体制的理论安全性由其底层MLWE问题的计算困难性所保证，有关LWE问题的计算复杂度及其求解方法可见参考文献[3]。而在MLWE问题的实例中，私密多项式和错误多项式的选取是影响问题求解难度的重要因素。此外，密码应用的具体环境中也存在很多降低密码安全性的可能性，例如随机数发生器的脆弱性、侧信道泄露、密钥素材未及时销毁，等问题都可能是影响此类密码实际安全的重要因素。
本赛题设计了对条件RLWE和MLWE问题若干变形，希望参赛队伍通过对这些问题的分析求解，分析NIST基于格的后量子标准算法的安全性，寻找可能的体系漏洞。在此基础上，掌握现有格算法的求解能力，提高格算法针对RLWE问题的求解效率，推动后量子密码分析方法的研究，对后量子密码体制的安全性做出更加全面的评价。
[1] National Institute of Standards and Technology (2024): Module-Lattice-Based Key-Encapsulation Mechanism Standard. (U.S. Department of Commerce, Washington, DC), Federal Information Processing Standards Publication (FIPS) 203. This publication is available free of charge from: https://doi.org/10.6028/NIST.FIPS.203
[2] National Institute of Standards and Technology (2024): Module-Lattice-Based Digital Signature Standard. (U.S. Department of Commerce, Washington, DC), Federal Information Processing Standards Publication (FIPS) 204. This publication is available free of charge from: https://doi.org/10.6028/NIST.FIPS.204
[3] Report on the Security of LWE: Improved Dual Lattice Attack, The Center of Encryption and Information Security – MATZOV, IDF.
未核对, 建议使用时自行与官方 PDF 核对
(1)