Practically Solving LPN in High Noise Regimes Faster Using Neural Networks. (arXiv:2303.07987v1 [cs.LG])

We conduct a systematic study of solving the learning parity with noise
problem (LPN) using neural networks. Our main contribution is designing
families of two-layer neural networks that practically outperform classical
algorithms in high-noise, low-dimension regimes. We consider three settings
where the numbers of LPN samples are abundant, very limited, and in between. In
each setting we provide neural network models that solve LPN as fast as
possible. For some settings we are also able to provide theories that explain
the rationale of the design of our models. Comparing with the previous
experiments of Esser, Kubler, and May (CRYPTO 2017), for dimension $n = 26$,
noise rate $tau = 0.498$, the ”Guess-then-Gaussian-elimination” algorithm
takes 3.12 days on 64 CPU cores, whereas our neural network algorithm takes 66
minutes on 8 GPUs. Our algorithm can also be plugged into the hybrid algorithms
for solving middle or large dimension LPN instances.