格问题与格密码#

本主题以计算格筛法为主线，连接计算格问题与格密码，重点讨论多层分桶、参数优化、去重与覆盖、渐进加维及平台成本。

#内容导航

基础知识按内容分组，组内顺序供阅读参考。

#格几何

• 格与基本计算问题：格与格基、格行列式与正交化、逐次极小值与 Minkowski 定理、基本计算格问题。
• 对偶与转移：对偶格、覆盖半径与转移定理。

#格约化

• 从约化基到近似 CVP　LLL 格基约化算法通过尺寸约化和交换改善格基，并给出首向量的长度上界。Babai 最近平面算法使用 LLL 约化基逐层取整，近似求解最近向量问题。
• LLL 的精度控制　浮点误差对 LLL 判定的影响讨论工作精度怎样影响取整与交换。从高位近似基向原基传递换基矩阵讨论输入保留的高位，以及截断和列缩放后如何在原基上保证约化质量。
• 投影块上的两种局部任务　用块内换基更新原基在块内求整数幺模矩阵，再将其作用于原基的相应列。BKZ 通过局部 SVP 改进格基在块内寻找短向量及其整数系数，再提升并插入原基。

#高斯分析

离散高斯、傅里叶变换与 Poisson 求和、平滑参数。

#格密码

q 元格、SIS、LWE。

#格筛法

• 模型与基本机制：高斯启发式与随机球面模型、筛法框架与两向量约化、Nguyen–Vidick、ListSieve 与 GaussSieve。
• 近邻搜索：近邻搜索与分桶、角度 LSH、球面 LSF。
• 多层分桶与覆盖：BGJ 递归分桶、分桶参数优化、去重与有效覆盖。
• 渐进筛法与实现：渐进筛法与向量池复用、G6K 与 Pump、并行筛法与平台成本。

#研究增量

BGJ 筛法的流式访存组织归入格筛法专题，分析多层 BGJ 的批量扫描、子桶输出与分层访存及其证据范围。

#阅读路线

• 筛法主线： 格几何基础与基本计算问题 → LLL 与 Babai → 高斯启发式、投影格与 BKZ → 筛法框架及经典算法 → 近邻搜索、过滤与递归分桶 → 参数优化、覆盖与去重 → 渐进筛法、G6K/Pump 与平台成本 → 流式访存的研究增量。
• 现代 LLL 支线　精确 LLL 的约化条件和势函数 → 浮点数下的取整与交换 → 高位截断和列缩放后的换基传递 → 投影块内的局部换基。
• 格密码支线： 格几何基础 → LLL 与 Babai → 对偶格与转移定理 → 高斯分析 → q 元格、SIS 与 LWE → 困难性归约与 Regev 公钥加密。

伙伴搜索、过滤器、多层分桶、选参与去重构成筛法的搜索与覆盖基础；渐进筛法、G6K/Pump 和平台成本分析进一步连接格约化策略与具体实现。阅读流式访存的研究增量时，可以沿这些关联补齐前置知识。

#阅读来源

通用基础可沿 Regev 的课程阅读 [1]。也可结合 Micciancio 的课程补充 [2]。

G6K 将筛法的状态操作、动态提升与插入策略组织为可组合的接口 [3, secs. 3.2–3.3, 4.1]。阅读时区分证明、启发式分析和实验观察。

#参考文献