Making the BKW Algorithm Practical for LWE

Forskningsoutput: Kapitel i bok/rapport/Conference proceedingKonferenspaper i proceedingForskningPeer review

1 Citering (SciVal)

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åkengelska
Titel på gästpublikationProgress in Cryptology – INDOCRYPT 2020
Undertitel på gästpublikation21st International Conference on Cryptology in India Bangalore, India, December 13–16, 2020 Proceedings
FörlagSpringer
Sidor417-439
Antal sidor23
ISBN (elektroniskt)978-3-030-65277-7
ISBN (tryckt)978-3-030-65276-0
DOI
StatusPublished - 2020 dec
EvenemangInternational Conference on Cryptology in India - INDOCRYPT 2020 - Bangalore, Indien
Varaktighet: 2020 dec 132020 dec 16
Konferensnummer: 21
https://indocrypt2020.iiitb.ac.in/

Publikationsserier

NamnLecture Notes in Computer Science
FörlagSpringer
Volym12578
ISSN (tryckt)0302-9743
ISSN (elektroniskt)1611-3349

Konferens

KonferensInternational Conference on Cryptology in India - INDOCRYPT 2020
Förkortad titelINDOCRYPT 2020
Land/TerritoriumIndien
OrtBangalore
Period2020/12/132020/12/16
Internetadress

Ämnesklassifikation (UKÄ)

  • Annan elektroteknik och elektronik

Fingeravtryck

Utforska forskningsämnen för ”Making the BKW Algorithm Practical for LWE”. Tillsammans bildar de ett unikt fingeravtryck.

Citera det här