Observations on the LPN Solving Algorithm from Eurocrypt'16

Sonia Bogos; Serge Vaudenay

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: 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},
      url = {https://eprint.iacr.org/2016/437}
}