随机格和对偶性
上文讲了各种平均情况格困难问题，并将其描述为对单向函数求逆或是寻找碰撞。现在可以将这些和特定随机格上的计算问题联系起来。
确定正整数 $n\leq m\leq q$，其中 $n$ 和/或 $m-n$ 作为主要安全参数。通常 $m$ 是 $n$ 较小的倍数，e.g.，$m=O(n)$ 或 $m=O(n\log n)$，$q$ 是一个大小为 $O(\log n)$ 比特的小素数(甚至不需要是素数)。格参数选择的优点之一可以看到模数的选择相当小，不同于数论密码学里常用的大素模数( $O(n)$ 比特)。对任意矩阵 $\mathbf{A}\in \mathbb{Z}^{n\times m}_q$ 定义
\[\Lambda_{q}^{\perp}(\mathbf{A})=\left\{\mathbf{x} \in \mathbb{Z}^{m}\colon \mathbf{A} \mathbf{x}=\mathbf{0} \bmod q\right\}\] \[\Lambda_{q}(\mathbf{A})=\left\{\mathbf{x} \in \mathbb{Z}^{m}\colon \mathbf{x}=\mathbf{A}^{T} \mathbf{s} \bmod q \qq{ for some } \mathbf{s} \in \mathbb{Z}_{q}^{n}\right\}\]我真的希望这些大佬能好好区分同余和等于，免得让我这种傻狗看着多费点脑子。
$\Lambda_{q}(\mathbf{A})$ 直观来看就是 $\mathbf{A}$ 的行空间模 $q$ 生成的格，$\Lambda_{q}^{\perp}(\mathbf{A})$ 则是线性方程组 $\mathbf{A} \mathbf{x}=\mathbf{0}$ 的解空间，就是 $A$ 的核。因为 $n < m$ 所以线性方程组肯定有无限个解。很好说明他们都是格，并且都是满秩格，因为易知他们包含 $m$ 个线性无关向量 $(0,…,0,q,0,…,0)$。
需要注意的是用来描述随机格的矩阵 $\mathbf{A}$ 并不是格基，对应格的格基 $\mathbf{B}$ 可以由 $\mathbf{A}$ 高效的计算出来，但没有必要。通常直接用 $\mathbf{A}$ 实行操作。
所以完全均匀随机的选取 $\mathbf{A}\in \mathbb{Z}^{n\times m}_q$ 定义了两类随机的 $m$ 维整数格，可以记作 $\Lambda_{q}(m,n)$ 和 $\Lambda_{q}^{\perp}(m,n)$。
这两类格之间的关系和 $\mathrm{SIS},\mathrm{LWE}$ 问题之间的联系就由下面的定义体现了：
-
$\mathrm{SIS}$ 问题要求在就 $\Lambda_{q}^{\perp}(m,n)$ 选取的随机格中找到一个小的非零向量。
-
$\mathrm{LWE}$ 问题要求在 $\Lambda_{q}(m,n)$ 的随机格中找到一个离给定目标向量 $\mathbf{b}$ 近的格向量。
这俩问题里“小的”，“近的”都是由集合 $X$ 定义的。如果 $X=\qty{\mathbf{x} \in \mathbb{Z}^{m} \mid norm{x} \leq \beta}$，那么目标就是找到对应范数或是距离最大为 $\beta$ 的向量。要注意的是这里并不总是最小的或是最近的，可能会存在更好的解，所以这里简单说“小的”，“近的”。
让我们具体的看一看。首先这些格都是 $q$ 阶的，i.e.，他们呈 $q$ 周期性 ：可以抓一个有限集 $Q=L \cap[0, \ldots, q)^{m}$ 这些格点，也就是坐标为 $\qty{0,…,q-1}$，这些点组成的离散超平行体，然后把他的复制 $Q+q\mathbb{Z}^n$ 平铺到整个空间来恢复整个格。这个性质使得将格描述为有限的点集，对这些格进行的绝大多数密码学操作都可以用模 $q$ 有限算术实现。
实际上 $\Lambda_{q}(\mathbf{A})$ 和 $\Lambda_{q}^{\perp}(\mathbf{A})$ 是标量 $q$ 放缩下的一对对偶格：
\[\Lambda_{q}(\mathbf{A})=q \cdot \widehat{\Lambda_{q}^{\perp}(\mathbf{A})} \qq{ and } \Lambda_{q}^{\perp}(\mathbf{A})=q \cdot \widehat{\Lambda_{q}(\mathbf{A})}\]特别的，$\det(\Lambda_{q}(\mathbf{A}))\cdot\det(\Lambda_{q}^{\perp}(\mathbf{A}))=q^m$。以及对于任意 $\mathbf{A}\in\mathbb{Z}^{n\times m}_q$，可得 $\det(\Lambda_{q}(\mathbf{A}))\leq q^n$ 且 $\det(\Lambda_{q}^{\perp}(\mathbf{A}))\geq q^{m-n}$。
对任意 $q$ 和 $\mathbf{A}\in \mathbb{Z}^{n\times m}_q$，可证明一下几个条件是等价的：
- $\det(\Lambda_{q}(\mathbf{A}))= q^n$
- $\det(\Lambda_{q}^{\perp}(\mathbf{A}))= q^{m-n}$
- $\mathbf{A}$ 为本原(primitive)矩阵，i.e.，$\mathbf{A} \mathbb{Z}_{q}^{m}=\mathbb{Z}_{q}^{n}$
如果 $\mathbf{A}\in \mathbb{Z}^{n\times m}_q$，则 $\operatorname{Pr}\qty{\operatorname{det}\left(\Lambda_{q}^{\perp}(\mathbf{A})\right)=q^n}=\operatorname{Pr}\qty{\operatorname{det}\left(\Lambda_{q}(\mathbf{A})\right)=q^{m-n}}=\operatorname{Pr}\qty{\mathbf{A} \mathbb{Z}_{q}^{m}=\mathbb{Z}_{q}^{n}} \geq 1-1 / q^{m-n}$
总之，对于特定选择的参数，(e.g.，$m\geq 2n$)，就分布 $\Lambda_{q}^{\perp}(m, n)$ 和 $\Lambda_{q}(m, m-n)$ 所选择的格有压倒性的概率 $\epsilon\geq1-q^{-n}$ 有相同的行列式 $q^n$，且分布 $\Lambda_{q}^{\perp}(m, n)$ 和 $\Lambda_{q}(m, m-n)$ 统计学上几乎完全相同。
再来看看 $\mathrm{SIS’},\mathrm{LWE}$ 问题之间的联系，本质上他们是一个问题的不同表示。但在密码学里，这两个问题通常会有完全不一样的参数选择。简单起见矩阵 $\mathbf{A}$ 约束为本原矩阵，或者更简单点直接 $[\mathbf{I}, \overline{\mathbf{A}}]$，假设 $X$ 是长度为 $\beta$ 约束的向量。
咱知道 $\mathrm{LWE}$ 是找距离目标点距离最多为 $\beta$ 的格点。现在令 $\mathbf{A}\in \mathbb{Z}^{n\times m}_q$ 为定义 $\mathrm{LWE}$ 格 $\Lambda_{q}(\mathbf{A})$ 的矩阵，通过上文结论咱知道这个格也可以表示为 $\Lambda_{q}^{\perp}(\mathbf{H})$，对于 $\mathbf{H} \in \mathbb{Z}_{q}^{(m-n) \times m}$。现在考虑 $\mathrm{SIS’}$ 实例 $\mathbf{H},\mathbf{Hb}$，其解恰恰是这样一个向量 $\norm{\mathbf{x}\leq\beta}\colon\mathbf{Hx=Hb}$，可知 $\mathbf{H(b-x)}=0\quad(\mathrm{mod}\enspace q)$，i.e.，向量 $\mathbf{v=b-x}$ 属于 $\Lambda_{q}^{\perp}(\mathbf{H})=\Lambda_{q}(\mathbf{A})$。综上，咱找到了 $\mathrm{LWE}$ 格里的一个向量 $\mathbf{v}\in\Lambda_{q}(\mathbf{A})$ 距离目标点 $\norm{b-v}=\norm{x}\leq \beta$。
上述证明可以看成一个从 $\mathrm{LWE}$ 到 $\mathrm{SIS}$ 的归约，加深加深理解，类似的也可以通过拆非齐次方程的通解为构建一个从 $\mathrm{SIS}$ 到 $\mathrm{LWE}$ 的归约。
总之这俩问题本质上是一个问题，且等价。但在密码学里这俩问题的参数选择通常大不相同，特别是由于格的行列式大小原因，涉及到 Minkowski 定理的连续极小值 $\mathrm{LWE}$ 问题通常会用比 $\mathrm{SIS’}$ 小的多的(与格的行列式相关)的 $\beta$。
