# Hardness of LPN problem with small secret

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?

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.

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.