格密码–LWE，DLWE和ss-LWE

0.数学符号

数学符号	含义	备注
${\mathbb{Z}}_q$	模$q$的整数集合，即{0,1,2,...,q−1}\{0,1,2,...,q-1\}{0,1,2,...,q−1}	用于定义LWE、DLWE、ss-LWE等问题中矩阵和向量的元素取值范围，是基础整数环
$x{\in }_{R}S$	$x$从集合$S$中均匀随机（且独立）地选取	如$s{\in }_R{\mathbb{Z}}_q^n$表示秘密向量$s$随机选自该向量空间，用于LWE等问题中随机参数的选取
$\text{LWE}(m,n,q,B)$	学习错误问题：给定$A{\in }_R{\mathbb{Z}}_q^{m\times n}$、$b=As+e(\mathrm{mod}q)$，寻找秘密向量$s$，其中$s{\in }_R{\mathbb{Z}}_q^n$，$e{\in }_R[-B,B{]}^m$且$B\ll q/2$	由Regev在2005年提出，核心是从带误差的线性方程中恢复秘密，是格密码的核心困难问题
$A{\in }_R{\mathbb{Z}}_q^{m\times n}$	$A$是一个$m$行$n$列的矩阵，元素属于${\mathbb{Z}}_q$，且随机选取	LWE问题的输入矩阵，用于构造带误差的线性方程$b=As+e(\mathrm{mod}q)$
$s{\in }_R{\mathbb{Z}}_q^n$	$s$是一个$n$维列向量，元素属于${\mathbb{Z}}_q$，且随机选取	LWE问题中的秘密向量，是需要求解的目标
$e{\in }_R[-B,B{]}^m$	$e$是一个$m$维列向量，每个分量在$-B$到$B$之间，且随机选取	LWE问题中的误差向量，“短”特性由$B\ll q/2$保证，是问题困难性的关键
$b=As+e(\mathrm{mod}q)$	向量$b$由矩阵$A$与秘密向量$s$的乘积加误差向量$e$后模$q$得到	LWE问题的核心方程，$b\in {\mathbb{Z}}_q^m$是已知输入，用于反推秘密$s$
$\text{DLWE}(m,n,q,B)$	决策性学习错误问题：给定$(A,c)$，判断$c$是$b=As+e(\mathrm{mod}q)$还是随机向量$r{\in }_R{\mathbb{Z}}_q^m$	是LWE的判定性版本，需区分“带误差的线性组合”与“纯随机向量”
$r{\in }_R{\mathbb{Z}}_q^m$	$r$是一个$m$维列向量，元素属于${\mathbb{Z}}_q$，且随机选取	DLWE中用于对比的随机向量，与$b$以等概率作为$c$的候选
$\text{ss-LWE}(m,n,q,B)$	短秘密学习错误问题：秘密向量$s{\in }_R[-B,B{]}^n$，其余同LWE	是LWE的变体，秘密向量也具有“短”特性，与LWE等价（可双向归约）
$Roun{d}_q(x)$	模$q$的取整函数，将$x$映射到最近的{0,1}\{0, 1\}{0,1}（如LWE加密解密中）	在解密中用于从$c_2-s^T{c}_1$还原明文m∈{0,1}m \in \{0,1\}m∈{0,1}，核心是判断值是否接近$0$或$\lceil q/2\rfloor$
$ss\text{-DLWE}(n,n,q,B)$	短秘密决策性学习错误问题：基于ss-LWE的判定性版本	与ss-LWE等价，在公钥加密安全性证明中作为困难问题假设
$c_1=A^{T}r+z$	加密过程中计算的第一部分密文，其中$A^T$是$A$的转置，$r,z{\in }_R[-B,B{]}^n$	Lindner-Peikert公钥加密方案中的密文分量，依赖公钥$A$
$c_2=b^{T}r+z^{\prime }+m\lceil q/2\rfloor (\mathrm{mod}q)$	加密过程中计算的第二部分密文，其中$b^T$是$b$的转置，$z^{\prime }{\in }_R[-B,B]$，m∈{0,1}m \in \{0,1\}m∈{0,1}	Lindner-Peikert公钥加密方案中的密文分量，嵌入明文$m$，依赖公钥$b$
$s^T{c}_1$	秘密向量$s$的转置与密文$c_1$的内积	解密过程中用于消除密文中的公开信息，还原含明文的误差项

1.LWE定义

