Paper 2016/437

Observations on the LPN Solving Algorithm from Eurocrypt'16

Sonia Bogos and Serge Vaudenay

Abstract

In this note we re-evaluate the Eurocrypt'16 paper by Zhang et al. in the area of LPN solving algorithms. We present the history of LPN solving algorithms and give the general description of the algorithm. While this new algorithm claims to improve all the previous results, we have discovered issues in its analysis. We review inconsistencies in complexity estimates and a misconception of some new reduction algorithm. What we show is that the results of Eurocrypt'16 do not provide better performance compared with the results from Asiacrypt'14.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Contact author(s)
soniamihaela bogos @ epfl ch
History
2016-05-04: received
Short URL
https://ia.cr/2016/437
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/437,
      author = {Sonia Bogos and Serge Vaudenay},
      title = {Observations on the LPN Solving Algorithm from Eurocrypt'16},
      howpublished = {Cryptology ePrint Archive, Paper 2016/437},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/437}},
      url = {https://eprint.iacr.org/2016/437}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.