4
$\begingroup$

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?

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

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.