0%

LWE 问题

发表于 更新于 分类于

在了解了 SIS 问题后，我们开始介绍另一个格中的困难问题假设：LWE（Learning With Errors）问题。LWE 问题比 SIS 问题稍显复杂，但是由于 LWE 问题可以归约到 SIS 问题，因此 LWE 问题内在与 SIS 问题又存在着联系。下面我们先给出 LWE 的定义再来讨论它与 SIS 的关系。

LWE 的定义

LWE 问题最初由 Regev 在 [Reg05] 中提出，是一个和 SIS 类似（analogue）的问题。我们在给出 LWE 问题的定义前，需要先引入一个与之密切相关的分布称为 LWE 分布。

LWE distribution

For a vector $\mathbf{s} \in \mathbb{Z}_q^n$ called the secret, the LWE distribution $A_{\mathbf{s}, \chi}$ over $\mathbb{Z}_q^n \times \mathbb{Z}_q$ is sampled by choosing $\mathbf{a} \in \mathbb{Z}_q^n$ uniformly at random, choosing $e \gets \chi$ and outputting

— by [Pei16] in p.22

这个分布简单来说就是先选择一个可以公开的向量 $\mathbf{a}$，然后用秘密值 $\mathbf{s}$ 去和 $\mathbf{a}$ 做内积，但是特殊在于内积之后还会加上一个误差项 $e$（$e$ 从一个特定的误差分布 $\chi$ 中选取），将得到的结果 $b$ 与可公开的 $\mathbf{a}$ 作为二元组一同输出。而由于 $\mathbf{a}$ 和 $e$ 本身并不固定而是从特定的分布中选取的，于是得到的二元组 $(\mathbf{a}, b)$ 也是一个分布。显然这个分布并不是随机分布，因为客观存在着一个 $\mathbf{s}$ 满足 $b=\langle \mathbf{s, a} \rangle + e \mod q$，但是如果没有这个 $\mathbf{s}$，这个分布看起来就和随机分布不可区分，也无法从这个分布中把 $\mathbf{s}$。这也是下面要说的 LWE 问题的两种版本。

LWE 有两种版本，一种是 decision-LWE，一种是 search-LWE。联系 LWE 分布的定义并且再加上一点点望文生义（或者我们可以类比 DDH 与 CDH 来思考），其实可以很容易就猜出这两种版本的 LWE 形式。下面给出它们的具体定义：

Search-$\mbox{LWE}_{n, q, \chi, m}$​

Given m independent samples $(\mathbf{a}_i, b_i) \in \mathbb{Z}_q^n \times \mathbb{Z}_q$ drawn from $A_{\mathbf{s}, \chi}$ for a uniformly random $\mathbf{s} \in \mathbb{Z}_q^n$ (fixed for all samples), find $\mathbf{s}$.

Descision-$\mbox{LWE}_{n, q, \chi, m}$

Given $m$ independent samples $(\mathbf{a}_i, b_i) \in \mathbb{Z}_q^n \times \mathbb{Z}_q$ where every sample is distributed according to either:

​ (1) $A_{\mathbf{s}, \chi}$ for a uniformly random $\mathbf{s} \in \mathbb{Z}_q^n$ (fixed for all samples), or

​ (2) the uniform distribution,

distinguish which is the case (with non-negligible advantage).

— by [Pei16] in p.22

LWE 的讨论

从 LWE 分布的生成过程可以发现，如果没有最后加上去的误差项（error）$e$，那么不管是 decision-LWE 还是 search-LWE 都可以很简单地通过高斯消元法来解决，因此可以说 LWE 的密码学意义全在于它的误差项 $e$，于是 $e$ 的选择就非常重要。

关于误差项 $e$ 的选择

从定义看出，误差项是从误差分布 $\chi$ 中选出来的，误差分布一般都是一个高斯分布，这是由于高斯分布的优良性质（其实主要是因为现在对于高斯分布的研究比较透彻）。因此误差项的选择其实就是要确定这个高斯分布的参数。这里不打算仔细地讨论高斯分布的参数选择问题，因为这涉及到 LWE 的困难性问题，也就是从 SIVP 和 GapSVP（worst-case）到 LWE（average-case）的归约证明。最后确定参数为 $\alpha \cdot q$，其中 $\alpha$ 称为 error rate，它远小于 1。

LWE 问题的 lattice 表示

为了让 LWE 问题在格密码学中发挥作用，我们同样需要将 LWE 的定义对应到某个格上。注意到除去误差项 $e$，LWE 定义中的 $b$ 的剩余部分 $\langle \mathbf{s, a} \rangle$ 似乎是符合 lattice 格点的规律性的，因此我们可以将这一部分与格点对应起来，由此得到下述表达式：

其中 $\mathbf{A}$ 为所有公开的 $\mathbf{a}_i$ 构成的矩阵，这么做只是为了将从同一 LWE 分布 $A_{\mathbf{s}, \chi}$ 中选取的多个样本 $(\mathbf{a}_i, b_i)$ 紧凑地表达出来，此时我们有 $\mathbf{b = A}^t\mathbf{s + e} \mod q$，同理 $\mathbf{b}$ 是所有样本中 $b_i$ 构成的向量，$\mathbf{e}$ 是所有样本中 $e_i$ 构成的向量。

同样我们在这里给出一个二维的示意图来阐述 LWE 问题与 $\mathcal{L}(A)$ 的对应关系。从图中可以看出 LWE 问题给定了一个平面中的点（根据 LWE 分布，这个点实际上离某个格点非常相近），而要解决 LWE 问题就是就是要找到这个离它非常近的格点，或者等价的，找到这两个点之间的差值，即误差 $\mathbf{e}$。

lwe

关于 SIS 与 LWE 的关系

首先来说他们之间的归约关系：$\mbox{decision-LWE} \le_\mbox{(reduce to)} \mbox{SIS}$。也就是说，若能解决 SIS 问题，则可以利用 SIS Oracle 去解决 decision-LWE 问题。具体做法为：在拿到 decision-LWE 的样本 $(\mathbf{A, b})$ 后，只需要向 SIS Oracle 询问（query）$\mathbf{Az=0}$ 的解 $\mathbf{z}$，再计算 $\mathbf{b}^t \mathbf{z}$ 就可以知道拿到的样本是服从 LWE 分布还是随机分布。因为如果是服从 LWE 分布，则此时有：

而因为误差项 $\mathbf{e}$ 较小，与 $\mathbf{z}$ 做内积后依然很小，这与随机分布的情况得到的结果就完全不同，以这个为依据就可以完全解决 decision-LWE。

其次，SIS 问题与 LWE 问题对应的 lattice 也有着对偶关系：

最后，这两个问题的应用范围也不尽相同。同样是格中的困难问题假设，LWE 问题似乎比 SIS 的应用范围更广泛。SIS 一般可以用来构造一些 “minicrypt” 比如说 OWF/CRHF，digital signature，ID scheme 等机制，但至今没有一个 PKE 是基于 SIS 的；相反 LWE可 以实现 “cryptomania”，包括 FHE，PKE，IBE 等等。

参考资料