Quantifying the success probability of brute force attack against (search) LPN

Question

I've been trying to learn about attacks on LPN ($n$-bit secret, noise rate $\eta$), and have found several allusions to a brute force algorithm that runs in time exponential in $n$ and requires a linear number of samples in $n$. For example, the third slide of this deck or the original BKW paper. That said, I have not been able to find the success probability of this algorithm, nor derive it myself.

LPN challenger:

• upon initialization, chooses random $s \in \mathbb{Z}_2^n$
• when queried, chooses random $a \in \mathbb{Z}_2^n$, computes $c = a \cdot s \mod{2}$ and returns the true $(a, c)$ with probability $1 - \eta$, or the corrupted $(a, 1 \oplus c)$ with probability $\eta$.

Bruteforce algorithm:

• query the LPN challenger for $m$ labelled samples $(x_1, l_1),...,(x_m, l_m) \in \mathbb{Z}_2^n \times \mathbb{Z}_2$
• for each potential secret $s_j \in \mathbb{Z}_2^n$, compute the empirical error rate $r_j = (1/m) (\sum_{i=1}^m (x_i \cdot s_j) + l_i \mod{2})$ (note each term of the sum is computed $\mod{2}$ but the sum itself is computed over the integers)
• output potential secret $s_t$ with empirical error rate $r_t$ closest to the noise rate $\eta$ (i.e. $t = arg\,min_t \lvert r_t - \eta \rvert$)

Intuitively, it seems this algorithm should succeed with probability significantly better than the trivial $\frac{1}{2^n}$ probability of guessing at random. But I'm not really sure how to quantify the success probability here. Any pointers to the literature or direct answers appreciated.

EDIT: I'm not 100% positive the last step of the bruteforce is actually the algorithm referenced in the literature, as the phrases I've seen used are "check which s is the best fit" and "find the one of least empirical error". So if I'm mistaken on the bruteforce algorithm description, let me know.

Answer 1

It's easiest if we simply pick the secret with the lowest score (which is also the maximum likelihood explanation). In this case, I can write down the cumbersome exact expression and then it is a question of which approximation you might like to use. Let's dispense with the $1/m$ factor in the score.

Exact expression

Note that for the causal solution $s_t$ the score $r_t$ is distributed $\mathrm{Bin}(m,\eta)$. We also note that the test is only likely to succeed when the score of the causal solution is bigger than the maximum of the non-causal scores. The non-causal scores should be distributed $\mathrm{Bin}(m,0.5)$ and the chance that one of these is less than or equal to some bound $r$ is given by $F(r;m,0.5)$ where $F$ is the binomial cumulative distribution function. Therefore the chance that all $2^n-1$ non-causal answers are greater than $r$ is given by $$(1-F(r;m,0.5))^{2^n-1}.$$

Summing over possible values of $r_t$ we see that the probability that the causal score is greater than all of the non-causal scores is given by $$\sum_{r=1}^m\left(1-F(r;m,0.5)\right)^{2^n-1}\left({m\atop r}\right)\eta^r(1-\eta)^{m-r}.$$

Approximations and bounds

$F$ is tiresome to calculate and so you may wish to approximate it with either Chernoff or Hoeffding bounds. It's also not the worst plan in the world to bound the above sum from below with the probability that $r_t$ is less than or equal to some fixed bound $r$ (given by $F(r;m,\eta)$) times the probability that the minimum of the non-causal scores is greater than the same fixed bound $r$: $$\left(1-F(r;m,0.5)\right)^{2^n-1}F(r;m,\eta).$$ A good choice of $r$ in this case might be $r\approx\eta m-2\sqrt{m\eta(1-\eta)}$ so that $F(r;m,\eta)\approx 0.95$ or simply $r\approx(1-\eta)m$ so that $F(r;m,\eta)\approx 0.5$.