2005年LWE(Learning With Errors)问题被Regev提出。
$\text{LWE}(m,n,q,B)$：给定随机矩阵$\mathbf{A}{\in }_R{\mathbb{Z}}_q^{m\times n}$、秘密向量$\mathbf{s}\in {\mathbb{Z}}_q^n$、误差向量$\mathbf{e}{\in }_R[-B,B{]}^m$（$B\ll q/2$），以及样本$\mathbf{b}=\mathbf{A}\mathbf{s}+\mathbf{e}(\mathrm{mod}q)$，目标是恢复秘密向量$\mathbf{s}$。 LWE问题的核心方程为：
$$\underset{m\times n\text{ 随机矩阵 }\mathbf{A}}{\underbrace{\left(\begin{array}{cccc}{a}_{11}& a_{12}& \dots & a_{1n}\\ a_{21}& a_{22}& \dots & a_{2n}\\ ⋮& ⋮& \ddots & ⋮\\ a_{m1}& a_{m2}& \dots & a_{mn}\end{array}\right)}}\underset{n\times 1\text{ 秘密向量 }\mathbf{s}}{\underbrace{\left(\begin{array}{c}{s}_1\\ s_2\\ ⋮\\ s_n\end{array}\right)}}+\underset{m\times 1\text{ 短误差向量 }\mathbf{e}}{\underbrace{\left(\begin{array}{c}{e}_1\\ e_2\\ ⋮\\ e_m\end{array}\right)}}\equiv \underset{m\times 1\text{ 样本向量 }\mathbf{b}}{\underbrace{\left(\begin{array}{c}{b}_1\\ b_2\\ ⋮\\ b_m\end{array}\right)}}(\mathrm{mod}q)$$

