注意, 本系列是Foundation of Lattice-Based Cryptography, 而不是Basic Lattice-Based Cryptography, 这意味着我们更多是关注基本定义, 困难问题, 算法, 而不是关注具体的密码方案. 此外, 基石对应foundation, 基础对应basics.

在文章中, 我们可能会用到SageMath作为计算工具以展示例子, 这是一个语法类似于Python的功能强大的开源计算软件.

基本定义

格实际上就是$\mathbb R^n$空间中周期出现的点阵, 它是$\mathbb R^n$的一个子集, 这里, “周期"是一个非常不精确的说法, 因此精确来说格可以定义如下.

定义

令$\Lambda\subset \mathbb R^n$, 如果存在$\mathbb R^n$中的线性无关向量组$\mathbf b_1,\cdots,\mathbf b_m$, 满足

$$ \mathbf v\in\Lambda\iff \exists z_1,\cdots,z_m\in\mathbb Z:\mathbf v=\sum_{i\in[m]}z_i\mathbf b_i $$

那么就称$\Lambda$为$\mathbb R^n$中的一个格. 当$m=n$时, 就说$\Lambda$是满秩的.

定义中, 我们要求格点是基的系数为整数的线性组合. “秩"一词是从英文"rank"中翻译过来的. 如果读者具有较好的代数基础, 那么可以得出实际上格上一个$\mathbb Z$-模. 这里的格的秩实际上就是这个$\mathbb Z$-模的秩.

其他

用SVP$\gamma$的Oracle求解GapSVP$\gamma$

当给定GapSVP$\gamma$的输入$(\mathbf B,r)$的时候, 访问一次SVP$\gamma$的Oracle可以得到一个向量$v$长度为$r^\prime$使得$r^\prime\in[\lambda_1(\mathbf B),\gamma\lambda_1(\mathbf B)]$, 此时我们可以根据$r^\prime$来决定输入. 根据$r,\lambda_1(\mathbf B)$的大小不同, 有如下几种情况:

其中阴影部分是我们能够得到的$r'$的大小. 可见, 将得到的结果和$\gamma r$进行比较, 当$r'<\gamma r$时, 就是1.或3.两种情况, 都应该输出NO. 反之, 则输出YES.

用GapSVP$_\gamma$的Oracle输出$[\lambda_1(\mathbf B),\gamma \lambda_1(\mathbf B)]$中的一个值

对于有理数的$\lambda_1(\mathbf B)$, 要求$\lambda_1(\mathbf B)$, 需要带不同的$r$到GapSVP$_\gamma$的Oracle中尝试. 当$r\leq\lambda_1$时, oracle输出YES, 而当$r>\gamma\lambda_1$时, oracle输出NO, 在$\lambda_1<r\leq \gamma \lambda_1$时, oracle的输出是不确定的, 带入不同的$r$, oracle典型的输出如下图

无论怎样的情况, 任取一对YES, NO, $[\lambda_1,\gamma\lambda_1]$中的一个数都在其间. (边界的情况要略微处理一下).