Solving LPN Using Covering Codes

Research output: Contribution to journalArticle

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,18) 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.

Details

Authors
Organisations
External organisations
  • University of Bergen
Research areas and keywords

Subject classification (UKÄ) – MANDATORY

  • Computer Science

Keywords

  • BKW, Covering codes, HB, Lapin, LPN, LPN-C
Original languageEnglish
Pages (from-to)1-33
Number of pages33
JournalJournal of Cryptology
Volume33
Issue number1
Early online date2019 Oct 15
Publication statusPublished - 2020 Jan
Publication categoryResearch
Peer-reviewedYes