矩阵乘法和加法的逐行展开（共 $m$(样本数量) 个方程，变量为 $s_1,s_2,\dots ,s_n$（$n是秘密向量\mathbf{s}$的维度），误差 $e_1,\dots ,e_m$ 是隐藏的短向量）：
$$\{\begin{array}{l}{a}_{11}{s}_1+a_{12}{s}_2+\cdots +a_{1n}{s}_n+e_1\equiv b_1(\mathrm{mod}q)\\ a_{21}{s}_1+a_{22}{s}_2+\cdots +a_{2n}{s}_n+e_2\equiv b_2(\mathrm{mod}q)\\ ⋮\\ a_{m1}{s}_1+a_{m2}{s}_2+\cdots +a_{mn}{s}_n+e_m\equiv b_m(\mathrm{mod}q)\end{array}$$

2.LWE参数

1.参数B分析

1.如果$B=0$(即e=0：没有误差)，那么原式可以化为$A\mathbf{s}=\mathbf{b}$(mod q)可以被快速解决。（ISIS中类似的方程是无法快速找到解的，而这里却可以，两者的核心区别是对解是否有约束）

2.如果$B$=$(q-1)/2$(误差过大),秘密$s$无法恢复（信息论上不可能）
3.实际中取==$B<q/4$确保误差既能掩盖关系，又能通过合理约束使解唯一
4.（Arora - Ge定理）若误差范围==B 的渐近增长速度严格慢于 $\sqrt{n}$（即当 $n$ 趋近于无穷大时，$B$ 相对于 $\sqrt{n}$ 可忽略不计 ），且样本数量 ( m ) 足够大（满足 $m\gg n$ ），则带误差学习问题（LWE）可在 亚指数时间（例如 $2^{n^{ϵ}}$ ，其中 $0<ϵ<1$ ）内被求解。

2.参数m和n分析

当m>>n的时，LWE会有唯一解（$\mathbf{s}，\mathbf{e}$）。LWE解的唯一性仅在：以向量 $A\mathbf{s}(\mathrm{mod}q)$ 为中心的 $q^n$个球中，任意两个都不重叠。 得以保证。

3.D-LWE(Decisional LWE)

定义：

$\text{DLWE}(m,n,q,B)$：给定随机矩阵$\mathbf{A}{\in }_R{\mathbb{Z}}_q^{m\times n}$、秘密向量$\mathbf{s}\in {\mathbb{Z}}_q^n$、误差向量$\mathbf{e}{\in }_R[-B,B{]}^m$（$B\ll q/2$），以及样本$\mathbf{b}=\mathbf{A}\mathbf{s}+\mathbf{e}(\mathrm{mod}q)$。和随机向量$\mathbf{r}{\in }_{\mathbf{R}}{\mathbb{Z}}_q^m$。输出的$\mathbf{c}$两种情况1.$\mathbf{c}=\mathbf{b}$(1/2的概率) 2.$\mathbf{c}=\mathbf{r}$(1/2)的概率。目标是对于给定的（A，$\mathbf{c}$）显著高于1/2的概率能够区分：$\mathbf{c}=\mathbf{b}$还是$\mathbf{c}=\mathbf{r}$

4.LWE与DLWE等价

Claim 1: DLWE ≤ LWE

目标：用 LWE 求解器区分 DLWE 实例 $(\mathbf{A},\mathbf{c})$ 是真实样本还是随机样本。

步骤：

1. 输入 DLWE 实例 $(\mathbf{A},\mathbf{c})$，其中 $\mathbf{c}$ 可能是：
   • 真实样本：$\mathbf{c}=\mathbf{A}\mathbf{s}+\mathbf{e}(\mathrm{mod}q)$
   • 随机样本：$\mathbf{c}=\mathbf{r}{\in }_R{\mathbb{Z}}_q^m$
2. 调用 LWE 求解器处理 $(\mathbf{A},\mathbf{c})$：
   • 若返回唯一有效解 $(\mathbf{s},\mathbf{e})$（满足 $\mathbf{A}\mathbf{s}+\mathbf{e}\equiv \mathbf{c}(\mathrm{mod}q)$ 且 $\mathbf{e}\in [-B,B{]}^m$），则判定 $\mathbf{c}$ 为真实样本
   • 若求解器失败（无解或超时），则判定 $\mathbf{c}$ 为随机样本

合理性：

• 当 $\mathbf{c}=\mathbf{b}$ 时，LWE 求解器能以高概率找到解（唯一解假设下）
• 当 $\mathbf{c}=\mathbf{r}$ 时，方程 $\mathbf{A}\mathbf{s}+\mathbf{e}\equiv \mathbf{r}(\mathrm{mod}q)$ 无解（因 $\mathbf{r}$ 独立于 $\mathbf{A}$）

Claim 2: LWE ≤ DLWE

目标：用 DLWE 求解器恢复 LWE 实例 $(\mathbf{A},\mathbf{b})$ 的秘密向量 $\mathbf{s}$（逐个分量猜测）。

假设原始矩阵和向量为：
$$\mathbf{A}=\left(\begin{array}{cccc}{a}_{11}& a_{12}& \cdots & a_{1n}\\ a_{21}& a_{22}& \cdots & a_{2n}\\ ⋮& ⋮& \ddots & ⋮\\ a_{m1}& a_{m2}& \cdots & a_{mn}\end{array}\right),\mathbf{b}=\left(\begin{array}{c}{b}_1\\ b_2\\ ⋮\\ b_m\end{array}\right),\mathbf{\Delta }=\left(\begin{array}{c}{\delta }_1\\ {\delta }_2\\ ⋮\\ {\delta }_m\end{array}\right)$$

1. 构造新矩阵 ${\mathbf{A}}^{\prime }$：

   • 将 $\mathbf{\Delta }$ 加到 $\mathbf{A}$ 的第一列：

   $${\mathbf{A}}^{\prime }=\left(\begin{array}{cccc}{a}_{11}+{\delta }_1& a_{12}& \cdots & a_{1n}\\ a_{21}+{\delta }_2& a_{22}& \cdots & a_{2n}\\ ⋮& ⋮& \ddots & ⋮\\ a_{m1}+{\delta }_m& a_{m2}& \cdots & a_{mn}\end{array}\right)$$

2. 构造新向量 ${\mathbf{b}}^{\prime }$：
   $${\mathbf{b}}^{\prime }=\left(\begin{array}{c}{b}_1+d\cdot {\delta }_1\\ b_2+d\cdot {\delta }_2\\ ⋮\\ b_m+d\cdot {\delta }_m\end{array}\right)$$

正确性分析：

令秘密向量 $\mathbf{s}=(s_1,s_2,\dots ,s_n{)}^T$，原始方程：
$$\mathbf{b}=\mathbf{A}\mathbf{s}+\mathbf{e}(\mathrm{mod}q)$$

1. 当 $s_1=d$ 时：
   $${\mathbf{b}}^{\prime }=\mathbf{b}+d\mathbf{\Delta }=\underset{\mathbf{b}}{\underbrace{\mathbf{A}\mathbf{s}+\mathbf{e}}}+d\mathbf{\Delta }$$
   代入 ${\mathbf{A}}^{\prime }$ 的定义：
   $${\mathbf{A}}^{\prime }\mathbf{s}=\left(\mathbf{A}+\left[\begin{array}{cccc}\mathbf{\Delta }& 0& \cdots & 0\end{array}\right]\right)\mathbf{s}=\mathbf{A}\mathbf{s}+s_1\mathbf{\Delta }$$
   因为 $s_1=d$，有：
   $${\mathbf{b}}^{\prime }=\mathbf{A}\mathbf{s}+\mathbf{e}+d\mathbf{\Delta }=\mathbf{A}\mathbf{s}+s_1\mathbf{\Delta }+\mathbf{e}={\mathbf{A}}^{\prime }\mathbf{s}+\mathbf{e}$$
   此时 $({\mathbf{A}}^{\prime },{\mathbf{b}}^{\prime })$ 是合法 LWE 样本。

2. 当 $s_1\ne d$ 时：
   $${\mathbf{b}}^{\prime }=\mathbf{A}\mathbf{s}+\mathbf{e}+d\mathbf{\Delta }=\underset{\text{LWE 结构}}{\underbrace{{\mathbf{A}}^{\prime }\mathbf{s}+\mathbf{e}}}+(d-s_1)\mathbf{\Delta }$$
   其中 $(d-s_1)\ne 0$，且 $\mathbf{\Delta }$ 均匀随机独立于 ${\mathbf{A}}^{\prime }$，因此 $(d-s_1)\mathbf{\Delta }$ 是均匀随机向量，使得 ${\mathbf{b}}^{\prime }$ 与 ${\mathbf{A}}^{\prime }$ 独立。此时 $({\mathbf{A}}^{\prime },{\mathbf{b}}^{\prime })$ 是随机样本。 至此通过DLWE得到了$s_1$

通过以下操作可以恢复整个秘密 $\mathbf{s}$

1. 遍历 $d\in {\mathbb{Z}}_q$，用 DLWE 求解器测试 $s_1=d$。

2. 找到正确的 $s_1$ 后，构造新问题：

   • 更新向量： ${\mathbf{b}}^{(2)}=\mathbf{b}-s_1\cdot \text{第一列}(\mathbf{A})(\mathrm{mod}q)$

   • 更新矩阵： ${\mathbf{A}}^{(2)}=\text{移除 }\mathbf{A}\text{ 的第一列}$

   • 递归求解 $(s_2,\dots ,s_n)$：
     $${\mathbf{b}}^{(2)}={\mathbf{A}}^{(2)}\left(\begin{array}{c}{s}_2\\ ⋮\\ s_n\end{array}\right)+\mathbf{e}(\mathrm{mod}q)$$

5.ss-LWE

1.定义：

$\text{ss-LWE}(m,n,q,B)$：给定随机矩阵$\mathbf{A}{\in }_R{\mathbb{Z}}_q^{m\times n}$、秘密向量$\mathbf{s}\in [-B,B{]}^n$、误差向量$\mathbf{e}{\in }_R[-B,B{]}^m$（$B\ll q/2$），以及样本$\mathbf{b}=\mathbf{A}\mathbf{s}+\mathbf{e}(\mathrm{mod}q)$，目标是恢复秘密向量$\mathbf{s}$。

2.LWE和ss-LWE的等价性

Claim 1 ss-LWE(m,n,q,B)$\le$LWE(m,n,q,B)

显然成立的，ss-LWE只是在LWE基础上加强了对$s$的约束。

Claim 2 LWE(m,n,q,B)$\le$ ss-LWE(m,n,q,B)
**目标：**通过 矩阵分块与逆运算，将LWE的“模 $q$ 随机秘密”转化为ss-LWE的“短误差组合”，利用ss-LWE的求解能力。
步骤：

1. 输入：LWE实例 $(A,\mathbf{b})$，满足 $\mathbf{b}=A\mathbf{s}+\mathbf{e}(\mathrm{mod}q)$，其中 $\mathbf{s}\in {\mathbb{Z}}_q^n$（模 $q$ 随机），$\mathbf{e}\in [-B,B{]}^m$（短误差）。

2. 矩阵分块：

   设 $A=\left[\begin{array}{c}{A}_1\\ A_2\end{array}\right]$（$A_1\in {\mathbb{Z}}_q^{n\times n}$，$A_2\in {\mathbb{Z}}_q^{(m-n)\times n}$），

   $\mathbf{b}=\left[\begin{array}{c}{\mathbf{b}}_1\\ {\mathbf{b}}_2\end{array}\right]$（${\mathbf{b}}_1\in {\mathbb{Z}}_q^n$，${\mathbf{b}}_2\in {\mathbb{Z}}_q^{m-n}$），

   $\mathbf{e}=\left[\begin{array}{c}{\mathbf{e}}_1\\ {\mathbf{e}}_2\end{array}\right]$（${\mathbf{e}}_1\in [-B,B{]}^n$，${\mathbf{e}}_2\in [-B,B{]}^{m-n}$）。

3. 构造ss-LWE实例：

   假设 $A_1$ 可逆（随机矩阵下高概率成立），定义 $A^{\prime }=-A_2{A}_1^{-1}\in {\mathbb{Z}}_q^{(m-n)\times n}$，

   定义新样本：${\mathbf{b}}^{\prime }=A^{\prime }{\mathbf{b}}_1+{\mathbf{b}}_2(\mathrm{mod}q)$。
   $$\begin{array}{rl}{\mathbf{b}}^{\prime }& =-A_2{A}_1^{-1}(A_1\mathbf{s}+{\mathbf{e}}_1)+A_2\mathbf{s}+{\mathbf{e}}_2\\ & =-A_2\mathbf{s}-A_2{A}_1^{-1}{\mathbf{e}}_1+A_2\mathbf{s}+{\mathbf{e}}_2\\ & =A^{\prime }{\mathbf{e}}_1+{\mathbf{e}}_2(\mathrm{mod}q)\end{array}$$
   其中，${\mathbf{e}}_1,{\mathbf{e}}_2$ 是 短向量（因 $\mathbf{e}$ 短），故 $(A^{\prime },{\mathbf{b}}^{\prime })$ 是 合法ss-LWE实例（维度为 $(m-n)\times n$）。

4. 恢复LWE的解：
   若ss-LWE求解器输出 $({\mathbf{e}}_1,{\mathbf{e}}_2)$，则通过分块逆运算可反推原秘密 $\mathbf{s}$（利用 ${\mathbf{b}}_1=A_1\mathbf{s}+{\mathbf{e}}_1$，解线性方程 $A_1\mathbf{s}={\mathbf{b}}_1-{\mathbf{e}}_1$）。

对比维度	LWE（Learning With Errors）	DLWE（Decisional LWE）	ss-LWE（Short-Secret LWE）
问题类型	搜索型问题	决策型问题	搜索型问题（LWE的变体）
核心定义	给定随机矩阵 $\mathbf{A}{\in }_R{\mathbb{Z}}_q^{m\times n}$、样本 $\mathbf{b}=\mathbf{A}\mathbf{s}+\mathbf{e}(\mathrm{mod}q)$，其中 $\mathbf{s}{\in }_R{\mathbb{Z}}_q^n$，$\mathbf{e}{\in }_R[-B,B{]}^m$（$B\ll q/2$）	给定随机矩阵 $\mathbf{A}{\in }_R{\mathbb{Z}}_q^{m\times n}$ 和向量 $\mathbf{c}$，判断 $\mathbf{c}$ 是 $\mathbf{b}=\mathbf{A}\mathbf{s}+\mathbf{e}(\mathrm{mod}q)$（真实样本）还是随机向量 $\mathbf{r}{\in }_R{\mathbb{Z}}_q^m$	给定随机矩阵 $\mathbf{A}{\in }_R{\mathbb{Z}}_q^{m\times n}$、样本 $\mathbf{b}=\mathbf{A}\mathbf{s}+\mathbf{e}(\mathrm{mod}q)$，其中 $\mathbf{s}{\in }_R[-B,B{]}^n$（短秘密），$\mathbf{e}{\in }_R[-B,B{]}^m$（$B\ll q/2$）
目标	恢复秘密向量 $\mathbf{s}$	以显著高于1/2的概率区分 $\mathbf{c}$ 是真实样本还是随机样本	恢复短秘密向量 $\mathbf{s}$
秘密向量约束	$\mathbf{s}{\in }_R{\mathbb{Z}}_q^n$（模 $q$ 均匀随机，无“短”约束）	$\mathbf{s}{\in }_R{\mathbb{Z}}_q^n$（同LWE）	$\mathbf{s}{\in }_R[-B,B{]}^n$（短向量，分量范围远小于 $q$）
误差向量约束	$\mathbf{e}{\in }_R[-B,B{]}^m$（短误差，$B\ll q/2$）	$\mathbf{e}{\in }_R[-B,B{]}^m$（同LWE）	$\mathbf{e}{\in }_R[-B,B{]}^m$（同LWE）
输入参数	$(\mathbf{A},\mathbf{b})$	$(\mathbf{A},\mathbf{c})$（$\mathbf{c}$ 为真实样本或随机向量）	$(\mathbf{A},\mathbf{b})$
与其他问题的关系	与DLWE等价（双向归约）；与ss-LWE等价（双向归约）	与LWE等价（双向归约）	与LWE等价（双向归约）；与ss-DLWE（短秘密决策型LWE）等价
核心特性	格密码核心困难问题，通过带误差的线性方程隐藏秘密	从“判定”角度刻画LWE的困难性，更易用于安全性证明	秘密向量为短向量，更贴近工程直觉，且不降低困难性（与LWE等价）

主要参考：

https://cryptography101.ca/