Hardness of LPN problem with small secret

Question

The Learning Parity with Noise (LPN) assumption states that, for a fixed secret $s$ chosen uniformly from $\{0,1\}^n$, then the distribution that outputs $(a,a\cdot s+e)$, where $a$ is uniform in $\{0,1\}^n$ and $e$ is sampled according to a Bernoulli distribution $\mathsf{Ber}_\tau$ (with parameter $\tau\in[0,1/2]$), is pseudorandom.

My question is: Does the LPN assumption holds even if $s$ is chosen according to the same distribution as the error, that is, $\mathsf{Ber}_\tau^n$?

In other words, given $s$ from $\mathsf{Ber}^n_\tau$, is the distribution $(a,a\cdot s+e)$ pseudorandom?

Answer 1

There is a simple trick (known in the LWE literature as the Hermite normal form of the problem) that takes an existing LPN problem and transforms it into a problem in which the secret has the same Bernoulli distribution as the error. This trick is proved in Lemma 2 of Applebaum et al. for a more general case, or on the (Ring-)LPN attacks of Kirchner (Section 4.3.2) or Bernstein and Lange (Section 3).

The idea is that you start with a number of $n$ samples $(\mathbf{a}_i, c_i)$, where $c_i = \mathbf{a}_i \cdot \mathbf{s}$. Suppose, now, that some subset of the $\mathbf{a}_i$ vectors is linearly independent (you do not need much more than $n$ randomly-sampled $\mathbf{a}_i$ for this to be the case), and let them form the matrix $M = \{ \mathbf{a}_{i_1}, \dots, \mathbf{a}_{i_k}\}$. Then we have $$\mathbf{c} = M^T\mathbf{s} + \mathbf{e},$$ where $\mathbf{c} = \{ c_{i_1}, \dots, c_{i_k}\}$ and $\mathbf{e} = \{ e_{i_1}, \dots, e_{i_k}\}$ are the corresponding vectors to the chosen $\mathbf{a}_i$. But we also have $$\mathbf{s} = {M^T}^{-1}(\mathbf{c} + \mathbf{e}).$$

Now that we have this matrix $M$, query the LPN oracle with a new sample $\mathbf{u}$, receiving $(\mathbf{u}, v = \mathbf{s}\cdot \mathbf{u} + e)$. But you can convert this into a second oracle that returns $(M^{-1}\mathbf{u}, \mathbf{c}\cdot M^{-1}\mathbf{u} + v)$. Obviously, $M(M^{-1}\mathbf{u}) = \mathbf{u}$. Further, $$ \begin{align} \phantom{=} &\mathbf{e}\cdot M^{-1}\mathbf{u} + e \\ = &(M^T\mathbf{s} + \mathbf{c})\cdot(M^{-1}\mathbf{u}) + e \\ = &M^T\cdot\mathbf{s}\cdot M^{-1}\mathbf{u} + \mathbf{c}\cdot M^{-1}\mathbf{u} + e \\ = &\mathbf{s}\cdot M M^{-1}\cdot u + \mathbf{c}\cdot M^{-1}\mathbf{u} + e \\ = &\mathbf{c} \cdot M^{-1}\mathbf{u} + v. \end{align} $$ So this is now an instance of LPN with Bernoulli-distributed secret $\mathbf{e}$, from which you can extract the original secret as $\mathbf{s} = {M^T}^{-1}(\mathbf{c} + \mathbf{e})$.

In other words, given some algorithm that solves LPN with a Bernoulli-distributed secret, you can also solve regular LPN with the same error distribution.

Answer 2

It seems to me this argument works:

According to Ryan O'Donnell's notes here here, $\tau$ is typically strictly smaller than $1/2$. Even in that case, if the secret $s$ is uniform this is enough to make $a\cdot s$ uniform, assuming the components of $a$ are independently chosen with a biased Bernoulli distribution. Even though each term $a_i \cdot s_i$ in the inner product $a\cdot s$ obeys $$ \mathbb{P}[a_i\cdot s_i=1]=\mathbb{P}[a_i=1]\mathbb{P}[s_i=1]=(1/2)(1-\tau/2):=q \neq 1/2, $$ the distribution of the inner product mod 2 is determined by the probability that the number of 1's in the biased binomial random variable $\text{Binomial}(n,\tau)$ is even or odd.

But since $$\sum_{0 \leq k \leq n} (-1)^k \binom{n}{k} \tau^k(1-\tau)^{n-k}=|1-2\tau|^n$$ the inner product $a\cdot s$ tends to zero with growing $n$ and and so $a\cdot s+e$ is nearly zero for $n$ large enough.

Then $a\cdot s+e$ approaches an unbiased distribution ($e$ is independent of $a\cdot s$) and hence $(a,a\cdot s+e)$ is pseudorandom for $n$ large enough.