LWE问题初探

Vect0r / 2023-05-03 / 原文

最近发现了格问题的极致恶心，所以还是得系统学一下；

LWE问题

1. 基本概念

对于已知一个矩阵 A 和一个向量 b ，他们满足关系式：\(b=As+e\)，e 为变换过程中的噪声向量，其值比较小，通过已知条件还原 s 称为LWE问题，又被称为误差还原，也是机器学习领域的一个容错学习问题；
对于基本的线性方程组求解：\(b=As\)问题，我们可以通过高斯消除法进行比较轻松的求解，但是对于引入噪声的情况，高斯消除法的消元过程会不断地放大噪声，导致最后的结果差异较大，所以我们应该采取更加合适的方法；
对于LWE问题，我们所得的 As 需要非常接近结果 b ，这和 CVP 问题又有了莫名地相似，也是一个 NP-hard 问题；

2. 分析过程

对于LWE问题，我们都是在有限域 p 上进行研究，称为 R-LWE 问题，主要探究是我们所需要求解的环多项式在受到随机噪声环多项式干扰的情况下，如何恢复目标多项式（均表示成向量或者矩阵的形式进行运算）；
所以它的基本表达式为\(As+e \equiv c \ (mod \ p)\)，可以转换为：

\[s_0a_{i,0}+s_1a_{i,1}+……+s_na_{i,n} \equiv c_i-e_i\ (mod\ p) \]

进一步得到：

\[s_0a_{i,0}+s_1a_{i,1}+……+s_na_{i,n}+e_i+k_ip\equiv c_i \]

之后构造格子 L ：

然后对格 L 使用 LLL 算法，得到无噪声下的最短向量 x（一个 good basis），然后再将 x 和 c 通过 babai 算法，求得在格基为 x 情况下 c 的 CVP 最近向量，这就是\(c-e\)的值，记为 b ，又因为：

\[A_{LWE}s=b^T \]

所以可以直接求得 s 的值；

3. 脚本实现

这里借用Lazzaro大佬的脚本 @ https://lazzzaro.github.io

点击查看代码

# Sage
from sage.modules.free_module_integer import IntegerLattice

row = 
column = 
prime = 

ma = 
res = 

W = matrix(ZZ, ma)
cc = vector(ZZ, res)

Babai's Nearest Plane algorithm
def Babai_closest_vector(M, G, target):
    small = target
    for _ in range(5):
        for i in reversed(range(M.nrows())):
            c = ((small * G[i]) / (G[i] * G[i])).round()
            small -=  M[i] * c
    return target - small

A1 = matrix.identity(column)
Ap = matrix.identity(row) * prime
B = block_matrix([[Ap], [W]])
lattice = IntegerLattice(B, lll_reduce=True)
print("LLL done")
gram = lattice.reduced_basis.gram_schmidt()[0]
target = vector(ZZ, res)
re = Babai_closest_vector(lattice.reduced_basis, gram, target)
print("Closest Vector: {}".format(re))

R = IntegerModRing(prime)
M = Matrix(R, ma)
M = M.transpose()

ingredients = M.solve_right(re)
print("Ingredients: {}".format(ingredients))

m = ''
for i in range(len(ingredients)):
    m += chr(ingredients[i])
print(m)