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].