格密码与最短向量下界

2023-11-01

前言

最短的非零向量长度是格密码中的一个基本量（定义前提为非零向量，因为格中总包含零向量，其模长为0），通常使用代量 $\lambda_1$ 表示。用格的观点来理解 $\lambda_1=r$ ：以r为半径的球内的格，只能形成一维的格的延展空间。

欧几里得范数，又叫 $l_2$ 范数，定义为如下：

$||x||_2=\sqrt{\sum x_i^2}$

$||x||_2$ 在本文章中简写为||x||。

$l_1$ 范数定义为如下：

$||x||_1=\sum|x_i|$

$l_\infty$ 范数定义为如下：

$l_\infty=max|x_i|$

一. 格的最短向量

首先定义圆心为原点，半径为r的m维实心球的式子，如下：

$\bar B(0,r)=\lbrace x\in R^m|||x||\leq r\rbrace$

对于秩为n的格 $\Lambda$ ，其连续最小值定义为如下：

$\lambda_i(\Lambda)=inf\lbrace r|dim(span(\Lambda\cap\bar B(0,r)))\geq i\rbrace$

如下图表示了最小值和次小值的长度：

此定义表明了格的最短向量，次短向量，······的长度。

二. 最短向量长度下界

若B为秩为n的格基， $\tilde {B}$ 代表对应的Gram-Schmidt正交化结果，那么最短向量长度满足如下不等式：

$\lambda_1(L(B))\geq min ||\tilde{b_i}||>0$

此处将用两种方法来证明该定理。

证明方法一：

任取 $x\in Z^n$ 为整数非零向量，很明显可得如下不等式：

$||Bx||\geq min||\tilde b_i||$

取 $j\in \lbrace 1, \ldots ,n\rbrace$ 且 $x_j$ 为下标最大的非零元素。由此可得如下等式：

对于任意的i<j，都有如下向量相乘的结论：

$<b_i,\tilde b_j>=0,\quad <b_j,\tilde b_j>=<\tilde b_j,\tilde b_j>$

根据向量相乘的结论，我们易得：

$|\langle Bx,\tilde b_j\rangle|\leq ||Bx||\cdot ||\tilde b_j||$

最终可得：

$||Bx||\geq |x_j|||\tilde b_j||\geq ||\tilde b_j||\geq min ||\tilde b_i||$

到此，证明完毕。

证明方法二：

从以上可以看出，在任何非零的组合中，最靠下的量最小的正值为 $\lVert \tilde{b}_i\rVert$ 。

三. 格点离散

对于任意两个不同格点x,y，总存在 $\xi>0$ ，满足 $\lVert x-y\rVert>\xi$ 。通过定义名称易理解，格是一个离散的集合。

证明：

四. 格的连续最小值

格的连续最小值可以用格内某向量长度表示，对于任意的 $1\leq i \leq n$ ,必定存在向量 $v_i\in \Lambda$ ，使得 $\lVert v_i\rVert=\lambda_i(\Lambda)$ 。

证明：

依据格的最短向量概念，半径为 $2\lambda_i(\Lambda)$ 的n维球内仅包含有限个格点。依据 $\lambda_i$ 的定义，球内必定包含长度为 $\lambda_i(\Lambda)$ 的向量。

总结

格密码的发展简史如下：

18世纪到1982年，拉格朗日、高斯、闵可夫斯基、埃尔米特等科学家开始研究格点的数学性质。

1982年到1996年进入LLL密码分析领域。

1996年到2005年第一代格密码开始出现，包含Ajtai96，AD97G, GH97。

2005年到2016年第二代格密码关注于实用化格密码算法，包含Regev0, GPV08, MP12, BLISS, NewHope, Frodo。

2016年至今，格密码开始不断标准化。

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)