计算机设计比赛就要弄完了，修改优化代码的日子要告一段落了。接下来准备迎接密码数学挑战赛，虽然我对密码学的学习还比较较有限，但我会尽我所能，尽可能地完成这次比赛。

竞赛官网：全国高校密码数学挑战赛

我选择的赛题是第二道题，”量子密码”这名字很吸引人，我也很想了解一下量子密码的相关知识。

让AI帮我梳理了一下题目，我发现题目中涉及到了很多数学的概念，比如环、多项式、同构、范数、汉明重量等。

RLWE 与 MLWE 密码学问题研究

数学基础

环与多项式环

  • 定义了 ( Zm = Z/mZ)，并在其上引入多项式环 ( Z_m[X])。对于多项式 ( f(X))，定义了商环 ( R{m,f} = Zm[X]/(f(X)))，并给出了同构映射 ( \Phi) 将 ( R{m,f}) 中的元素映射为 ( Z_m) 上的向量。
  • 在 ( Z^n) 和 ( Z{nm}) 上定义了范数，通过 ( \Phi) 扩展到 ( R{m,f}) 上，同时定义了元素的汉明重量 ( wt(a))，用于衡量 ( R_{m,f}) 中元素的大小。

密码学问题

  • RLWE 问题：给定 ( R_{m,f}) 中的元素 ( a(X))，存在秘密多项式 ( s(X)) 和误差多项式 ( e(X))，使得 ( t(X) = a(X)s(X) + e(X))，( t(X)) 公开而 ( s(X)) 需保密。
  • MLWE 问题：矩阵 ( A(X)) 的元素属于 ( R_{m,f})，存在秘密向量 ( s(X)) 和误差向量 ( e(X))，使得 ( t(X)^T = A(X)s(X)^T + e(X)^T)。

NIST 相关密码方案

  • Kyber：参数为 ( n = 256)，( q = 3329)，( f(X) = X^{256} + 1)，MLWE 参数 ((k, l)) 有多种组合。
  • Dilithium：参数为 ( q = 8380417)，MLWE 参数 ((k, l)) 也有多种组合。

实验参数设置

  • RLWE 问题实验：给出了不同的 ( n) 和 ( q) 值下的 RLWE 问题实例，对秘密多项式 ( s(X)) 和误差多项式 ( e(X)) 的取值范围进行了限制。
  • MLWE 问题实验：给出了 ( n = 256)，( q = 3329)，( f(X) = X^{256} + 1)，((k, l) = (2, 2)) 时的 MLWE 问题实例，对秘密向量 ( s(X)) 的取值范围进行了限制。

研究方案

研究目标

  • 深入理解 RLWE 和 MLWE 问题的数学原理和密码学应用。
  • 分析不同参数设置下 RLWE 和 MLWE 问题的安全性和效率。
  • 探索 RLWE 和 MLWE 问题在实际密码系统中的应用潜力。

研究方法

理论分析

  • 数学基础研究：研究环论、多项式环、同构映射。
  • 密码学原理分析：分析 RLWE 和 MLWE 问题的定义、安全性证明和密码学应用。

实验研究

  • 参数敏感性分析：改变 (n)、(q)、(f(X)) 等参数，研究其对 RLWE 和 MLWE 问题安全性和效率的影响。
  • 安全性评估：使用密码分析工具，评估不同参数设置下的 RLWE 和 MLWE 问题的安全性。
  • 效率测试：实现 RLWE 和 MLWE 问题的算法，测试时间复杂度和空间复杂度。

研究步骤

第一阶段：理论学习（第 1 - 2 周）

  • 学习环论、多项式环、同构映射等数学知识。
  • 研究 RLWE 和 MLWE 问题的定义、安全性证明和密码学应用。

第二阶段：实验准备（第 3 - 4 周）

  • 实现 RLWE 和 MLWE 问题的加密、解密和签名算法。
  • 搭建实验环境，准备实验数据。

第三阶段：实验研究（第 5 - 8 周）

  • 进行参数敏感性分析，记录实验结果。
  • 对不同参数设置下的 RLWE 和 MLWE 问题进行安全性评估和效率测试。

第四阶段：结果分析与总结（第 9 - 10 周）

  • 分析实验结果，总结不同参数设置下 RLWE 和 MLWE 问题的安全性和效率特点。
  • 撰写研究报告，提出研究结论和建议。

预期成果

  • 深入理解 RLWE 和 MLWE 问题的数学原理和密码学应用。
  • 分析不同参数设置下 RLWE 和 MLWE 问题的安全性和效率，为实际密码系统的设计提供参考。
  • 撰写研究报告，总结研究成果和发现。