LWE study

Lyutoon

cryptographyalgorithm

发布于：2021年3月15日

次浏览

Learning With Errors

1. What is LWE?

Here Oded Regev gives a definition of LWE :

2. Get started

linear system of equations:

if we want to get the value of $x_1, x_2, x_3$, we can use Gaussian Elimination to solve this problem. Or we can just use matrix to represent this problem:

LWE settings:

How about add an small error term $e?$

This time, we get:

Or in other words, we can represent it in matrix style where $e$ is the error term:

Then now we put the equations into finite field:

Then we need to recover the secret $x$.

General situation:

As the same, we need to recover $s.$ Where $e$ is small.

Then from this equation we can construct a lattice $L$ that satisfies:

Our target is to recover secret $s.$

Solve LWE

Step 1: LLL algorithm

First we apply LLL algorithm to lattice $L$ to get a good basis.

Step 2: Solve CVP using Babai’s algorithm

We know that there is a close vector named $b$ that belongs to $L$ and is close to $a$ because $e$ is small which is a CVP. So we can solve for $b$ using Baibai’s algorithm to get rid of the error term $e$ which is:

so we just need to solve this equation over the ring mod p.

Example code

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
35
36
37
38
39
40
41

def Babai_closest_vector(L, w):
    '''
    Yet another method to solve apprCVP, using a given good basis.
    INPUT:
    * "L" -- a matrix representing the LLL-reduced basis (v1, ..., vn) of a lattice.
    * "w" -- a target vector to approach to.
    OUTPUT:
    * "v" -- a approximate closest vector.
    Quoted from "An Introduction to Mathematical Cryptography":
    In both theory and practice, Babai's closest plane algorithm
    seems to yield better results than Babai's closest vertex algorithm.
    '''
    G, _ = L.gram_schmidt()
    t = w
    i = L.nrows() - 1
    while i >= 0:
        w -= round( (w*G[i]) / G[i].norm()^2 ) * L[i]
        i -= 1
    return t - w

A_value = [...] # exactly 'A' in General situation
b_value = [...] # exactly 'a' in General situation
m = ... 
n = ...
p = ...
# construct the lattice L after applying LLL
Lattice = matrix(ZZ, m + n, m)
for x in range(m):
    for y in range(n):
        Lattice[m + y, x] = A_value[x, y]
    Lattice[x, x] = p
lattice = IntegerLattice(Lattice, lll_reduce=True)
print('LLL done')
# prepare for Babai's algorithm
target = vector(ZZ, b_value)
closest_v = Babai_closest_vector(lattice.reduced_basis, target)
print('Find closest vector:{} '.format(closest_v))
# solve the equation: A*s = b
A_LWE = matrix(Zmod(p), A_value)
s = A_LWE.solve_right(closest_v)
print(s)

Solve LWE by solving SVP

After participating in 天融信杯 I have searched a lot of papers to find how to solve LWE problem in a faster way. So it comes a method called Embedding method to convert CVP to SVP:

Always, we set $M=1$ to increase the chance that BKZ will return the correct answer.

Also there will be some optimization to help us solve LWE.

Conclusion

Solving LWE problem is NP hard which can be reduced to CVP, SVP . So is we wanna solve LWE we mush solve CVP, SVP first or we must solve NP problem. In other words, we can make lattice reduction algorithm faster to help us solve LWE much more easily. Low dimention only!!

更新于：2021年3月15日