Solving LPN Using Covering Codes

Summary, in English

We present a new algorithm for solving the LPN problem. The algorithm has a similar form as some previous methods, but includes a new key step that makes use of approximations of random words to a nearest codeword in a linear code. It outperforms previous methods for many parameter choices. In particular, we can now solve instances suggested for 80-bit security in cryptographic schemes like HB variants, LPN-C and Lapin, in less than 2(80) operations.

• Författare: Qian Guo; Thomas Johansson; Carl Löndahl
• Redaktör: Tetsu Iwata; Palash Sarkar
• Avdelning/ar: Institutionen för elektro- och informationsteknik; ELLIIT: the Linköping-Lund initiative on IT and mobile communication
• Publiceringsår: 2014
• Språk: Engelska
• Sidor: 1-20
• Publikation/Tidskrift/Serie: Advances in Cryptology - Asiacrypt 2014
• Volym: 8873
• Länkar: http://dx.doi.org/10.1007/978-3-662-45611-8_1
• Dokumenttyp: Konferensbidrag
• Förlag: Springer
• Ämne: Computer Science
• Conference name: 20th Annual International Conference on the Theory and Application of Cryptology and Information Security (Asiacrypt)
• Conference date: 2014-12-07 - 2014-12-11
• Conference place: Kaohsiung, Taiwan
• Status: Published
• ISBN/ISSN/Övrigt: ISSN: 0302-9743; ISSN: 1611-3349; ISBN: 978-3-662-45610-1