Making the BKW Algorithm Practical for LWE

Alessandro Budroni; Qian Guo; Thomas Johansson; Erik Mårtensson; Paul Stankovski Wagner

doi:10.1007/978-3-030-65277-7_19

Making the BKW Algorithm Practical for LWE

Alessandro Budroni, Qian Guo, Thomas Johansson, Erik Mårtensson, Paul Stankovski Wagner

University of Bergen

Forskningsoutput: Kapitel i bok/rapport/Conference proceeding › Konferenspaper i proceeding › Peer review

Sammanfattning

The Learning with Errors (LWE) problem is one of the main mathematical foundations of post-quantum cryptography. One of the main groups of algorithms for solving LWE is the Blum-Kalai-Wasserman (BKW) algorithm. This paper presents new improvements for BKW-style algorithms for solving LWE instances. We target minimum concrete complexity and we introduce a new reduction step where we partially reduce the last position in an iteration and finish the reduction in the next iteration, allowing non-integer step sizes. We also introduce a new procedure in the secret recovery by mapping the problem to binary problems and applying the FastWalsh Hadamard Transform. The complexity of the resulting algorithm compares favourably to all other previous approaches, including lattice sieving. We additionally show the steps of implementing the approach for large LWE problem instances. The core idea here is to overcome RAM limitations by using large file-based memory.

Originalspråk	engelska
Titel på värdpublikation	Progress in Cryptology – INDOCRYPT 2020
Undertitel på värdpublikation	21st International Conference on Cryptology in India Bangalore, India, December 13–16, 2020 Proceedings
Förlag	Springer
Sidor	417-439
Antal sidor	23
ISBN (elektroniskt)	978-3-030-65277-7
ISBN (tryckt)	978-3-030-65276-0
DOI	https://doi.org/10.1007/978-3-030-65277-7_19
Status	Published - 2020 dec.
Evenemang	International Conference on Cryptology in India - INDOCRYPT 2020 - Bangalore, Indien Varaktighet: 2020 dec. 13 → 2020 dec. 16 Konferensnummer: 21 https://indocrypt2020.iiitb.ac.in/

Publikationsserier

Namn	Lecture Notes in Computer Science
Förlag	Springer
Volym	12578
ISSN (tryckt)	0302-9743
ISSN (elektroniskt)	1611-3349

Konferens

Konferens	International Conference on Cryptology in India - INDOCRYPT 2020
Förkortad titel	INDOCRYPT 2020
Land/Territorium	Indien
Ort	Bangalore
Period	2020/12/13 → 2020/12/16
Internetadress	https://indocrypt2020.iiitb.ac.in/

Ämnesklassifikation (UKÄ)

Annan elektroteknik och elektronik

Tillgång till dokument

10.1007/978-3-030-65277-7_19

1 Doktorsavhandling (sammanläggning)

Some Notes on Post-Quantum Cryptanalysis
Mårtensson, E., 2020, Lund: Department of Electroscience, Lund University. 290 s.
Forskningsoutput: Avhandling › Doktorsavhandling (sammanläggning)

Öppen tillgång
Fil

1 Avslutade

Lightweight Cryptography for Autonomous Vehicles
Johansson, T. (Forskare) & Guo, Q. (Forskare)
2020/08/01 → 2023/12/31
Projekt: Forskning

Citera det här

Budroni, A., Guo, Q., Johansson, T., Mårtensson, E., & Stankovski Wagner, P. (2020). Making the BKW Algorithm Practical for LWE. I Progress in Cryptology – INDOCRYPT 2020: 21st International Conference on Cryptology in India Bangalore, India, December 13–16, 2020 Proceedings (s. 417-439). (Lecture Notes in Computer Science; Vol. 12578). Springer. https://doi.org/10.1007/978-3-030-65277-7_19

@inproceedings{137c8112cc8f47f2aa6a74792497b266,

title = "Making the BKW Algorithm Practical for LWE",

abstract = "The Learning with Errors (LWE) problem is one of the main mathematical foundations of post-quantum cryptography. One of the main groups of algorithms for solving LWE is the Blum-Kalai-Wasserman (BKW) algorithm. This paper presents new improvements for BKW-style algorithms for solving LWE instances. We target minimum concrete complexity and we introduce a new reduction step where we partially reduce the last position in an iteration and finish the reduction in the next iteration, allowing non-integer step sizes. We also introduce a new procedure in the secret recovery by mapping the problem to binary problems and applying the FastWalsh Hadamard Transform. The complexity of the resulting algorithm compares favourably to all other previous approaches, including lattice sieving. We additionally show the steps of implementing the approach for large LWE problem instances. The core idea here is to overcome RAM limitations by using large file-based memory.",

keywords = "BKW, LWE, Lattice-Based Cryptography, FWHT, Post- Quantum Cryptography",

author = "Alessandro Budroni and Qian Guo and Thomas Johansson and Erik M{\aa}rtensson and {Stankovski Wagner}, Paul",

year = "2020",

month = dec,

doi = "10.1007/978-3-030-65277-7_19",

language = "English",

isbn = "978-3-030-65276-0",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "417--439",

booktitle = "Progress in Cryptology – INDOCRYPT 2020",

address = "Germany",

note = "International Conference on Cryptology in India - INDOCRYPT 2020, INDOCRYPT 2020 ; Conference date: 13-12-2020 Through 16-12-2020",

url = "https://indocrypt2020.iiitb.ac.in/",

}

