2012/699 claims that its LPN(768,0.015)-based cryptosystem provides 2^80 security.

However, the Kirchner attack in 2011/377 shows that small error rates create a huge loss of LPN security. 2012/699 claims that it's additionally protected by a limit on the number of LPN outputs; this does stop the attack stated in 2011/377, but the improved attack in 2012/355 ("Never trust a bunny") shows, among other things, that such limits provide very little protection. (See the last paragraph of 2012/355.)

An initial quantitative analysis suggests that the LPN(768,0.015) problem in the 2012/699 cryptosystem not only fails to provide 2^80 security, but in fact is easily breakable on a small computer cluster. Presumably this also breaks the cryptosystem per se, not just the underlying security assumption. Serious security would require much larger, and slower, parameters.

---D. J. Bernstein

The paper has updated. It now mentions the new work that Dan pointed out and warns the reader that taking this work into account would mean that the parameters would have to be changed. We plan to give some concrete results in the next version of the paper.

- Ivan Damgård