Observations on the LPN Solving Algorithm from Eurocrypt'16

In this note we re-evaluate the Eurocrypt’16 paper by Zhang et al. [9] in the area of LPN solving algorithms. We present the history of LPN solving algorithms and give the general description of the algorithm from [9]. 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 [9] do not provide better performance compared with the results from Asiacrypt’14 [5].


Year:
2016
Laboratories:




 Record created 2016-10-18, last modified 2018-03-17

n/a:
Download fulltext
PDF

Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)