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}$.
import numpy as np
from lbpqc.primitives.rng import RNG
from lbpqc.primitives import matrix
from lbpqc.primitives.lattice import embeddings, reductions, fullrank
rng = RNG(0)
m, n, q = 10, 5, 17 # These are parameters for LWE distribution
s = np.array([2,2,1,4,5]) # Here we chose a secret vector
# We sample from LWE distribution, for error distribution we use rounded gaussian with mean = 0 and stddev = q * (1/n) / 2pi
A, b = rng.LWE_dist(q, s, m, "rounded", q, 1 / n)
print("LWE distribution:")
print("A:")
print(A)
print()
print("b:")
print(b)
print("s:")
print(s)
e = b - A@s
print("e = b - As")
print("e:")
print(e)
LWE distribution: A: [[ 4 13 11 0 6] [14 9 0 13 12] [14 2 1 14 0] [ 9 1 5 8 7] [ 6 0 0 2 0] [11 8 11 4 10] [12 6 7 16 13] [16 6 11 16 11] [14 11 11 6 14] [ 2 9 12 14 8]] b: [ 75 158 89 92 20 115 173 175 155 129] s: [2 2 1 4 5] e = b - As e: [ 0 0 0 0 0 0 1 1 0 -1]
Primary attack is achieved by constructing a lattice from our LWE pair $(A, \mathbf{b})$ thru some embedding method and then by using lattice reduction algorithm we can obtain a short vector that should allow us to reconstruct the secret vector $\mathbf{s}$.
First we will reduce the LWE problem to BDD by constructing the associated q-ary lattice
$$
\mathcal{L'} = \left\{ \mathbf{y'} \in \mathbb{Z}^m : \mathbf{y'} = A\mathbf{x'}\mod q, \quad \forall \mathbf{x'} \in \mathbb{Z}^n \right \}
$$
We can try to solve the BDD directly by using babai's nearest plane algorithm, or furthemore reduce the BDD to SVP with Kannan's embedding.
Let's first try solving BDD.
print("LWE as BDD problem:")
BDD_Basis = embeddings.q_ary_basis(A, q)
print(BDD_Basis)
LWE as BDD problem: [[ 1 0 0 0 0 13 1 10 2 1] [ 0 1 0 0 0 7 2 9 16 10] [ 0 0 1 0 0 13 13 1 13 10] [ 0 0 0 1 0 5 0 14 2 5] [ 0 0 0 0 1 7 6 14 4 5] [ 0 0 0 0 0 17 0 0 0 0] [ 0 0 0 0 0 0 17 0 0 0] [ 0 0 0 0 0 0 0 17 0 0] [ 0 0 0 0 0 0 0 0 17 0] [ 0 0 0 0 0 0 0 0 0 17]]
When solving BDD with babai's nearest plane algorithm we use vector $\mathbf{b}$ as our target vector.
The nearest plane algorithm will give us some close lattice vector $\mathbf{w}$ that satisfies $\mathbf{w} = A\mathbf{x'} \mod q$ for all $x \in \mathbb{Z}^n$ and since the error vector $\mathbf{e}$ is relatively short, we can expect that $\mathbf{w} = A\mathbf{s} \mod q$ where $\mathbf{s}$ is a secret we are looking for.
In order to obtain the secret vector we need to solve linear system of equations, we can use Gaussian-Jordan elimination for that. One caveat is that we are solving the system in $\mathbb{Z}_q$.
w = reductions.babai_nearest_plane(BDD_Basis, b).astype(int)
Aw = np.block([A, w.reshape(-1,1)])
R, _ = matrix.mod_RREF(Aw, q)
# since we have more equations than variables, after first elimination we fill with zeros the redundant rows
# after that, in order to solve the system we perfom second elimination only on the first n rows
sw = matrix.mod_RREF(R[:len(s)], q)[0][:, -1]
print("recovered secret:")
print(sw)
print("true secret:")
print(s)
recovered secret: [2 2 1 4 5] true secret: [2 2 1 4 5]
Now we can use Kannan's embedding.
For Kannan's embedding we define the embedding lattice $\mathcal{L_K}$ as follows
$$
\mathcal{L_K} := \left\{ \mathbf{y} \in \mathbb{Z}^{m + 1} : \mathbf{y} = \bar{A}x \mod q, \quad \forall \mathbf{x} \in \mathbb{Z}^{n+1}, \bar{A} = \begin{pmatrix} A & \mathbf{b} \newline \mathbf{0} & 1 \end{pmatrix}
\right \}
$$
If the columns of the matrix $\bar{a}$ are linearly independed (given the nature of LWE there is a very high chance they are), then $\mathbf{v}^T = (\mathbf{e}^T| 1)$ is a short vector in the lattice. We can find it by using some lattice reduction algorithm e.g. LLL.
Recall that $A\mathbf{s} = \mathbf{b} - \mathbf{e}$, so we can solve for $\mathbf{s}$ using the same technis as for BDD.
Id = lambda n: np.identity(n, int)
Zn = lambda m, n: np.zeros((m,n), int)
Ad = np.block([[A, b.reshape(-1, 1)], [Zn(1, n), np.array([1])]])
Kannans_Basis = embeddings.q_ary_basis(Ad, q)
print("Kannan's embedding")
print(Kannans_Basis)
Kannan's embedding [[ 1 0 0 0 0 13 0 9 2 2 16] [ 0 1 0 0 0 7 0 7 16 12 15] [ 0 0 1 0 0 13 0 5 13 6 4] [ 0 0 0 1 0 5 0 14 2 5 0] [ 0 0 0 0 1 7 0 8 4 11 11] [ 0 0 0 0 0 17 0 0 0 0 0] [ 0 0 0 0 0 0 1 1 0 16 1] [ 0 0 0 0 0 0 0 17 0 0 0] [ 0 0 0 0 0 0 0 0 17 0 0] [ 0 0 0 0 0 0 0 0 0 17 0] [ 0 0 0 0 0 0 0 0 0 0 17]]
v = reductions.LLL(Kannans_Basis).astype(int)[0]
print("v should have a form of (e | 1) where e is LWE noise vector so A * s = b - v")
print("v:")
print(v)
print("e:")
print(e)
print()
As = b - v[:m] if v[-1] == 1 else b + v[:m]
Aw = np.block([A, As.reshape(-1,1)])
R, _ = matrix.mod_RREF(Aw, q)
ss = matrix.mod_RREF(R[:len(s)], q)[0][:, -1]
print("recovered secret:")
print(ss)
print("true secret:")
print(s)
v should have a form of (e | 1) where e is LWE noise vector so A * s = b - v v: [ 0 0 0 0 0 0 -1 -1 0 1 -1] e: [ 0 0 0 0 0 0 1 1 0 -1] recovered secret: [2 2 1 4 5] true secret: [2 2 1 4 5]