dc.contributor.author | Guo, Qian | |
dc.contributor.author | Johansson, Thomas | |
dc.contributor.author | Löndahl, Carl | |
dc.date.accessioned | 2020-06-15T16:07:13Z | |
dc.date.available | 2020-06-15T16:07:13Z | |
dc.date.issued | 2019-10-15 | |
dc.Published | Guo Q, Johansson T, Löndahl. Solving LPN Using Covering Codes. Journal of Cryptology. 2020;33:1-33 | eng |
dc.identifier.issn | 1432-1378 | en_US |
dc.identifier.issn | 0933-2790 | en_US |
dc.identifier.uri | https://hdl.handle.net/1956/22601 | |
dc.description.abstract | 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 the (512,1/8) LPN instance with complexity less than 2^80 operations in expectation, indicating that cryptographic schemes like HB variants and LPN-C should increase their parameter size for 80-bit security. | en_US |
dc.language.iso | eng | eng |
dc.publisher | Springer | en_US |
dc.rights | Attribution CC BY | eng |
dc.rights.uri | http://creativecommons.org/licenses/by/4.0/ | eng |
dc.subject | LPN | eng |
dc.subject | BKW | eng |
dc.subject | Covering codes | eng |
dc.subject | LPN-C | eng |
dc.subject | HB | eng |
dc.subject | Lapin | eng |
dc.title | Solving LPN Using Covering Codes | en_US |
dc.type | Peer reviewed | |
dc.type | Journal article | |
dc.date.updated | 2020-02-12T06:39:25Z | |
dc.description.version | publishedVersion | en_US |
dc.rights.holder | Copyright 2019 The Author(s) | en_US |
dc.identifier.doi | https://doi.org/10.1007/s00145-019-09338-8 | |
dc.identifier.cristin | 1771365 | |
dc.source.journal | Journal of Cryptology | |
dc.relation.project | Norges forskningsråd: 247742 | |