格密码-LWE问题-海口c网

格密码-LWE问题

article/2025/6/30 12:24:23

格密码是一种备受关注的 PQC 算法，其安全性基于最坏情况下格问题的困难性，它是来自于 Regev 密码系统和 Lyubashevsky-Peikert-Regev 密码系统的思想。

2022 年，NIST 完成了 PQC 第三轮标准化过程，共有四种候选算法被选中进行标准化，包括 PKE/KEM 算法 CRYSTALS-Kyber，数字签名算法 CRYSTALS-Dilithium， Falcon 和 SPHINCS+。

格密码学是利用 $R_{n}$ 中格点上的困难问题作为安全密码系统的基础。格密码的优势包括抵抗量子攻击的安全性假设，算法的简单性、有效性和并行性，最坏情况下困难问题的强安全保障以及有通用的结构。

格中的数学困难问题主要包括:

- 最坏情况下最短向量问题（Shortest Vector Problem，SVP）
- 最近向量问题（Closest Vector Problem，CVP）
- 平均情况下的最小整数解（Shortest Integer Solution，SIS）问题
- 错误学习（Learning With Errors，LWE）问题

这些问题是被认为能够抵抗量子计算攻击的。

一、LWE问题简介

容错学习(learning with errors, LWE)问题就是求解带噪声的线性方程组问题, 由Oded Regev在[Reg05] 中提出, 他也因此结果荣获2018年的哥德尔奖. LWE问题的困难性基于的复杂性假设非常弱, 但是功能却异常强大, 由于LWE问题尚无有效的量子求解算法, 因此基于LWE假设的加密方案被认为是抗量子的。
LWE问题是求解带噪声的线性方程组问题. LWE问题的困难性基于的复杂性假设非常弱, 但是功能却异常强大, 由于LWE问题尚无有效的量子求解算法, 因此基于LWE假设的加密方案被认为是抗量子的.由于LWE的结构具有效率高的特点，LWE或其相关问题被广泛用于构造抵抗量子计算攻击的PKE/KEM密码方案。

二、求解线性方程组

假设挑战者(challenger)有一个n维向量s，但出于某种原因，挑战者并不将这一向量公开；
作为攻击者(adversery)可以要求挑战者提供方程(一般是模p同余方程)，挑战者可以根据某种分布生成随机的系数向量 $a_{i}$ ,并且计算出 $a_{i}\cdot s=b_{i}$ ,并将 $(a_{i},b_{i})$ 发送给攻击者；
因此，只要满足在 $a_{1}$ ， $a_{2}$ ,...., $a_{m}$ 中选出一个n元线性无关向量组，就可以求解这个方程
但是这样显然不安全，为了使攻击者不能破解出向量s，我们可以对我们给出的结果增加一些误差。

增加误差

我们在每次生成 $a_{i}$ 时，还可以根据误差项分布 $\chi$ 生成一个误差项 $e_{i}$ ,令 $a_{i}\cdot s+e_{i}=b_{i}$ ,此时仍将 $(a_{i},b_{i})$ 发送给挑战者
由于对于攻击者，误差项分布 $\chi$ 未知，因此问题较之前变得复杂，事实上，这是一个NP难的问题
一般定义 $s,a_{i}\in Z^n_{q}$ , $e_{i}\in \chi$ ,而 $b_{i} = s\cdot a_{i}+e_{i}mod p$ ,因此 $b_{i}\in Z_{q}$
由于 $a_{i}$ 是随机选取的，而 $b_{i}$ 是在与 $Z^n_{q}$ 上随机选取出的向量进行运算并加上 $e_{i}\in \chi$ 而得到的，因而定义 $(a_{i},b_{i})$ 服从一个新的分布 $LWE_{p,\chi }$ ,称该分布为LWE分布，其定义在 $Z^n_{q}\times Z_{q}$ 上。
有的地方将LWE分布记作 $LWE_{s,\chi }$
由于该问题定义在离散的情况下，因此将其称为格上问题。

矩阵形式

在一般应用中，通常会将LWE问题写作矩阵形式，即把 $b_{i},e_{i}$ 都写作向量形式 $b\in Z^m_{p}$ , $e\in \chi ^m$ ,将 $a_{i}$ 写作矩阵形式 $A\in Z^{m\times n}_{p}$
由此可将等式写作 $b^T = As^T+e^T(mod p)$

三、LWE问题

最基本的LWE问题有两个版本，且这两个问题之间存在多项式时间的规约。

3.1 探索LWE问题

探索LWE问题(search LWE)问题即： $SLWE_{n,p,\chi ,m}$ ,定义为：给定服从 $LWE_{p,\chi }$ 的Oracle，在最多进行m次访问的情况下求出n维向量s；
一般来说，要求m是一个关于n的多项式，即 $m=m(n)$ 是一个多项式函数，对于一个只能在概率多项式时间内运行的攻击者是无法有充足的时间访问超多项式次Oracle的(给的时间太多了)

3.2 判定LWE问题

判定LWE问题(decision LWE)即： $DLWE_{n,p,\chi ,m}$ 定义为给定m个来自以下两个分布 $LWE_{p,\chi }$ 和 $Z^n_{q}\times Z_{q}$ 上的均匀分布，要求以不可忽略的优势区分这两种情况
有时候定义为判定问题，要求如果拿到的是 $LWE_{p,\chi }$ 分布，输出1为正确答案；