4
$\begingroup$

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$?

$\endgroup$
2
  • 2
    $\begingroup$ How about this paper eprint.iacr.org/2018/741? This paper says that if $A$ is binary, LWE with $A$ is broken. $\endgroup$ Commented Jul 26, 2022 at 9:12
  • 1
    $\begingroup$ 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. $\endgroup$
    – Kolja
    Commented Jul 29, 2022 at 3:19

1 Answer 1

1
+50
$\begingroup$

This is not intended as an answer, but hopefully a helpful comment. (Apparently I don't have the reputation on this website to leave a comment -- apologies.)

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!

$\endgroup$
4
  • 1
    $\begingroup$ 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. $\endgroup$
    – Kolja
    Commented Aug 4, 2022 at 15:59
  • $\begingroup$ 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? =) $\endgroup$ Commented Aug 5, 2022 at 2:01
  • $\begingroup$ 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$. $\endgroup$ Commented Aug 5, 2022 at 2:04
  • $\begingroup$ 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. $\endgroup$
    – Kolja
    Commented Aug 5, 2022 at 16:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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