04格的最小距离、最短向量问题（SVP）及其变体和闵可夫斯基定理

一、格的最小距离（$\mathbf{\lambda }(\mathbf{\Lambda })$）

格$\Lambda$中两不同格点的最小欧几里得距离，等价于“最短非零格向量的长度”
λ(Λ)=inf⁡{∥v∥∣v∈Λ∖{0}}\lambda(\Lambda) = \inf\left\{ \|\boldsymbol{v}\| \mid \boldsymbol{v} \in \Lambda \setminus \{\boldsymbol{0}\} \right\}λ(Λ)=inf{∥v∥∣v∈Λ∖{0}} （格的离散性使得inf = min）
性质：由格的加法封闭性（若$\mathbf{x},\mathbf{y}\in \Lambda$，则$\mathbf{x}-\mathbf{y}\in \Lambda$）保证两种定义等价。

注：

1. 默认范数：欧氏范数$\Vert \cdot {\Vert }_2$（除非特别说明）。

2. inf vs min

   • inf（下确界）：集合$S$的下确界是其所有下界中的最大值 ，记作 inf$S$。下确界不一定属于集合$S$

   • min（最小值）：若集合$S$存在一个元素$a$，使得对于所有$x\in S$,都有$a\le x$,则$a$是$S$的最小值，记作min$S$。要求$a$必须属于集合$S$

     例子：inf(60,80)=60;min[60,80]=80

二、最短向量问题（SVP）及其变体

均为密码学中的核心困难问题，基于$\lambda (\Lambda )$的计算与判定，按$\gamma \ge 1$（近似因子）分类如下：

问题类型	目标描述
GapSVP${}_{\gamma }$（决策版）	输入基$B$和$d>0$，判定“是否存在非零格点$\mathbf{v}$满足$|\mathbf{v}|<d$”（是）或“所有非零格点$|\mathbf{v}|>\gamma d$”（否）。
EstSVP${}_{\gamma }$（计算版）	输入基$B$，输出$d\in [\lambda (\Lambda ),\gamma \lambda (\Lambda ))$（估计最短向量长度范围）。
SVP${}_{\gamma }$（搜索版）	输入基$B$，找到非零格点$\mathbf{v}$满足$0<|\mathbf{v}|\le \gamma \lambda (\Lambda )$（找到近似最短向量）。
SIVP${}_{\gamma }$	找到$n$个线性无关格点${\mathbf{u}}_i$，满足$|{\mathbf{u}}_i|\le \gamma \cdot {\lambda }_n$（${\lambda }_n$为第$n$最小逐次极小）。

三、闵可夫斯基定理（Minkowski’s Theorem）

作用

估计与基无关的$\lambda (\Lambda )$上界（仅依赖格的维度$n$和行列式$\det (\Lambda )$）。 此前依赖基选择的上界${\min }_i\Vert {\mathbf{b}}_i\Vert$。

定义

• 赫米特因子（Hermite Factor）：$\gamma (\Lambda )={\left(\frac{\lambda (\Lambda )}{\det (\Lambda {)}^{1/n}}\right)}^2$，具有缩放不变性（与格的基无关）。

$\lambda (\Lambda )$ ：表示格中最短距离

det($\Lambda$)：格的基本域体积

n是格的维度

• 赫米特常数（Hermite Constant）：${\gamma }_n={\sup }_{\Lambda }\gamma (\Lambda )$，在所有可能的 $n$ 维格 $\Lambda$ 中，取赫米特因子 $\gamma (\Lambda )$ 的最大值（严格来说是上确界），这个最大值就是赫米特常数 ${\gamma }_n$。

${\gamma }_n$：第 $n$ 维的赫米特常数（一个仅依赖于维度 $n$ 的常数） $\sup$：上确界（supremum），即所有可能取值中的最小上界（最大值或极限最大值）
$\Lambda$：$n$ 维格（任意 $n$ 维格点集）
$\gamma (\Lambda )$：格 $\Lambda$ 的赫米特因子

定理与推论

1. Blichfeldt原理

   若集合$S\subseteq \text{span}(B)$满足$\text{vol}(S)>\det (\Lambda )$，则存在${\mathbf{z}}_1,{\mathbf{z}}_2\in S$使得z1−z2∈Λ∖{0}\boldsymbol{z}_1 - \boldsymbol{z}_2 \in \Lambda \setminus \{\boldsymbol{0}\}z1​−z2​∈Λ∖{0}（集合中存在两个点的差是非零格点）。

