Paper 2023/372

Practically Solving LPN in High Noise Regimes Faster Using Neural Networks

Haozhe Jiang, Tsinghua University
Kaiyue Wen, Tsinghua University
Yilei Chen, Tsinghua University
Abstract

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, Kübler, 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.

Metadata
Available format(s)
PDF
Category
Attacks and cryptanalysis
Publication info
Preprint.
Keywords
LPNMachine Learning
Contact author(s)
jianghz20 @ mails tsinghua edu cn
wenky20 @ mails tsinghua edu cn
chenyilei @ mail tsinghua edu cn
History
2023-03-16: approved
2023-03-15: received
See all versions
Short URL
https://ia.cr/2023/372
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2023/372,
      author = {Haozhe Jiang and Kaiyue Wen and Yilei Chen},
      title = {Practically Solving LPN in High Noise Regimes Faster Using Neural Networks},
      howpublished = {Cryptology ePrint Archive, Paper 2023/372},
      year = {2023},
      note = {\url{https://eprint.iacr.org/2023/372}},
      url = {https://eprint.iacr.org/2023/372}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.