本篇讲一讲密码学组建所用到的平均情况格计算问题。上一篇跟这一篇之间应该还差一些很关键的关于格计算问题复杂度的归约问题，涉及到为什么咱基于平均情况计算问题所构建的方案的安全性基于最坏情况的格计算问题复杂度。但这方面内容涉及到很多数学内容包括对偶格，高斯分布等等内容，并且这些晦涩的复杂度研究对于咱构造方案这个上层建设过程并没有影响。感兴趣的可以看一看，相关的资料也有很多，可以了解到为什么我们构造方案时的参数选择有这么大的自由性，这源于格上各种困难问题及他们之间错综复杂的归约关系。比如这些困难问题到底哪个最难？最难的困难问题又有怎样的复杂度？等等。
平均情况格计算问题
咱都知道格上许多计算问题都有最坏情况困难性，比如广为人知的 $\mathbf{SVP}_{\gamma}$,$\mathbf{CVP}_{\gamma}$,$\mathbf{SIVP}_{\gamma}$ 等等。
但我们实际构造密码学组件时却不用这些困难问题，一个原因是这些问题不便于密码学使用，毕竟密码学的使用场景要求其安全性基于平均情况困难性，因此咱广泛使用以下几个平均情况格计算问题构造密码学组件，也就是这几个问题敲开了格密码 cryptomania 的大门。这些有以下参数：$n,m,q$ 和短向量集合 $X\subseteq\mathbb{Z}^m$, e.g., 集合 $X={\mathbf{x} \mid\norm{\mathbf{x}} \leq \beta}$ 即所有欧几里得范数为 $\beta$ 所约束的向量。
定义 1 Short Integer Solution problem $\mathbf{SIS}$, 输入一个矩阵 $\mathbf{A} \in \mathbb{Z}^{n\times m}_{q}$，要求找到一个非零向量 $\mathbf{x}\in X$ 使得 $\mathbf{A x}=0 \quad(\bmod\enspace q)$。
定义 2 Learning With Errors problem $\mathbf{LWE}$, 输入一个矩阵 $\mathbf{A} \in \mathbb{Z}^{n\times m}_{q}$ 和一个向量 $\mathbf{b}$ ，要求找到一个向量 $\mathbf{s}$ 使得 $\mathbf{b}-\mathbf{A}^{t}\mathbf{s}\in X$
以上两个是典中典，也有一些变体, e.g., $\mathbf{SIS’}$。
定义 3 The Inhomogeneous SIS problem $\mathbf{SIS’}$, 输入一个矩阵 $\mathbf{A} \in \mathbb{Z}_{q}^{n\times m}$ 和一个向量 $\mathbf{b}\in \mathbb{Z}^{n}_{q}$，要求找到一个向量 $\mathbf{x}\in X$ 使得 $\mathbf{A x}=\mathbf{b} \quad(\bmod\enspace q)$。
注意到 $\mathbf{x}$ 在 $\mathbf{SIS}$ 里要求是非零的毕竟要避免平凡解，但在 $\mathbf{SIS’}$ 里不需要这样的约束。$\mathbf{SIS’}$ 可以看作是更一般情况的 $\mathbf{SIS}$，实际上这两个问题是等价的，可以互相归约，归约算法也很简单。
密码学里面 $\mathbf{SIS},\mathbf{LWE},\mathbf{SIS’}$ 通常被用作平均情况困难问题，这要求定义输入实例的近似概率分布。通常：
-
矩阵 $\mathbf{A}$ 在 $\mathbb{Z}^{n\times m}_{q}$ 上均匀随机选择。
-
$\mathbf{LWE}$ 中，向量 $\mathbf{b}$ 通过均匀随机选取 $\mathbf{s}\gets \mathbb{Z}^n_{q}$ 进行选择，$\mathbf{e}\gets D_{X}$在一个 $X$ 的近似分布上进行采样，并且设置 $\mathbf{b}=\mathbf{A}^{t}+\mathbf{e}$。
-
$\mathbf{SIS’}$ 中，向量 $\mathbf{b}$ 由 $\mathbf{Ax}$ 其中均匀随机选择 $\mathbf{x}\gets D_{X}$ 设定。
接下来整点使用这些问题的最简单的密码学功能，将展现这些问题之间的联系和它们和格之间的联系。当然，这之中有很深的联系，不然也不会叫做格密码了。现在我们暂时将 $\mathbf{SIS},\mathbf{LWE},\mathbf{SIS’}$ 解释为特定随机分布的格上的平均情况格问题，之后咱会了解到这些问题和最坏情况格问题之间的联系。
函数家族
最简单的密码学原语：单向函数和抗碰撞哈希函数。
大多数密码方案都通常可以由 函数家族 描述，i.e.，一系列函数 $f_{k}\colon X\to Y$ 且由一个键值 $k\in K$ 索引。密码学应用里面一般会要求其为单向函数，i.e.，计算简单(给定函数键值 $k$ 和输入 $x$)，但逆向计算困难(给定 $k$ 和目标值 $y=f(x)$)。
定义 4 一个函数家族是一类函数 $\mathcal{F}=\{f_{k}\colon X \to Y\}_{k \in K}$ 有着共同的定义域 $X$ 和陪域 $Y$，由键值空间 $K$ 索引，伴随一个(通常是均匀随机的)键值上的概率分布 $k\gets K$。
通常，定义域 $X$ 也会被赋予一个概率分布 $x\gets X$。为了规范化渐进方法下的高效计算的概念，需要考虑的一系列函数家族 $\mathcal{F}_n$ 由安全参数 $n$ 索引，也就是说定义域 $X_n$，陪域 $Y_n$ 和键值空间 $K_{n}$ 都取决于 $n$。跟前面文章所讲过的一样，高效计算被确定为能在关于 $n$ 多项式时间内进行的计算，反过来不可行的计算就是运行时间关于 $n$ 呈超多项式关系(比如指数)。方便起见，接下来的内容里咱会固定安全参数 $n$ 的值不变，然后考虑一个单一的函数家族 $\mathcal{F}=\{f_{k}\colon X \to Y\}_{k \in K}$，隐含其对安全参数 $n$ 的依赖。
咱总是要求函数家族 $\mathcal{F}$ 可高效计算，也就是说键值分布 $k\gets K$ 可被高效采样，且存在一个评估为高效的算法输入 $k\in K$ 和 $x\in X$，输出 $f_k(x)$。咱同样假设定义域 $X$ 上的集合成员测试和对输入值采样 $x\gets X$ 也可高效完成。
函数家族可定义多种安全属性。两个最基本的是抗碰撞性和单向性。
定义 5 一个函数家族 $\mathcal{F}=\left\{f_{k}\colon X \to Y\right\}$ 是抗碰撞的如果其对于任意PPT算法 $\mathcal{A}$，
\[\operatorname{Pr}\qty{x_{1}, x_{2} \in X \wedge x_{1} \neq x_{2} \wedge f_{k}\left(x_{1}\right)=f_{k}\left(x_{2}\right) \mid k \gets K,\left(x_{1}, x_{2}\right) \gets \mathcal{A}(k)} \leq \epsilon\]对于可忽略的 $\epsilon=n^{-\omega(1)}$。 比如指数级小数 $\epsilon=2^{-\Omega(n)}$。
定义 6 一个函数家族 $\mathcal{F}=\left\{f_{k}\colon X \to Y\right\}$ 是关于(可高效采样的)输入分布 $X$ 单向的如果其对于任意PPT算法 $\mathcal{A}$，
\[\operatorname{Pr}\left\{x^{\prime} \in X \wedge f_{k}\left(x^{\prime}\right)=y \mid k \gets K, x \gets X, y=f_{k}(x), x^{\prime} \gets \mathcal{A}(k, y)\right\} \leq \epsilon\]对于可忽略的 $\epsilon=n^{-\omega(1)}$。
咱看到单向性的定义里面敌手算法 $\mathcal{A}$ 所输出的 $x’$ 的值没要求跟去计算 $y$ 的值相同，这是为了避免平凡函数也被定义成单向的，比如 $f(x)=0$，毕竟对于这种常函数如果要求找相同的值的话概率是可忽略的。但如果 $f_k$ 在 $X$ 上是单射的，$\mathcal{A}$ 就只能计算跟原来相同的值才能成功了。
另一个重要的密码原语里常见的安全定义是伪随机性。
定义 7 一个函数家族 $\mathcal{F}=\{f_{k}\colon X \to Y\}$ 是一个在输入分布 $X$ 上的伪随机生成器，如果这两个分布 $D_{0}=\{\left(k, f_{k}(x)\right) \mid k \gets K, x \gets X\}$ 和 $D_{1}=\{(k, y) \mid k \gets K, y \gets Y\}$ 是 $\epsilon$-不可区分的对于一些可忽略的 $\epsilon$，i.e.，对任意PPT算法 $\mathcal{A}$，
\[\left|\operatorname{Pr}\left\{\mathcal{A}(x) \mid x \leftarrow D_{0}\right\}-\operatorname{Pr}\left\{\mathcal{A}(x) \mid x \leftarrow D_{1}\right\}\right| \leq \epsilon\]$\mathbf{SIS’}$ 问题和 $\mathrm{LWE}$ 问题都可以很简单描述为对单向函数家族求逆，两个函数家族都由 $\mathbf{A} \in \mathbb{Z}^{n\times m}_{q}$ 索引。
- $\mathbf{SIS}$ 函数 $f_{\mathbf{A}} \colon X \to \mathbb{Z}_{q}^{n}$ 定义为：
输入分布为 $D_{X}$
- $\mathbf{LWE}$ 函数 $g_{\mathbf{A}}: \mathbb{Z}_{q}^{n} \times X \rightarrow \mathbb{Z}_{q}^{m}$ 定义为：
输入分布为 $\mathcal{U}\left(\mathbb{Z}_{q}^{n}\right) \times D_{X}$
这样定义 $\mathbf{SIS’}$ 问题就变成求逆单向函数 $f_{\mathbf{A}}$，$\mathbf{LWE}$ 则是求逆 $g_{\mathbf{A}}$。对于任意集合 $X$，$X’=X-X=\qty{\mathbf{x}-\mathbf{x}’\mid\mathbf{x},\mathbf{x}’\in X}$ 上的 $\mathbf{SIS}$ 问题就是找到 $f_{\mathbf{A}}$ 在定义域 $X$ 上的碰撞，因为就是找到零解。
