# Finding the exact solution of an LWE instance with a sparse matrix

I already asked a question about the feasibility of LWE when the matrix A is sparse or small here.

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?

I was provided a good answer showing that when $$A$$ is small/sparse, the solution to the LWE problem is not unique, and a solution can be easily found.

My question is the following: can the exact solution of the above problem be found, if it is committed to via another regular LWE instance. In other words:

Let $$s \leftarrow \chi^n$$; $$e,e' \leftarrow \chi^n$$, let $$A$$ be a sparse matrix ($$n=m$$, $$\sqrt{n}$$ non-zero elements, each equal to $$\pm 1$$), and let $$A'$$ be a uniformly random matrix. Let $$t=As+e$$ and $$t' = A's+e'$$.

Given $$t$$ and $$t'$$ can we find $$s$$?

• How about this paper eprint.iacr.org/2018/741? This paper says that if $A$ is binary, LWE with $A$ is broken. Commented Jul 26, 2022 at 9:12
• This helps a lot. Thanks. It doesn't directly provide an answer to the problem, right? I'm considering an $n\times n$ matrix, for which I know there are many solutions in the sparse matrix case, and I want to find one specific solution committed to in a separate LWE instance. Commented Jul 29, 2022 at 3:19

Let's view this is an LWE with side information problem. That is, you're intending to attack $$({\bf A}, {\bf b} = {\bf A}{\bf s} + {\bf e})$$, and you're presented with auxiliary information $$({\bf A'}, {\bf b}' = {\bf A}{\bf s} + {\bf e}')$$.

Since solving for any one of the many solutions $${\bf s}'_1, ..., {\bf s}'_k$$ is easy (since $${\bf A'}$$ is not only sparse, but ternary), a naïve way to view the side information $$({\bf A}', {\bf b}')$$ is that you're presented with a auxiliary set $$S = \{{\bf s}'_1, ..., {\bf s}'_k\}$$ of possible values of $${\bf s}.$$ Obviously, if $$|S| = k$$ is $${\sf poly}(n),$$ there is a simple polynomial-time attack by enumerating the $${\bf s}_i'.$$ Similarly -- in concrete analysis -- if enumerating $$|S|$$ ($$2^{30}$$? $$2^{40}$$? etc.) is within your computational bounds, the problem is immediately concretely easy. So, the more interesting situation is when $$|S| = {\sf superpoly}(n).$$ (As this is just meant to be a comment, I haven't bothered to check $$|S|$$ for this, or other possible, distribution(s) of the auxiliary $$({\bf A}', {\bf b}')$$ -- but for any problem of this form, that is the first step to perform, of course.)

However, more information is clearly present in the presented auxiliary value $$({\bf A}', {\bf b}')$$ than simply the set $$S.$$

For example, given $${\bf A}'$$, for each candidate-solution $${\bf s}_i' \in S$$, it is easy to derive the corresponding induced candidate-error term $${\bf e}_i'.$$

Note that the $${\bf e}_i'$$ will be in the support of the corresponding distribution $$\chi^n$$. However, the various $${\bf e}_i'$$ will not occur with equal probability under i.i.d. sampling of $$\chi^n$$.

Intuitively, for each candidate $${\bf s}_i' \in S$$, what I want to do is check whether $${\bf s}_i'$$ is indeed the solution $${\bf s}$$ of $$({\bf A}, {\bf b})$$. (You can do the obvious thing -- subtract $${\bf A}{\bf s}_i'$$ off $${\bf b}$$ and check if the result is short.)

However, if I could somehow cheaply order my enumeration through the $${\bf s}_i'$$ according to the probability that the induced $${\bf e}_i'$$ would be sampled from $$\chi^n,$$ I will clearly do much better in total attack cost in expectation than $$\tilde O(|S|)$$. (Such ordering is, of course, possible in principle -- finding a way to do it that gives a speed-up is the important question. Details left to the person who will actually answer this question. =))

Further, I wanted to point out that if there is a way to "shoe-horn" the auxiliary information provided by $$({\bf A}', {\bf b}')$$ into the format of, e.g., the Distorted Bounded Distance Decoding (DBDD) approach of Dachman-Soled et al. (cf. https://eprint.iacr.org/2020/292.pdf), then you should be able to very cleanly derive a good cost estimate of this problem (for many variant distributions of the sparse/short $${\bf A}'$$) using that single DBDD framework.

Edit: An extra, parting thought-- An interesting approach might be to artificially add additional error (in some controlled way) to the $$({\bf A}', {\bf b}')$$ auxiliary information before attempting to enumerate a solution set $$S$$. Note that if I increase the error, it seems I might be able to 'naturally eliminate' potential $${\bf s}_i'$$ candidates that induce error terms $${\bf e}_i'$$ that are on the 'tails' of the $$\chi^n$$ distribution. An approach like this seems to naturally restrict the set $$S$$ toward solutions that are more likely on average to be the solution $${\bf s}$$ to the primary instance $$({\bf A}, {\bf b})$$. Good luck!

• I never considered the number of solutions ($|S|$) of $As+e$, is it indeed polynomial? If it is, and if all the solutions can be enumerated, the problem becomes trivial. Commented Aug 4, 2022 at 15:59
• I can comment now - thanks! $|S|$ depends heavily on the distribution of $A, s$ and $e$. For natural choices, it is polynomial; for other natural choices, it is exponential. For some natural choices of dist that lead to polynomially-bounded $S$, finding one element of $S$ is hard; for other natural choices of dist that are polynomially-bounded, find every element of $S$ is easy. If we assume there is a good motivation for this question, then answering these questions is the content of a publishable paper (outside the scope of SE =)). I would first ask (yourself) - why do you care? =) Commented Aug 5, 2022 at 2:01
• Example: In the typical LWE-crypto setting (let $A, s$ be uniform and $e \leftarrow \chi$ for "typical" $\chi,$) then $|S| = 1.$ (This is what leads to a correctly decryptable ciphertext.) -- Or, modify the above so that $A = I_n$ for the $n$-by-$n$ identity matrix $I_n.$ Now $|S| = |{\sf support}(\chi)| = B^n = \Omega(2^n)$ where $B$ is the number of valid coordinates per individual error term of $e$. Commented Aug 5, 2022 at 2:04
• Maybe you misunderstood my comment, I was asking if $|S|$ was polynomial in size when $A$ is a sparse matrix with $\pm1$ as only non-zero values. The problem is related to a different more practical issue, but I preferred to explain it in simplest terms through a generic LWE instance. Commented Aug 5, 2022 at 16:05