2. 闵可夫斯基凸体定理

   若$\Lambda \subset {\mathbb{R}}^n$是满维格，$S\subset {\mathbb{R}}^n$为对称凸集且$\text{vol}(S)>2^n\det (\Lambda )$，则$S$必包含非零格点。

   

   证明思路：通过S/2={x∣2x∈S}S/2 = \{\boldsymbol{x} \mid 2\boldsymbol{x} \in S\}S/2={x∣2x∈S}转化为Blichfeldt原理的条件，结合对称凸性推导。

   令$S/2=x:2x\in S$,根据体积的性质，对集合进行缩放变换时，体积与缩放因子的n次幂成正比。我们假设缩放因子是 $\frac{1}{2}$,所以只需要证明vol($S$/2)=$\frac{1}{2^n}$vol($S$)>det($\Lambda$)。由Blichfeldt原理（若集合$S$$\subseteq \text{span}(\mathbf{B})$满足vol($S$)>det($\Lambda$），则存在$z_1-z_2\in \Lambda$\{0}。所以可得$z_1,z_2\in S/2$使得$z_1-z_2\in \Lambda$\{0}。

   而因为$z_1,z_2\in S/2$可得$2z_1\in S,2z_2\in S$根据对称凸集的性质（字面意思，终点的连线仍然在集合内部）
   因此：2t$z_1$-2(1-t)$z_2$$\in$$S$（死去的高中记忆开始攻击我，这个表示两个向量终点连线线段的任意向量）

   所以：$z_1-z_2\in S$ (t=$\frac{1}{2}$)成立

3. 范数上界推论

• 推论1（${\ell }_{\infty }$-范数上界）：存在非零格点x∈Λ∖{0}\boldsymbol{x} \in \Lambda \setminus \{\boldsymbol{0}\}x∈Λ∖{0}，满足$\Vert \mathbf{x}{\Vert }_{\infty }\le \det (\Lambda {)}^{1/n}$。

假设反命题：所有非零格点满足 $|x{|}_{\infty }>\det (\Lambda {)}^{1/n}$,取最小范数：令 $l=\min |x{|}_{\infty }>\det (\Lambda {)}^{1/n}$,构造立方体：C={x:∣x∣∞<l}C = \{x : |x|_{\infty} < l\}C={x:∣x∣∞​<l},体积：$\mathrm{vol}(C)=(2l{)}^n>2^n\det (\Lambda )$

应用凸体定理：$C$ 为中心对称凸体且体积 $>2^n\det (\Lambda )$
⇒ $C$ 包含非零格点 $y$

导出矛盾：,$y\in C$ ⇒ $|y{|}_{\infty }<l$

但 $l$ 是最小 ${\ell }_{\infty }$ 范数 ⇒ 矛盾

• 推论2（${\ell }_2$-范数上界，闵可夫斯基主定理）：(说明格中短向量必然存在)
  存在非零格点x∈Λ∖{0}\boldsymbol{x} \in \Lambda \setminus \{\boldsymbol{0}\}x∈Λ∖{0}，满足：

  $\Vert \mathbf{x}{\Vert }_2\le \sqrt{n}\cdot \det (\Lambda {)}^{1/n}$ 即$$\lambda (\Lambda )\le \sqrt{n}\cdot \det (\Lambda {)}^{1/n}$$

  （由$\Vert \mathbf{x}{\Vert }_2\le \sqrt{n}\Vert \mathbf{x}{\Vert }_{\infty }$结合推论2推导）。

  4.欧几里得范数和无穷范数之间的关系

对任意向量 $$\mathbf{x}=(x_1,x_2,\dots ,x_n)\in {\mathbb{R}}^n$$，有：

∥x∥2=x12+x22+⋯+xn2≤n⋅max⁡{x12,x22,…,xn2}=n⋅∥x∥∞ \|\boldsymbol{x}\|_2 = \sqrt{x_1^2 + x_2^2 + \cdots + x_n^2} \leq \sqrt{n \cdot \max\{x_1^2, x_2^2, \ldots, x_n^2\}} = \sqrt{n} \cdot \|\boldsymbol{x}\|_\infty ∥x∥2​=x12​+x22​+⋯+xn2​ ​≤n⋅max{x12​,x22​,…,xn2​} ​=n ​⋅∥x∥∞​

直观理解：

• ${\ell }_2$ 范数：各分量平方和的平方根。
• ${\ell }_{\infty }$ 范数：分量的绝对值的最大值（即 $\Vert \mathbf{x}{\Vert }_{\infty }={\max }_i|x_i|$）。
• 由于每个分量的平方 $x_i^2\le \Vert \mathbf{x}{\Vert }_{\infty }^2$，因此平方和最多为 $n\cdot \Vert \mathbf{x}{\Vert }_{\infty }^2$，开方后得到不等式。

该不等式表明==${\ell }_2$ 范数被 ${\ell }_{\infty }$ 范数控制==，且最坏情况下相差 $\sqrt{n}$ 倍，在格理论中，此关系常用于分析最短向量问题（SVP）的近似算法。