Learning With Error（LWE）问题学习

news/2024/5/22 3:35:59/文章来源:https://blog.csdn.net/qq_43271194/article/details/126852827

概念

又称误差还原，容错学习问题，即已知一个矩阵 $A$ 以及一个向量，求解
$b^=Ax+e\hat{b}=A x+e$
这里 $e$ 是一个固定数值范围内随机采集的一个随机噪音向量，所以这个问题就转化为通过 $A$ 和 $b^\hat{b}$ 来还原最初的未知向量 $x$
可以理解为：需要找到一组系数，使得一组基向量的线性组合无线逼近目标向量，使用噪音误差的大小来定义我们需要距离目标向量有多近。

分类
一般分为两类，决策LWE（简称为DLWE）的设定和搜索LWE（简称为SLWE）基本相同。唯一不同的是，SLWE最后的问题是需要我们找到 $s$ ，而DLWE只需要让我们辨别看到的 $b^=As+e\hat b = As+e$ 到底是LWE问题中的误差乘积还是一个随机生成的向量。

搜索LWE问题（Search LWE Problem）

关键概念
在这里插入图片描述
$LWE(n,m,q,xB):SearchVersionLetA←RZqm×n,s←RZq,e←RxBGiven(A,As+e),finds′∈Zqns.t.∥As′−(As+e)∥∞≤BLWE\left(n, m, q, x_{B}\right): Search Version\\ Let A \stackrel{R}{\leftarrow} \mathbb{Z}_{q}^{m \times n}, s \stackrel{R}{\leftarrow} \mathbb{Z}_{q}, e \stackrel{R}{\leftarrow} x_{B} \\ Given (A, A s+e) , find s^{\prime} \in \mathbb{Z}_{q}^{n} s.t. \left\|A s^{\prime}-(A s+e)\right\|_{\infty} \leq B$
帮助理解：
这里开始定义了四个重要的参数，

$m$ 代表线性方程组有多少个方程，
$n$ 代表了每个方程中有多少个未知数。
$q$ 则是有限域的大小，一般来说这会是一个足够大的素数。
误差噪音取值上限 $B$ 的大小决定问题中需要找到的解距离实际取值 $b^\hat{b}$ 可以相差多少。
$R$ 代表随机选取。

结合各个参数的含义，则LWE问题的定义就是给定矩阵 $A$ 与误差乘积 $A s + e$ ，如何能够搜索出（search）一个合理的 $As′As^{\prime}$ ，使得得到的向量和问题给定的 $A s + e$ 之间的误差不能超过误差上限 $B$ 。

可以理解为：给定矩阵 $A$ 以及带有误差的结果 $A s + e$ 还原出未知的向量 $s$ 。

来看看这些个参数会如何影响LWE问题的难度

如果系统中的未知变量越多那么，问题将越难，也就是增大 $n$ 的大小会增加LWE问题的难度， $n$ 也被称为LWE问题的安全参数。
$m$ 可以看作 $n$ 的多项式倍数，如果可用的方程组越多，那么解出未知向量就会容易一些。
$q$ 也可以看作 $n$ 的多项式倍数
误差 $B$ 需要比 $q$ 小很多，这样找到正确的解老说会相对简单。

决策LWE问题（Decisional LWE Problem）

在解决证明一个困难问题的安全性的时候，我们一般都会使用决策版本的LWE问题（Decisional LWE）

$E\left(n, m, q, x_{B}\right) : Decisional Version\\ \operatorname{Let} A \stackrel{R}{\leftarrow} \mathbb{Z}_{q}^{m \times n}, s \stackrel{R}{\longleftarrow} \mathbb{Z}_{q}, e \stackrel{R}{\leftarrow} x_{B}, v \stackrel{R}{\longleftarrow} \mathbb{Z}_{q}^{m} .\\ Distinguish (A, A s+e) from (A, v) .$
只能看到两个值， $A$ 和 $b^\hat b$ ，需要辨别出看到的到底是一个LWE问题实例 $b^=As+e\hat b = As+e$ ，还是一个随机变量 $v$
由于LWE问题本身就是困难的，所以从 $A s + e$ 中提取出未知变量 $x$ 来是很困难的，也就是，在我们眼中 $A s + e$ 和一个随机变量其实没多大区别，没法获取有价值的信息。
一般来说参数一个个生成比较费力，所以一般都指定一个参数例如 $n$ 然后交给一个函数 $f (n)$ 来生成其他参数的输出，只要保证参数生成符合要求即可。

Regev加密算法

这是一个基于DLWE（决策性LWE问题）的格密码学中的公钥加密系统

具体内容

在这里插入图片描述

正确性验证
将解密部分计算展开
$x~=c1−c0⋅s=rTb+q/2⋅x−rTAs=rT(As+e)−rTAs+q/2⋅x=rTe+q/2⋅x\begin{array}{c} \tilde{x}=c_{1}-c_{0} \cdot s \\ =r^{T} b+q / 2 \cdot x-r^{T} A s \\ =r^{T}(A s+e)-r^{T} A s+q / 2 \cdot x \\ =r^{T} e+q / 2 \cdot x \end{array}$
在这里插入图片描述
把有限素数域所有数字连接起来形成一个环状结构，当需要加密一个bit的时候，把这个bit映射到环上去，0代表环的一头（即0），1代表环的另一头（即q/2）。我们叠加的噪音就等于是把这个映射的点往上或者往下位移了一部分，这样只要噪音的大小不过分（低于q/4），我们就可以通过看这个值到底在环的哪一侧来判断这个bit的具体取值了。但是一旦叠加噪音超过了临界值，那么就无法判断bit的值了。
在这里插入图片描述
假如，噪音变大了，就有可能导致误差上限超过临界值，一旦超过，那么0和1极有可能映射到相同的点上去，那就导致解密失败。