3.1.2 Ajtai 归约：从 SVP 到 SIS

文档摘要

3.1.2 Ajtai 归约：从 SVP 到 SIS 3.1.2 Ajtai 归约：从 SVP 到 SIS —— 一线工程师手记：如何把最坏情况的格难题，稳稳“嫁接”到平均情况的随机实例上你有没有试过，在深夜调试一个格密码模块时，突然意识到：我们天天用的 LWE 加密、基于 SIS 的签名方案，其安全性证明里反复出现的那个“假设 SVP 在最坏情况下难解”，其实和你生成的那批随机矩阵 $ \mathbf{A} \in \mathbb{Z}q^{n \times m} $ 并无直接关系？ ——它不来自某个特定格基，而来自一个统计分布；它不依赖于某条特别刁钻的最短向量，而仰赖于绝大多数随机实例都难以求解这一事实。那么问题来了：这个“绝大多数”凭什么可信？