格密码与最短向量上界

article/2025/10/2 8:45:12

前言

一. BLICHFELD理论

二. 闵可夫斯基凸体定理

三. n维球体体积结论

四. 闵可夫斯基第一定理

五. 闵可夫斯基第二定理

结论

前言

本节主要讨论闵可夫斯基提出的关于连续最小值的上界问题。为了简化分析过程，仅讨论满秩的格，将结果类推到非满秩的格也是同理可得。

一. BLICHFELD理论

对于任意满秩格 $\Lambda \in R^n$ 和可测量的集合 $S\in R^n$ ，如果满足 $vol(S)>det(\Lambda)$ ,那么必定存在 $z_1,z_2\in S$ ，满足 $z_1-z_2\in \Lambda$ 。如下图所示：

证明：将S平移到基本区中，若 $vol(S)>det(\Lambda)$ ，则存在重合点。具体分析思路如下：

假定B为 $\Lambda$ 的格基，让x遍历所有格点 $\Lambda$ ，如下集合构成n维空间 $R^n$ 的一部分：

$x+P(B):=\lbrace x+y\lvert y\in P(B)\rbrace$

每个基本区都会有重叠的部分，定义交集如下：

$S_x=S\cap(x+P(B))$

由此，原集合就被分成了各个小块，如下：

$S=\cup _{x\in \Lambda}S_x$

体积也对应分成很多小块：

$vol(S)=\sum_{x\in\Lambda}vol(S_x)$

将每个小集合里面的格点去掉：

$\hat{S_x}=S_x-x$

单个点对体积是无影响的，所以以下结论依旧成立：

$\hat{S_x}\subseteq P(B)$ 以及 $vol(\hat{S_x})=vol(S_x)$

由此可得：

$\sum_{x\in\Lambda}vol(\hat{S_x})=\sum_{x\in\Lambda}vol(S_x)=vol(S)>vol(P(B))$

由此，一定存在一些格点 $x,y\in \Lambda, x\not=y$ ，保证 $\hat{S_x}\cap\hat{S_y}\not=0$ 。用z代表 $\hat{S_x}\cap\hat{S_y}$ 中的点，所以z+x一定包含在 $S_x\subseteq S$ ，z+y包含在 $S_y\subseteq S$ 。所以 $(z+x)-(z+y)=x-y$ 也包含在 $\Lambda$ 中。定理证明完毕。

由此定理可以类推出闵可夫斯基凸体定理。此定理表明一个足够大的中心对称的凸体一定包含一个非零的格点。如果S是中心对称的，当 $x\in S$ 时， $-x\in S$ ；因为是个凸体，当 $x,y \in S$ 且 $\lambda \in [0,1]$ ，不难推出 $\lambda x+(1-\lambda)y\in S$ 。中心对称和凸体的前提条件，去掉任何一个，闵可夫斯基凸体定理就会不成立。

二. 闵可夫斯基凸体定理

对于任意满秩格 $\Lambda \in R^n$ 和中心对称凸集 $S\in R^n$ ，若 $vol(S)>2^ndet(\Lambda)$ ，则S包含非零格点。

证明：

令 $\hat{S}=\frac{1}{2}S=\lbrace x|2x\in S\rbrace$ 。所以 $vol(\hat{S})=2^{-n}vol(S)>det\Lambda$ 。根据BLICHFELD理论，一定存在两个点 $z_1,z_2\in\hat{S}$ ，满足 $z_1-z_2\in\Lambda$ 且不是原点。根据定义， $2z_1,2z_2\in S$ ，又因为S是中心对称的，所以 $-2z_2\in S$ 。另外由于S是凸体， $\frac{2z_1-2z_2}{2}=z_1-z_2$ 也在空间S中。如下图所示：

此证明的主体思想：将S等比例缩小一半。

三. n维球体体积结论

$vol(B(0,r))\geq{(\frac{2r}{\sqrt{2}})}^n$

证明：

此球内包含一个长度为 $\frac{2r}{\sqrt{n}}$ 的立方体。如下图：

所以可得 $\lbrace x\in R^n|\forall i,|x_i|<\frac{r}{\sqrt{n}}\rbrace\subseteq B(0,r)$ 。证明完毕。