Budroni, A, Guo, Q , Johansson, T , Mårtensson, E & Stankovski Wagner, P 2020, Making the BKW Algorithm Practical for LWE. i Progress in Cryptology – INDOCRYPT 2020: 21st International Conference on Cryptology in India Bangalore, India, December 13–16, 2020 Proceedings. Lecture Notes in Computer Science, vol. 12578, Springer, s. 417-439, International Conference on Cryptology in India - INDOCRYPT 2020, Bangalore, Indien, 2020/12/13. https://doi.org/10.1007/978-3-030-65277-7_19

Making the BKW Algorithm Practical for LWE. / Budroni, Alessandro; Guo, Qian ; Johansson, Thomas et al.
Progress in Cryptology – INDOCRYPT 2020: 21st International Conference on Cryptology in India Bangalore, India, December 13–16, 2020 Proceedings. Springer, 2020. s. 417-439 (Lecture Notes in Computer Science; Vol. 12578).

Forskningsoutput: Kapitel i bok/rapport/Conference proceeding › Konferenspaper i proceeding › Peer review

TY - GEN

T1 - Making the BKW Algorithm Practical for LWE

AU - Budroni, Alessandro

AU - Guo, Qian

AU - Johansson, Thomas

AU - Mårtensson, Erik

AU - Stankovski Wagner, Paul

N1 - Conference code: 21

PY - 2020/12

Y1 - 2020/12

N2 - The Learning with Errors (LWE) problem is one of the main mathematical foundations of post-quantum cryptography. One of the main groups of algorithms for solving LWE is the Blum-Kalai-Wasserman (BKW) algorithm. This paper presents new improvements for BKW-style algorithms for solving LWE instances. We target minimum concrete complexity and we introduce a new reduction step where we partially reduce the last position in an iteration and finish the reduction in the next iteration, allowing non-integer step sizes. We also introduce a new procedure in the secret recovery by mapping the problem to binary problems and applying the FastWalsh Hadamard Transform. The complexity of the resulting algorithm compares favourably to all other previous approaches, including lattice sieving. We additionally show the steps of implementing the approach for large LWE problem instances. The core idea here is to overcome RAM limitations by using large file-based memory.

AB - The Learning with Errors (LWE) problem is one of the main mathematical foundations of post-quantum cryptography. One of the main groups of algorithms for solving LWE is the Blum-Kalai-Wasserman (BKW) algorithm. This paper presents new improvements for BKW-style algorithms for solving LWE instances. We target minimum concrete complexity and we introduce a new reduction step where we partially reduce the last position in an iteration and finish the reduction in the next iteration, allowing non-integer step sizes. We also introduce a new procedure in the secret recovery by mapping the problem to binary problems and applying the FastWalsh Hadamard Transform. The complexity of the resulting algorithm compares favourably to all other previous approaches, including lattice sieving. We additionally show the steps of implementing the approach for large LWE problem instances. The core idea here is to overcome RAM limitations by using large file-based memory.

KW - BKW

KW - LWE

KW - Lattice-Based Cryptography

KW - FWHT

KW - Post- Quantum Cryptography

U2 - 10.1007/978-3-030-65277-7_19

DO - 10.1007/978-3-030-65277-7_19

M3 - Paper in conference proceeding

SN - 978-3-030-65276-0

T3 - Lecture Notes in Computer Science

SP - 417

EP - 439

BT - Progress in Cryptology – INDOCRYPT 2020

PB - Springer

T2 - International Conference on Cryptology in India - INDOCRYPT 2020

Y2 - 13 December 2020 through 16 December 2020

ER -

Making the BKW Algorithm Practical for LWE

Sammanfattning

Publikationsserier

Konferens

Ämnesklassifikation (UKÄ)

Tillgång till dokument

Fingeravtryck

Forskningsoutput

Some Notes on Post-Quantum Cryptanalysis

Projekt

Lightweight Cryptography for Autonomous Vehicles

Citera det här