格密码系统和传统公钥密码系统的对比

Lattice-based Crypto	Standard Crypto
可证明安全	不总是可证明安全的
最坏情况下困难问题	平均情况下困难问题
格困难问题	整数分解、离散对数
抗量子攻击	不抗量子攻击
简单的加法计算	乘法、指数运算

可证明安全

安全性证明

• 安全性证明是从解决困难问题到攻破密码学方案的规约。
• 为密码学方案没有基础性缺陷提供证据。
• 为参数选择提供依据。

平均情况困难性：破解RSA并不意味着能分解所有的整数，只意味着可以分解某个特定的整数。（平均情况下整数分解是困难的）

最坏情况困难性：

格的定义

定义1. 格是线性无关的向量的全部整数组合。
L = { a 1 v ⃗ 1 + ⋯ + a n v ⃗ n ∣ a i ∈ Z } L=\{a_1\vec{v}_1+\cdots + a_n\vec{v}_n | a_i \in \mathbb{Z}\} L={a1​v 1​+⋯+an​v n​∣ai​∈Z}
定义2. 格是 R n \mathbb{R}^n Rn 下的离散加法子群。

格与基

给定两个基，怎样判断他们是否对应同样的格?
如下操作不改变格本身：

• 交换基中向量 （ v ⃗ i ↔ v ⃗ j \vec{v}_i \leftrightarrow \vec{v}_j v i​↔v j​）
• 对基向量进行取反操作 （ v ⃗ i → − v ⃗ i \vec{v}_i \to -\vec{v}_i v i​→−v i​）
• 一个基向量的整数倍加到另一个基向量上 （ v ⃗ i ← v ⃗ i + k v ⃗ j \vec{v}_i \leftarrow \vec{v}_i + k\vec{v}_j v i​←v i​+kv j​）

上述操作等价于对格基 B B B 右乘酉矩阵 U U U （ ∣ U ∣ = ± 1 |U|=\pm 1 ∣U∣=±1）。
两个基 B 1 , B 2 B_1,B_2 B1​,B2​ 相等，当且仅当 B 2 = B 1 U B_2=B_1U B2​=B1​U。

平行多面体

基向量的线性组合，系数取值为 0 0 0 到 1 1 1 构成的区域称为平行多面体。
P ( B ) = { a 1 b ⃗ 1 + ⋯ + a n b ⃗ n ∣ a i ∈ [ 0 , 1 ) } P(B)=\{a_1\vec{b}_1 + \cdots + a_n\vec{b}_n | a_i \in [0,1)\} P(B)={a1​b 1​+⋯+an​b n​∣ai​∈[0,1)}
如果 x ⃗ = a 1 b ⃗ 1 + ⋯ + a n b ⃗ n \vec{x}=a_1\vec{b}_1 + \cdots + a_n\vec{b}_n x =a1​b 1​+⋯+an​b n​，则
x ⃗   m o d   P ( B ) : = ( a 1   m o d   1 ) b ⃗ 1 + ⋯ + ( a n   m o d   1 ) b ⃗ n \vec{x}\bmod P(B):=(a_1 \bmod 1) \vec{b}_1 + \cdots + (a_n \bmod 1) \vec{b}_n x modP(B):=(a1​mod1)b 1​+⋯+(an​mod1)b n​

通过模 P ( B ) P(B) P(B) 可以确定点和格之间的关系。点在格上当且仅当点模 P ( B ) P(B) P(B) 后得到的点是 0 0 0 点。（平行多面体中仅存在一个格点—— 0 0 0 点）。

