LWE问题的学习

容错学习问题 （LWE问题， Learning With Errors）是一个机器学习领域中的怀疑难解问题，由Oded Regev 在2005年提出，他因此赢得2018年哥德尔奖。这是一个极性学习问题的一般形式。

定义

随机选取一个矩阵 \[ A ∈ Z^{m*n}_q \] 一个随机向量 \[ s \in Z^{n}_q \] 一个随机向量 \[ e \in \xi ^{m} \] 输出 \[ g_A(s,e)=As+e(mod \ q) \] 一个LWE问题是，给定一个矩阵 A，和LWE系统的输出 ,还原s。

假如我们先没有这噪音部分

其实感觉来说更像是解决一种线性方程组

例如 \[ 3x_1+4x_2+x_3=0\\ 4x_1+2x_2+5x_3=1\\ 2x_1+x_2+x_3=1 \] 构成矩阵的话是这样的 \[ \begin{pmatrix} 3 & 4 &1 \\ 4 & 2 &5 \\ 2 & 1 &1 \end{pmatrix} *\begin{pmatrix} x_1\\ x_2\\ x_3 \end{pmatrix}=\begin{pmatrix} 0 \\ 1 \\ 1 \end{pmatrix} \] 用矩阵的形式来表示之后，这个问题求解的方法也和之前的方法一样：我们可以把矩阵和的行与行之间相加或相减，然后最后得到未知数的结果。我们把这一类行与行之间操作求解未知数的方法统称为高斯消除法（Gaussian Elimination）。

其实LWE问题就是有噪音的高斯消除问题

但是多了一个e的话，之前的办法是行不通的

其中e是我们在一个固定数值范围内随机采集的一个随机噪音向量，能否有效的通过A和LWE系统的输出（向量b） 的值来还原最初的未知数向量

加上这么一个随机噪音之后，我们线性代数的方法就已经不管用了，因为如果我们使用高斯消除法对每一行进行消除的时候，同时还会带着噪音进去，所以导致无法算出任何一个未知数的值。

这也是LWE的难点

能想到与其相关应该是CVP，最近向量问题。无限逼近向量b。

例题

LWE?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
from secret import secret
assert len(secret)==66*3
sec = [ord(x) for x in secret]

DEBUG = False
m = 66
n = 200
p = 3
q = 2^20

def errorV():
  return vector(ZZ, [1 - randrange(p) for _ in range(n)])

def matrixMn():
  return matrix(ZZ, [[q//2 - randrange(q) for _ in range(n)] for _ in range(m)])

A, B, C = matrixMn(), matrixMn(), matrixMn()
x = vector(ZZ, sec[0:m])
y = vector(ZZ, sec[m:2*m])
z = vector(ZZ, sec[2*m:3*m])
e = errorV()
b = x*A+y*B+z*C+e

if DEBUG:
  print('x = %s' % x)
  print('y = %s' % y)
  print('z = %s' % z)
  print('e = %s' % e)
print('A = \n%s' % A)
print('B = \n%s' % B)
print('C = \n%s' % C)
print('b = %s' % b)


\[ b=x*A+y*B+z*C+e \]

可是这样我们怎么联想到LWE上呢 \[ x*A+y*B+z*C \] 可以看出这样 \[ X=( x, y,z)\\ A=\begin{pmatrix} A \\ B \\ C \end{pmatrix} \] 这样就构成了我们喜欢的样子

我们已知A,B,C,b

我们如何求出e呢 \[ b=AX+e \] 然后构造矩阵 $$ L= \[\begin{pmatrix} A &b\\ 0&B \\ \end{pmatrix}\]

\[ 然后 \] \[\begin{align} \begin{pmatrix} A &b\\ 0&B \\ \end{pmatrix} *\begin{pmatrix} -x\\ 1\\ \end{pmatrix}= \begin{pmatrix} e\\ B \\ \end{pmatrix} \end{align}\] $$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

from Crypto.Util.number import *
import gmpy2
import re

m = 66
n = 200
p = 3
q = 2^20

with open ("C:\\Users\\zxrdfw\\Desktop\\out","r") as f:
    data = f.read().split('\n')
    f.close()

A = matrix(m, n, [int(j) for i in data[1: m + 1] for j in re.findall(r'-?\d+', i)])
B = matrix(m, n, [int(j) for i in data[m + 1: 2 * m + 2] for j in re.findall(r'-?\d+', i)])
C = matrix(m, n, [int(j) for i in data[2 * m + 2: 3 * m + 3] for j in re.findall(r'-?\d+', i)])
b = vector([int(j) for i in data[3 * m + 3:] for j in re.findall(r'-?\d+', i)])

A = block_matrix([[A], [B], [C]])
M = block_matrix([[A, matrix(3 * m, 1, [0] * 3 * m)], [matrix(b), matrix([1])]])
e = M.LLL()[0][:n]
x = A.solve_left(b - e)
for i in x:
    print(chr(i),end="")

参考：

https://blog.csdn.net/qq_51999772/article/details/127316643?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522167998694716800180666536%2522%252C%2522scm%2522%253A%252220140713.130102334.pc%255Fall.%2522%257D&request_id=167998694716800180666536&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2allfirst_rank_ecpm_v1~rank_v31_ecpm-1-127316643-null-null.142