Solving LPN Using Covering Codes

被引：15

作者：

Guo, Qian ^{[1
,2
]}

Johansson, Thomas ^{[1
]}

Londahl, Carl ^{[1
]}

机构：

[1] Lund Univ, Dept Elect & Informat Technol, Lund, Sweden

[2] Univ Bergen, Selmer Ctr, Dept Informat, Bergen, Norway

来源：

JOURNAL OF CRYPTOLOGY | 2020年 / 33卷 / 01期

基金：

瑞典研究理事会;

关键词：

LPN; BKW; Covering codes; LPN-C; HB; Lapin; SECURITY; HB;

D O I：

10.1007/s00145-019-09338-8

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

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 LPN instance with complexity less than operations in expectation, indicating that cryptographic schemes like HB variants and LPN-C should increase their parameter size for 80-bit security.

引用

页码：1 / 33

页数：33

共 32 条

[1] Albrecht MR, 2014, LECT NOTES COMPUT SC, V8383, P429, DOI 10.1007/978-3-642-54631-0_25
[2] More on average case vs approximation complexity
Alekhnovich, M
[J]. 44TH ANNUAL IEEE SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, PROCEEDINGS, 2003, : 298 - 307
[3] [Anonymous], 2012, ELEMENTS INFORM THEO
[4] [Anonymous], 2012699 CRYPT EPRINT
[5] [Anonymous], 2011377 CRYPT EPRINT
[6] Bernstein D, 2013, NEVER TRUST BUNNY RA, P137
[7] Noise-tolerant learning, the parity problem, and the statistical query model
Blum, A
Kalai, A
Wasserman, H
[J]. JOURNAL OF THE ACM, 2003, 50 (04) : 506 - 519
[8] Bogos S., 2015, TECH REP
[9] Optimization of LPN Solving Algorithms
Bogos, Sonia
Vaudenay, Serge
[J]. ADVANCES IN CRYPTOLOGY - ASIACRYPT 2016, PT I, 2016, 10031 : 703 - 728
[10] Cohen G., 1997, Covering Codes

← 1 2 3 4 →