2
$\begingroup$

Is the LWE problem easy when the matrix $A$ is sparse?

Recall that the LWE problem is the following: Let $q$ be a prime, let $\chi$ be a distribution of $\textit{small}$ elements over $\mathbb{Z}/q$, and let $n,m$ be two integers (dimensions of vectors that we work with). Sample $s \leftarrow \chi^n$, $e \leftarrow \chi^m$ and $A \leftarrow \mathbb{Z}/q^{m \times n}$, where elements of $A$ are sampled uniformly at random. Let $t=As + e$.

Given $A$ and $t$, find $s$.

This problem is believed to be hard under some reasonable assumptions on $q$, $\chi$, $n$, $m$.

My question is - what is $A$ is a (somewhat) sparse matrix, for example $n=m$, and $A$ has $\approx\sqrt{n}$ non-zero elements in each column, and every non-zero element is $\pm1$. Does the problem remain hard? Or does the problem become trivial? What if I increase $m$ from $m=n$ to something larger?

$\endgroup$

1 Answer 1

2
$\begingroup$

Firstly we should note that this LWE problem with have many solutions whereas LWE problems typically only have one. Let $u_i$ be the $i$th standard basis vector with entry 1 in location $i$ and zero in other positions. Then $$(s',e'):=(s+u_i,e-Au_i)$$ satisfies $As'+e'=t$ and $s'$ differs from $s$ by 1 in a single position while $e'$ differs from $e$ is $O(\sqrt n)$ places by at most 1. This solution will be indistinguishable from $(s,e)$ drawn from Gaussian distributions unless $\sigma$ is very small indeed. It should be clear how to generate a still larger family.

Moreover, it will be easy to find such solutions. One old school method for attacking LWE is to expend a great deal of computation to find a reduced basis for a lattice created by augmenting $A$ to create the following basis $$\left[\begin{matrix}A&I\\ qI & 0\\\end{matrix}\right]$$ and then using Euchner-Schnorr enumeration to solve a close vector problem for the target $(t,0)$ differing by the vector $(-e,s)$. Unless $q$ is very small, by choosing a very sparse $A$ you are presenting a spectacular basis for a sublattice of this augmented lattice given by the first $n$ rows (the vectors are of $L_2$-norm $O(\sqrt n)$ and the augmented lattice is of dimension $2n$ and determinant $q^n$) which will lead to a very easy enumeration problem (further assisted by limitations on the size of the entries of $s$ and $e$ from the problem set up) which will quickly turn up one of these many solutions. One way to think of this is to observe that the entries of $t$ have almost certainly not changed by reducing modulo $q$ which means that the family of solutions all lie in our sublattice with the spectacular basis.

From a cryptographic point of view, basing a system on a private key value $s$ would lead to a family of equivalent private keys which could also be used to take the role of the legitimate user. Likewise, recovering one of these private keys would be very easy indeed.

Increasing $m$ would not remove these problems as I can always throw away the final $m-n$ entries of $t$.

$\endgroup$
5
  • $\begingroup$ Great answer, thanks ! $\endgroup$
    – Kolja
    Jun 30 at 17:25
  • $\begingroup$ I have a follow-up question - so, when $A$ is sparse, it is easy find a solution to the problem. What if we have another $t' = A's + e'$ with the same secret, but a different error, and a completely random matrix $A'$. Is it easy to find $s$ now? I'm saying - let's commit to the secret $s$ with a LWE instance. Is it trivial to find this exact $s$ among the set of solutions to the problem $t=As+e$ with the $A$ matrix sparse? $\endgroup$
    – Kolja
    Jul 22 at 21:25
  • $\begingroup$ I'm not sure if I fully understand what is and is not presented to the attacker. Could you ask this as a new question? $\endgroup$
    – Daniel S
    Jul 22 at 23:44
  • $\begingroup$ Let $s$ be a secret, let $A$ be a sparse matrix, $A'$ a random matrix, $e,e'$ small errors. Further let $t= As+e$ and $t'=As+e'$. $A,A',t,t'$ are presented to the attacker. I will post it as a separate question. $\endgroup$
    – Kolja
    Jul 23 at 20:38
  • $\begingroup$ A new question is posed here. $\endgroup$
    – Kolja
    Jul 25 at 21:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.