  In this paper it is shown that given a sufficient number of (noisy) random
binary linear equations, the Learning from Parity with Noise (LPN) problem can
be solved in essentially cube root time in the number of unknowns. The
techniques used to recover the solution are known from fast correlation attacks
on stream ciphers. As in fast correlation attacks, the performance of the
algorithm depends on the number of equations given. It is shown that if this
number exceeds a certain bound, and the bias of the noisy equations is
polynomial in number of unknowns, the running time of the algorithm is reduced
to almost cube root time compared to the brute force checking of all possible
solutions. The mentioned bound is explicitly given and it is further shown that
when this bound is exceeded, the complexity of the approach can even be further
reduced.
