2012 Reports :  Cryptology ePrint Archive Forum
Discussion forum for Cryptology ePrint Archive reports posted in 2012. Please put the report number in the subject. 
Goto Thread: PreviousNext
Goto: Forum ListMessage ListNew TopicSearchLog In
2012/699: dangerous
Posted by: djb (IP Logged)
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

Re: 2012/699: dangerous
Posted by: ivandamgard (IP Logged)
Date: 18 December 2012 12:14

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

Please log in for posting a message. Only registered users may post in this forum.