到此铺垫完毕，可引出格最短向量的上界问题。

四. 闵可夫斯基第一定理

对于任意满秩格 $\Lambda\in R^n$ ，其最短向量长度满足如下：

$\lambda_1(\Lambda)\leq\sqrt{n}{(det\Lambda)}^{\frac{1}{n}}$

证明：根据定义，球 $B(0,\lambda_1(\Lambda))$ 内包含非零格点，根据以上分析可得：

${(\frac{2\lambda_1(\Lambda)}{\sqrt{n}})}^n\leq vol(B(0,\lambda_1(\Lambda)))\leq2^n det(\Lambda)$ 。整理此式子不难得出 $\lambda_1(\Lambda)$ 的上界。

主题思想： $B(0,\lambda_1(\Lambda))$ 不含任何非零格点+闵可夫斯基凸体定理。

对于闵可夫斯基第一定理的理解与分析：

定理中 ${(det\Lambda)}^\frac{1}{n}$ 看起来可能有些奇怪，实际上有它本身的意义：能够与空间维度联系起来。例如，将格 $c\Lambda$ 看成原格 $\Lambda$ 扩大c倍产生。所以易得 $\lambda_1(c\Lambda)=c\lambda_1(\Lambda)$ 。另一方面，在n维度上 $det(c\Lambda)=c^ndet(\Lambda)$ ，等式右边正如我们所理解的那样扩大c倍。由此得出结论，任意秩为n，行列式为1的格，最短向量的上界为 $\sqrt{n}$ 。

这个上界可以进一步缩小吗？答案是可以的！举个例子，取一个很小的 $\epsilon>0$ ，考虑一组格基 ${(\epsilon,0)}^T,{(0,\frac{1}{\epsilon})}$ ，此格的行列式为1，依据闵可夫斯基第一定理可得上界为 $\sqrt{2}$ ，然而实际最短向量为 $\epsilon$ 。实际上，已经有研究将 $\sqrt{n}$ 的上界缩小到 $c\sqrt{n}, c<1$ 。此处讨论的二维可以拓展到多维。

闵可夫斯基第一定理研究的是最短向量，也就是第一个连续最小值 $\lambda_1$ 。加强版的连续最小值问题可以由闵可夫斯基第二定理说明，以下研究的不只是 $\lambda_1$ ，考虑的是 $\lambda_i$ 的几何平均数。

五. 闵可夫斯基第二定理

对于任意满秩格 $\Lambda\in R^n$ ，其连续最小值最小值满足：

$(\prod_{i=1}^n\lambda_i(\Lambda))^{1/n}\leq\sqrt n(det \Lambda)^{1/n}$

证明：取 $x_1,\ldots,x_n\in \Lambda$ 为连续最小值代表的向量，也就是 $\lVert x_i\rVert=\lambda_i(\Lambda)$ 。令 $\tilde{x_1},\ldots,\tilde{x_n}$ 代表对应的Gram_Schmidt正交化结果。引入一个椭球体，轴为 $\tilde{x_1},\ldots,\tilde{x_n}$ 所在的直线，长度为 $\lambda_1,\ldots,\lambda_n$ 。可得如下椭球体内部空间（不包含边界）：

易得，椭球体不包含任何非零格点。以二维为例子，理解为 $x_1$ 向量在椭圆的边界， $x_2$ 向量在椭圆的外部，如下图：

此部分证明该椭球体用T表示时，该椭球体T的内部不包含任何非零格点。

取任意非零的格点 $y\in\Lambda$ ，让 $1\leq k\leq n$ 使得k是对应的最大值，且满足如下不等式：

$||y||\geq\lambda_k(\Lambda)$

如果 $x_1,\ldots,x_k,y$ 是k+1个线性独立的向量，且要求它们的长度就都小于 $\lambda_{k+1}(\Lambda)$ ，显然是互相矛盾的。所以可得

$y\in span(\tilde{x_1},\ldots,\tilde{x_k})=span(x_1,\ldots,x_k)$ 。

综合以上：

由此可得 $y\notin T$ 。