In [ ]:

!pip install "pqlattice[fast]"

!pip install "pqlattice[fast]"

Primary attack on search-LWE problem¶

In this notebook we are going to solve search-LWE by using primary attack.
First let's define the LWE.
Given parameters $n, q \in \mathbb{Z} $ and some non-uniform probability distribution $\chi$ on $\mathbb{Z}_q$ we define an LWE sample $(\mathbf{a},b)$ for a secret vector $\mathbf{s} \in {\mathbb{Z}^n_q}$ as follows $$ \begin{align*} \mathbf{a} &\leftarrow \operatorname{Uniform}(\mathbb{Z}^n_q) \newline b &:= \langle \mathbf{a}, \mathbf{s}\rangle + e \end{align*} $$ where error $e$ is sampled from $\chi$ distribution. $$ \mathbf{e} \leftarrow \chi $$ As we take more samples, we can arrange them into a matrix/vector form. So for $m$ samples we define matrix $A \in \mathbb{Z}^{m\times n}_q$ to be obtained from uniform distribution and use vector $\mathbf{e} \in \mathbb{Z}^m$ for error $$ \begin{align*} A &\leftarrow \operatorname{Uniform}(\mathbb{Z}^{m\times n}_q) \newline \mathbf{e} &\leftarrow \chi^{m} \newline \mathbf{b} &:= A\mathbf{s} + \mathbf{e} \end{align*} $$ For search-LWE problem, given only pair $(A, \mathbf{b})$ we need to obtain secret vector $\mathbf{s}$.

In [1]:

import pqlattice as pq
import numpy as np
import math
pq.settings.set_backend("fast")

import pqlattice as pq import numpy as np import math pq.settings.set_backend("fast")

In [2]:

n = 14
sigma = 2
q = 1000
m = 50
secret_dist = "ternary"

possible_values = []
if secret_dist == "binary":
    possible_values = [0, 1]
elif secret_dist == "ternary":
    possible_values = [-1, 0, 1]

n = 14 sigma = 2 q = 1000 m = 50 secret_dist = "ternary" possible_values = [] if secret_dist == "binary": possible_values = [0, 1] elif secret_dist == "ternary": possible_values = [-1, 0, 1]

In [3]:

lwe = pq.random.LWE(n, q, sigma, secret_dist, 80)
secret = lwe.secret
A, b = lwe.sample_matrix(m)

lwe = pq.random.LWE(n, q, sigma, secret_dist, 80) secret = lwe.secret A, b = lwe.sample_matrix(m)

In [4]:

K = pq.lattice.embeddings.kannan(A, b, q)
pq.show(K)

K = pq.lattice.embeddings.kannan(A, b, q) pq.show(K)

Matrix of integers with shape: 65 x 65
======================================
       [0]   [1]   [2]   [3]   [4]  ...  [60]  [61]  [62]  [63]  [64]
 [0]  1000     0     0     0     0  ...     0     0     0     0     0
 [1]     0  1000     0     0     0  ...     0     0     0     0     0
 [2]     0     0  1000     0     0  ...     0     0     0     0     0
 [3]     0     0     0  1000     0  ...     0     0     0     0     0
 [4]     0     0     0     0  1000  ...     0     0     0     0     0
 ...   ...   ...   ...   ...   ...  ...   ...   ...   ...   ...   ...
[60]   398   382   764   104   492  ...     1     0     0     0     0
[61]   247   361     4   249   799  ...     0     1     0     0     0
[62]   173   606   153   649   685  ...     0     0     1     0     0
[63]   968   177   540   508   354  ...     0     0     0     1     0
[64]   -16  -549  -665  -753  -979  ...     0     0     0     0     1

In [5]:

L = pq.lattice.lll(K)
print(pq.linalg.norm(L[0]))

L = pq.lattice.lll(K) print(pq.linalg.norm(L[0]))

13.30413469565007

In [6]:

B = pq.lattice.bkz(L)
print(pq.linalg.norm(B[0]))

B = pq.lattice.bkz(L) print(pq.linalg.norm(B[0]))

13.30413469565007

In [7]:

v = B[0]
e = v[:m]
s = v[m:m + n]

print("Recovered noise: ", e)
print()
print("Recovered secret:", s)
print("True secret:     ", secret)

v = B[0] e = v[:m] s = v[m:m + n] print("Recovered noise: ", e) print() print("Recovered secret:", s) print("True secret: ", secret)

Recovered noise:  [-1 -4 -1 -3 0 1 0 0 1 3 2 0 2 1 -1 -1 1 6 0 0 -1 1 0 2 -1 1 0 -2 2 1 1 0
 1 0 1 -2 0 -2 -3 1 -1 3 -2 1 -1 3 3 -2 2 -1]

Recovered secret: [1 0 1 1 1 0 -1 0 1 0 1 1 1 0]
True secret:      [1 0 1 1 1 0 -1 0 1 0 1 1 1 0]