• 一个格会有很多基本区域（fundamental region），并不是所有的基本区域都是平行多面体。
• 在一个基本区域中，不存在两个等价的空间点。一个基本区域只包含每个陪集中的一个代表。
• 同一个格对应的平行多面体的体积相同。
• 可以把一个平行多面体内部的点一一映射到另一个平行多面体。
• 格基的行列式的绝对值本质上是平行多面体的体积，表明了格点的密度。
• L ( B ) L(B) L(B) 的行列式 d e t ( L ) = ∣ d e t ( B ) ∣ det(L)=|det(B)| det(L)=∣det(B)∣ （基向量构成的平行多面体的体积）
  ∣ d e t ( B U ) ∣ = ∣ d e t ( B ) d e t ( U ) ∣ = ∣ d e t ( B ) ∣ |det(BU)|=|det(B)det(U)|=|det(B)| ∣det(BU)∣=∣det(B)det(U)∣=∣det(B)∣
• 行列式 = 基本平行多面体的体积 = 格点密度的倒数

连续极小（Successive Minima）

λ 1 ( L ) \lambda_1(L) λ1​(L) 表示 L L L 中最短非零向量的长度（ L 2 L_2 L2​ 范数）
（最短向量一般有多个，如 v ⃗ \vec{v} v 和 − v ⃗ -\vec{v} −v ）
Z n \mathbb{Z}^n Zn 格中有 2 n 2n 2n 个最短向量（每个轴上有 2 2 2 个）

