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.


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, 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 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.


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.