按理论脉络组织：形式化证明 → 格理论 → LWE/PQC → 格攻击方法。

可证明安全框架

参考：Boneh-Shoup Ch.1–2 · Katz-Lindell

• 归约：若多项式时间敌手 A 攻破方案 Π，则可构造 B 解决困难问题 L
• 安全游戏：敌手与挑战者交互；优势 Advantage = |Pr[win] - 1/2|
• ROM：哈希建模为随机 oracle；标准模型不依赖此理想化
• 混合论证：Game-hopping 逐步将真实游戏变为平凡游戏

典型归约链

• IND-CPA 加密 → 单向置换 / DDH 假设
• RSA-OAEP → RSA 问题 + ROM
• 格签名 → SIS / LWE 困难性

格理论基础

参考：CTF Wiki · 格概述

• 格：基向量 b₁,…,bₙ 的整数线性组合；格点 L(B) = {Σ xᵢbᵢ}
• 行列式 det(L)：基变换不变量
• SVP：最短向量问题；CVP：最近向量问题
• LLL：多项式时间求 2^{n/2} 近似最短向量
• BKZ：块规约；实际安全估计的核心工具

经典格密码

• GGH：基于 CVP 困难性；密钥是「好基」
• NTRU：多项式环 Z[x]/(x^n-1)；与 Ring-LWE 相关

LWE 与后量子

参考：NIST PQC · Regev 2005

• LWE：给定 (A, b = As + e mod q)，求秘密 s；e 为小误差
• Ring-LWE：环上 LWE；NTRU、Kyber 基础
• Regev 加密：理解格公钥加密的入口方案
• 格签名：GPV 框架；Fiat-Shamir with aborts
• FHE 起步：BGV/BFV 基于 Ring-LWE；Bootstrapping 刷新噪声

与 ZK 的连接

• Sigma 协议 → Fiat-Shamir → 格上零知识证明
• 读 SNARK 前建议先掌握 Sigma 协议与承诺方案

教材：Boneh-Shoup Ch.17–20

格攻击方法

参考：CTF Wiki · 格基规约

• 构造格：将攻击条件转化为格中的短向量问题
• LLL/BKZ：规约基，取最短向量或最近向量
• Coppersmith：求模多项式小根；与格方法互补
• 应用场景：ECDSA 坏 nonce、Knapsack、RSA 部分已知明文

练习：CTF 格题从建格到出 flag 完整走一遍。

工具与实践

工具	用途
SageMath	格构造、LLL/BKZ、Coppersmith
fpylll	Python 高性能格基规约
lattice-rs	Rust 格算法试验
liboqs-rust	生产 PQC 集成

<p class="kb-note-inline">本站笔记 <span class="crypto-pending">待撰写</span>。</p>