λ k ( L ) ( k ∈ [ 1 , n ] \lambda_k(L) (k\in [1,n] λk​(L)(k∈[1,n]）：包含 k k k 个线性无关的向量的最小球的半径（ n n n表示格的维度）。

λ n \lambda_n λn​： n n n 个线性无关向量的半径。 （包含了整个 n n n 维线性空间的基，也对应格的基）

Gram-Schmidt 正交化

给定一组有序向量 v 1 , ⋯   , v n v_1,\cdots,v_n v1​,⋯,vn​ Gram-Schmidt 正交化的过程就是把每一个向量向前一个向量的正交空间投影，得到一组正交的向量 v ~ 1 , ⋯   , v ~ n \tilde{v}_1,\cdots, \tilde{v}_n v~1​,⋯,v~n​.（正交化后得到的向量不一定在格点上）

将得到的正交向量进行规范化得到正交基：
v ~ 1 ∣ ∣ v ~ 1 ∣ ∣ , ⋯   , v ~ n ∣ ∣ v ~ n ∣ ∣ \frac{\tilde{v}_1}{||\tilde{v}_1||}, \cdots, \frac{\tilde{v}_n}{||\tilde{v}_n||} ∣∣v~1​∣∣v~1​​,⋯,∣∣v~n​∣∣v~n​​

因此 v 1 , ⋯   , v n v_1,\cdots,v_n v1​,⋯,vn​ 在这组基下可以写成如下形式:

[ ∣ ∣ v ~ 1 ∣ ∣ ∗ ⋯ ∗ 0 ∣ ∣ v ~ 2 ∣ ∣ ⋯ ∗ ⋮ ⋮ ⋱ ⋮ 0 0 ⋯ ∣ ∣ v ~ n ∣ ∣ ] (QR 分解) \begin{bmatrix} ||\tilde{v}_1|| & * & \cdots & * \\ 0 & ||\tilde{v}_2|| & \cdots & * \\ \vdots & \vdots & \ddots &\vdots \\ 0 & 0 & \cdots & ||\tilde{v}_n|| \end{bmatrix} \tag{QR 分解} ⎣⎢⎢⎢⎡​∣∣v~1​∣∣0⋮0​∗∣∣v~2​∣∣⋮0​⋯⋯⋱⋯​∗∗⋮∣∣v~n​∣∣​⎦⎥⎥⎥⎤​(QR 分解)

v 2 v_2 v2​ 在 v ~ 1 \tilde{v}_1 v~1​ 和 v ~ 2 \tilde{v}_2 v~2​ 的生成空间中。

通过下面两个引理很容易证明 Gram-Schmidt box 是一个基本区域。

• 引理 1：由 v 1 , ⋯   , v n v_1,\cdots,v_n v1​,⋯,vn​ 生成的格的行列式为 ∏ ∣ ∣ v ~ i ∣ ∣ \prod ||\tilde{v}_i|| ∏∣∣v~i​∣∣ .
• 引理 2： λ 1 ≥ m i n ∣ ∣ v ~ i ∣ ∣ \lambda _1 \ge min ||\tilde{v}_i|| λ1​≥min∣∣v~i​∣∣.

格是这个矩阵列向量的整数组合，所以这个矩阵的列向量生成了格，这种表示方法只是把格基旋转了一下，本质上没有改变基。如果在最右边的列向量使用一个非 0 0 0 系数，那么这个格向量的长度最短也至少为 ∣ ∣ v ~ n ∣ ∣ ||\tilde{v}_n|| ∣∣v~n​∣∣ （等号的情况为 ∣ ∣ v ~ n ∣ ∣ ||\tilde{v}_n|| ∣∣v~n​∣∣ 上方元素全为 0 0 0 ），对于其他列同理，因为至少有一列的系数不为 0 0 0，因此 引理 2 成立。

从而得到了 λ 1 \lambda _1 λ1​ 的下界。

Minkowski 定理

Blichfeld 定理：对任意格 Λ \Lambda Λ 和体积大于 d e t ( Λ ) det(\Lambda) det(Λ) 的集合 S S S，可以找到两个点 z 1 , z 2 ∈ S , z 1 ≠ z 2 z_1,z_2\in S, z_1 \neq z_2 z1​,z2​∈S,z1​​=z2​，使得 z 1 − z 2 ∈ Λ z_1-z_2\in \Lambda z1​−z2​∈Λ（即 z 1 − z 2 z_1-z_2 z1​−z2​ 为格点）。
Minkowski 定理：对任意格 Λ \Lambda Λ 和关于原点对称的凸区域 S S S（如果 x x x 在 S S S 中，那么 − x -x −x 也在 S S S 中，即 S = − S S=-S S=−S），如果 S S S 的体积大于 2 n d e t ( Λ ) 2^ndet(\Lambda) 2ndet(Λ)，那么在 S S S 中一定存在一个非 0 0 0 格点。
(如果不是凸区域，可以在格点的空隙中构造足够大的区域满足上述条件。如果不要求关于原点对称，可以构造一个足够“高”的图形满足上述条件。）

证明：
取一个集合，相对 S S S 在每一个维度缩小 1 2 \frac{1}{2} 21​，称为 S 2 \frac{S}{2} 2S​。
由于 S 2 \frac{S}{2} 2S​ 是在每个维度都缩小了 1 2 \frac{1}{2} 21​，因此其体积是 S S S 的 1 2 n \frac{1}{2^n} 2n1​。
由于 S S S 的体积大于 2 n d e t ( Λ ) 2^ndet(\Lambda) 2ndet(Λ)，从而得到 S 2 \frac{S}{2} 2S​ 的体积大于 d e t ( Λ ) det(\Lambda) det(Λ)。
因此根据 Blichfeld 定理 可以在 S 2 \frac{S}{2} 2S​ 中找到两个点 z 1 , z 2 z_1,z_2 z1​,z2​ 使得他们的差为格点。
由于 z 1 , z 2 z_1,z_2 z1​,z2​ 在 S 2 \frac{S}{2} 2S​ 中，因此 2 z 1 , − 2 z 2 2z_1,-2z_2 2z1​,−2z2​ 在 S S S 中（关于原点对称），因为 S S S 是凸集合，所以 2 z 1 , − 2 z 2 2z_1,-2z_2 2z1​,−2z2​ 的平均数（ z 1 − z 2 z_1-z_2 z1​−z2​）也在 S S S 中，得证。

推论：对任意格 Λ \Lambda Λ 都有
λ 1 ( Λ ) ≤ n ⋅ d e t ( Λ ) 1 n \lambda _1(\Lambda) \leq \sqrt{n}\cdot det(\Lambda)^{\frac{1}{n}} λ1​(Λ)≤n ​⋅det(Λ)n1​
此处 1 n \frac{1}{n} n1​ 为放缩系数，例如，如果 Λ \Lambda Λ 放大 10 10 10 倍，那么不等式左边相应地放大了 10 10 10 倍，这时候需要不等式右边也放大同样的倍数，而右边是 Λ \Lambda Λ 的行列式，根据行列式的性质右边放大了 1 0 n 10^n 10n 倍，因此需要放缩系数 1 n \frac{1}{n} n1​ 来平衡放缩的倍数。

对于任意行列式为1的格，一定有一个长度不超过 n \sqrt{n} n ​ 的格向量。
证明：
取一个半径为 n \sqrt{n} n ​ 的球，那么这个球的体积大于 2 n 2^n 2n，对于任意一个行列式为 1 1 1 的格，球中一定包含一个格点，根据定义，这个格点对应的格向量的长度一定小于球的半径 n \sqrt{n} n ​。

为什么球的体积至少为 2 n 2^n 2n?
因为球内部包含一个方盒，方盒的每个维度都是 [ − 1 , 1 ] [-1,1] [−1,1]，方盒的体积是 2 n 2^n 2n（所有维度的长度乘在一起）
方盒中点的范数最大是 n \sqrt{n} n ​（在球上的点）

计算问题

• 给定一个基 B B B 以及一个向量 v ⃗ \vec{v} v ，判断 v ⃗ \vec{v} v 是否在格 L ( B ) L(B) L(B) 中。
  把 v ⃗ \vec{v} v 表示成 B B B 中向量的线性组合的形式。（高斯消元，看系数是否都为整数）

• 给定两个基 B 1 , B 2 B_1,B_2 B1​,B2​，判断是否有 L ( B 1 ) = L ( B 2 ) L(B_1)=L(B_2) L(B1​)=L(B2​)。
  方法1. 根据 B 1 = U B 2 B_1=UB_2 B1​=UB2​，尝试求 U U U，检测 U U U 是否是酉矩阵。
  方法2. 判断 B 1 B_1 B1​ 中的每一个向量是否都在 B 2 B_2 B2​ 对应的格中，如果是，则证明 B 1 B_1 B1​ 中向量的线性组合也在 L ( B 2 ) L(B_2) L(B2​) 中（格对于加法是封闭的），从而可以得到 L ( B 1 ) ⊆ L ( B 2 ) L(B_1) \subseteq L(B_2) L(B1​)⊆L(B2​)，然后反过来再求一遍。

• 最短向量问题（SVP）：给定一个格（指定格中一组基，基向量可能非常长），找到格中的一个最短向量。

• SVP γ _\gamma γ​: 给定格基 B B B，找到 L ( B ) L(B) L(B) 中的一个向量使其长度不大于 γ λ 1 ( L ( B ) ) \gamma \lambda_1(L(B)) γλ1​(L(B))

• GapSVP γ _\gamma γ​（判定性问题）：给定一个格，判断 λ 1 \lambda_1 λ1​ 小于 1 1 1 还是大于 γ \gamma γ。

• 最短独立向量问题（SIVP）

• SIVP γ _\gamma γ​：给定格基 B B B，在 L ( B ) L(B) L(B) 中找到 n n n 个长度不大于 γ λ n ( L ( B ) ) \gamma \lambda _n(L(B)) γλn​(L(B)) 的线性无关的格向量。

• 最近向量问题（CVP）：给定格基 B B B 以及一个点 v v v （不一定是格点），找到一个格点使其到 v v v 的距离不超过到 v v v 最近的格点与 v v v 距离的 γ \gamma γ 倍。

• SVP γ _\gamma γ​ 不比 CVP γ _\gamma γ​ 难。（已经证明）

• 有界距离解码问题（Bounded Distance Decoding，BDD）：已知一个已经非常接近的点，求精确的最近的点。

参考文献

[1] BIU Winter School - https://www.youtube.com/watch?v=4ulHOV8iLls&t=6186s