<p>Since you are specifically interested in <span class="math-container">$q=2$</span>, I will focus on this case in my answer. A note on your choice of tags: you tagged your question with "lattice" and "lattice-theory"; however, your question seems much more closely related to questions in coding theory. I elaborate below.</p>

<p>A good starting point is to observe that LPN with matrix <span class="math-container">$A$</span> reduces to the hardness of decoding a linear code generated by the parity-check matrix <span class="math-container">$B$</span> of <span class="math-container">$A$</span> - or rather, in the decisional case, to distinguishing a codeword from random.</p>

<p><em>proof:</em> for any secret vector <span class="math-container">$s$</span>, <span class="math-container">$B\cdot\chi = B\cdot(As + \chi) \approx_{\mathsf{LPN}} B\cdot U_m = U_{m-n}.$</span></p>

<p>Hence, one can reword your question as follows: for which choice of code matrix is the corresponding decoding problem hard? Coding theory gives essentially the following informal answer: it is hard for most choices of codes. Specifically, there are only few linear codes for which we <em>do</em> know of an efficient decoding algorithms - hardness of decoding seems to be the rule rather than the exception.</p>

<p>Some examples of bad choices of <span class="math-container">$A$</span>: if <span class="math-container">$A$</span> is an LDPC code, then its parity-check matrix <span class="math-container">$B$</span> is sparse, and distinguishing <span class="math-container">$B\cdot\chi$</span> from random is easy (given that <span class="math-container">$\chi$</span> is a distribution over sparse vectors). Reed-Solomon codes can also be decoded efficiently when the noisy codeword has sufficiently low noise rate, hence should be used with care (but if there is enough noise, they should still work).</p>

<p>In general, we do not have any generic reduction stating "if <span class="math-container">$A$</span> has the following structure, then the LPN problem with respect to the matrix <span class="math-container">$A$</span> is as hard as the standard LPN problem." However, we do have good conjectures regarding what properties of <span class="math-container">$A$</span> make the corresponding LPN problem hard. Two of the main such properties is for the code to have a good minimal distance - ideally, meeting the Gilbert-Varshamov bound (which is achieved with good probability by a linear code generated by a uniformly random matrix, corresponding to the standard LPN assumption), and to satisfy the <em>uniform output property</em> (see the next two references). This was investigated in <a href="https://dl.acm.org/citation.cfm?id=2554815" rel="nofollow noreferrer">this paper</a>, where new candidate efficient linear codes (with linear-time encoding) were suggested as plausible candidates for giving an intractable variant of LPN (see also the <a href="http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-get.cgi/2013/MSC/MSC-2013-22.pdf" rel="nofollow noreferrer">master thesis</a> of the first author, specifically the chapter 5).</p>

<p>While LPN with a random parity-check matrix <span class="math-container">$B$</span> is the most well-studied form of the assumption, a bunch of specific alternative choices of code matrix have been used in the cryptography literature. These includes LDPC codes, which are at the core of the famous cryptosystem of Alekhnovich (note that if the code matrix <span class="math-container">$A$</span> is an LDPC code, the LPN variant is insecure; however, when its <em>parity-check matrix <span class="math-container">$B$</span></em> is an LDPC code, meaning that <span class="math-container">$A$</span> is a sparse matrix, then it leads to a plausible assumption), MDPC codes, used to construct variants of the McEliece cryptosystem, quasi-cyclic codes, codes generated by Toeplitz matrices, and others. An overview of candidates which have been used in the literature is given, with pointers, in <a href="https://eprint.iacr.org/2019/273.pdf" rel="nofollow noreferrer">one of my recent papers</a>.</p>

CC BY-SA 4.0
2019-05-08T13:20:59.287Z
2019-05-08T13:20:59.287Z
Geoffroy Couteau
<p><strong>The "usual decisional LWE":</strong>
The challenger and the adversary get a common <strong>random</strong> matrix <span class="math-container">$A \in F_{q}^{m \times n}$</span>. The challenger chooses a secret <span class="math-container">$s \in F_{q}^{n}$</span> and generates random (small) secret noise vector <span class="math-container">$\chi \in F_{q}^{m}$</span>, and the claim is that the adversary can't distinguish efficiently between <span class="math-container">$(A, As + \chi)$</span> and <span class="math-container">$(A, U_{m})$</span> (where <span class="math-container">$U$</span> is the uniform distribution over <span class="math-container">$F_{q}$</span>).</p>

<p><strong>My question:</strong>
Assume that the challenger and adversary do not get <span class="math-container">$A$</span> at random, but rather create <span class="math-container">$A$</span> via some deterministic reduction from some common input <span class="math-container">$x$</span>. All the rest is the same, i.e., the challenger chooses the secret  <span class="math-container">$s \in F_{q}^{n}$</span> and generates random (small) noise vector <span class="math-container">$\chi \in F_{q}^{m}$</span> and then sends to the adversary either <span class="math-container">$As + \chi$</span>, or a true random vector. What conditions does <span class="math-container">$A$</span> have to fulfill to ensure that the challenger can't distinguish between  <span class="math-container">$(A, As + \chi)$</span> and   <span class="math-container">$(A, U_{m})$</span>?</p>

