从传统公钥密码到 LWE
如今我们日常使用的主流公钥密码体系（比如 RSA、Diffie–Hellman、椭圆曲线密码 ECC），背后依赖的核心困难问题大多是两类：
Factorization（大整数分解）：RSA 的安全性基础Discrete Logarithm（离散对数）：DH / ECC 的安全性基础
在经典计算机上，这两类问题目前都没有已知的多项式时间算法，因此它们在过去几十年里支撑了几乎整个互联网的密钥交换与身份认证体系。
但问题出在这些年的新研究：量子计算。
一旦具备足够规模、容错能力的量子计算机，Shor 算法可以在多项式时间内求解整数分解和离散对数——也就是说，RSA/DH/ECC这些传统公钥加密方法将会失去安全性。为了应对这种潜在威胁，我们需要寻找一类在量子模型下仍然被认为困难的数学问题，这就是所谓的 Post-Quantum Cryptography（后量子密码）。
在候选的后量子方向里，格（Lattice） 密码学是最重要的一支。
格可以简单理解成是这样的集合：
格上有一些非常自然但又非常难的问题，比如：
- 找到某个格里最短的非零向量（SVP 类问题）
- 在某种近似意义下找“足够短”的向量（GapSVP/SIVP 等）
这类问题的特点是：
- 目前没有已知的像Shor高效一样的量子算法能解决，
- 更关键的是，很多格密码构造能给出非常强的理论背书：把“平均情况下随机实例的困难性”与“最坏情况下格问题的困难性”联系起来（worst-case → average-case 的味道）
换句话说：攻击者不是只需要碰到一个弱实例，而是被迫面对一种更“结构性”的困难来源。
那么我们该怎么样利用格的特殊复杂性来设计一些更具体的问题，并在此基础上设计加密流程呢？
一个非常成功的实现便是LWE（Learning With Errors，带误差学习）。
LWE
相信大家都学过，这样的一个线性方程组：
其中$b \in \mathbb{Z}^n, A \in \mathbb{Z}^{n \times m}$已知 , $s \in \mathbb{Z}^m$未知，可以利用高斯算法或者很多其他的numerical的算法高效地解出来。
而LWE的想法便是在右边加上一个随机的error $e \in \mathbb{Z}^m$：
这样一来就很难通过这些等式准确地求出来s。
并且它非常符合公钥加密的特点：我们有一个密钥（这里是$s$），然后我们进行一番操作得到一个公钥（这里是$A,b$）。但是其他人无法通过公钥将密钥还原出来。
Regev LWE Public-Key Encryption
这个加密方案是由Oded Regev在2005 年提出的，出自他在ACM STOC 2005的论文 “On lattices, learning with errors, random linear codes, and cryptography”。
整体加解密流程：（q为任意质数）
生成密钥：
生成一个随机的矩阵$A \in \mathbb{Z}^{n \times m}_q$，公钥。
生成一个随机向量$s \in \mathbb{Z}^m_q$，私钥
计算公钥$b \in \mathbb{Z}^n_q$：
这里$e$是一个误差向量(Error)，系数非常小的向量。
加密：
生成一个一次性的小系数的随机向量$r$
计算密文$u$ ：
计算密文$v$：
这一步对二进制消息$m$的处理是为了尽量将$m$中的0，1区分开。
密文：$(u,v)$
解密：
- 计算因为$e,r$（的系数）都足够小，所以根据结果一位一位来还原$m$（离0更近返回0，离$\lfloor q/2 \rfloor$更近就返回1。）
