Discussion forum for Cryptology ePrint Archive
reports posted in 2012
. Please put the report number in the subject.
Posted by: djb
Date: 15 December 2012 00:06
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