<p>I'm currently more interested in the case of <span class="math-container">$q=2$</span>, i.e., the LPN problem, but even a conclusion on the non-binary scenario may be useful.</p>

<p>I realize this question might be tricky and without an answer, so my hope is to at least get references to articles that either tried to tackle this issue directly or at the very least articles that will be a good entry point for me in the case I'll have to try and solve it myself.</p>

<cc.complexity-theory><lattice><integer-lattice>
Hardness of LWE on not-uniform vector samples
Bartolinio
# Hardness of LWE on not-uniform vector samples

(Asked by: username_0 on 2019-05-06)

**The "usual decisional LWE":**
The challenger and the adversary get a common **random** matrix $A \in F\_{q}^{m \times n}$. The challenger chooses a secret $s \in F\_{q}^{n}$ and generates random (small) secret noise vector $\chi \in F\_{q}^{m}$, and the claim is that the adversary can't distinguish efficiently between $(A, As + \chi)$ and $(A, U\_{m})$ (where $U$ is the uniform distribution over $F\_{q}$).

**My question:**
Assume that the challenger and adversary do not get $A$ at random, but rather create $A$ via some deterministic reduction from some common input $x$. All the rest is the same, i.e., the challenger chooses the secret $s \in F\_{q}^{n}$ and generates random (small) noise vector $\chi \in F\_{q}^{m}$ and then sends to the adversary either $As + \chi$, or a true random vector. What conditions does $A$ have to fulfill to ensure that the challenger can't distinguish between $(A, As + \chi)$ and $(A, U\_{m})$?

I'm currently more interested in the case of $q=2$, i.e., the LPN problem, but even a conclusion on the non-binary scenario may be useful.

I realize this question might be tricky and without an answer, so my hope is to at least get references to articles that either tried to tackle this issue directly or at the very least articles that will be a good entry point for me in the case I'll have to try and solve it myself.

**Tags:** cc.complexity-theory, lattice, integer-lattice

---

## 1 answers

### Answer by username_1 on 2019-05-08. Score: 3 | Accepted answer

Since you are specifically interested in $q=2$, I will focus on this case in my answer. A note on your choice of tags: you tagged your question with "lattice" and "lattice-theory"; however, your question seems much more closely related to questions in coding theory. I elaborate below.

A good starting point is to observe that LPN with matrix $A$ reduces to the hardness of decoding a linear code generated by the parity-check matrix $B$ of $A$ - or rather, in the decisional case, to distinguishing a codeword from random.

*proof:* for any secret vector $s$, $B\cdot\chi = B\cdot(As + \chi) \approx\_{\mathsf{LPN}} B\cdot U\_m = U\_{m-n}.$

Hence, one can reword your question as follows: for which choice of code matrix is the corresponding decoding problem hard? Coding theory gives essentially the following informal answer: it is hard for most choices of codes. Specifically, there are only few linear codes for which we *do* know of an efficient decoding algorithms - hardness of decoding seems to be the rule rather than the exception.

Some examples of bad choices of $A$: if $A$ is an LDPC code, then its parity-check matrix $B$ is sparse, and distinguishing $B\cdot\chi$ from random is easy (given that $\chi$ is a distribution over sparse vectors). Reed-Solomon codes can also be decoded efficiently when the noisy codeword has sufficiently low noise rate, hence should be used with care (but if there is enough noise, they should still work).

In general, we do not have any generic reduction stating "if $A$ has the following structure, then the LPN problem with respect to the matrix $A$ is as hard as the standard LPN problem." However, we do have good conjectures regarding what properties of $A$ make the corresponding LPN problem hard. Two of the main such properties is for the code to have a good minimal distance - ideally, meeting the Gilbert-Varshamov bound (which is achieved with good probability by a linear code generated by a uniformly random matrix, corresponding to the standard LPN assumption), and to satisfy the *uniform output property* (see the next two references). This was investigated in [this paper](https://dl.acm.org/citation.cfm?id=2554815), where new candidate efficient linear codes (with linear-time encoding) were suggested as plausible candidates for giving an intractable variant of LPN (see also the [master thesis](http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-get.cgi/2013/MSC/MSC-2013-22.pdf) of the first author, specifically the chapter 5).

While LPN with a random parity-check matrix $B$ is the most well-studied form of the assumption, a bunch of specific alternative choices of code matrix have been used in the cryptography literature. These includes LDPC codes, which are at the core of the famous cryptosystem of Alekhnovich (note that if the code matrix $A$ is an LDPC code, the LPN variant is insecure; however, when its *parity-check matrix $B$* is an LDPC code, meaning that $A$ is a sparse matrix, then it leads to a plausible assumption), MDPC codes, used to construct variants of the McEliece cryptosystem, quasi-cyclic codes, codes generated by Toeplitz matrices, and others. An overview of candidates which have been used in the literature is given, with pointers, in [one of my recent papers](https://eprint.iacr.org/2019/273.pdf).


---

