On the Sample Complexity of solving LWE using BKW-Style Algorithms

Qian Guo; Erik Mårtensson; Paul Stankovski Wagner

doi:10.1109/ISIT45174.2021.9518190

On the Sample Complexity of solving LWE using BKW-Style Algorithms

Qian Guo, Erik Mårtensson, Paul Stankovski Wagner

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

Sammanfattning

The Learning with Errors (LWE) problem receives much attention in cryptography, mainly due to its fundamental significance in post-quantum cryptography. Among its solving algorithms, the Blum-Kalai-Wasserman (BKW) algorithm, originally proposed for solving the Learning Parity with Noise (LPN) problem, performs well, especially for certain parameter settings with cryptographic importance. The BKW algorithm consists of two phases, the reduction phase and the solving phase.

In this work, we study the performance of distinguishers used in the solving phase. We show that the Fast Fourier Transform (FFT) distinguisher from Eurocrypt'15 has the same sample complexity as the optimal distinguisher, when making the same number of hypotheses. We also show that it performs much better than theory predicts and introduce an improvement of it called the pruned FFT distinguisher. Finally, we indicate, via extensive experiments, that the sample dependency due to both LF2 and sample amplification is limited.

Originalspråk	engelska
Titel på värdpublikation	IEEE International Symposium on Information Theory (ISIT)
Förlag	IEEE - Institute of Electrical and Electronics Engineers Inc.
ISBN (elektroniskt)	978-1-5386-8209-8
ISBN (tryckt)	978-1-5386-8210-4
DOI	https://doi.org/10.1109/ISIT45174.2021.9518190
Status	Published - 2021
Evenemang	2021 IEEE International Symposium on Information Theory - Melbourne, Australien Varaktighet: 2021 juli 12 → 2021 juli 20 https://2021.ieee-isit.org/

Konferens

Konferens	2021 IEEE International Symposium on Information Theory
Förkortad titel	ISIT
Land/Territorium	Australien
Ort	Melbourne
Period	2021/07/12 → 2021/07/20
Internetadress	https://2021.ieee-isit.org/

Ämnesklassifikation (UKÄ)

Annan elektroteknik och elektronik

Tillgång till dokument

10.1109/ISIT45174.2021.9518190

https://arxiv.org/abs/2102.02126Licens: CC BY

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

Citera det här

@inproceedings{771b0359d65b40caa6de3b26d96b6972,

title = "On the Sample Complexity of solving LWE using BKW-Style Algorithms",

abstract = "The Learning with Errors (LWE) problem receives much attention in cryptography, mainly due to its fundamental significance in post-quantum cryptography. Among its solving algorithms, the Blum-Kalai-Wasserman (BKW) algorithm, originally proposed for solving the Learning Parity with Noise (LPN) problem, performs well, especially for certain parameter settings with cryptographic importance. The BKW algorithm consists of two phases, the reduction phase and the solving phase.In this work, we study the performance of distinguishers used in the solving phase. We show that the Fast Fourier Transform (FFT) distinguisher from Eurocrypt'15 has the same sample complexity as the optimal distinguisher, when making the same number of hypotheses. We also show that it performs much better than theory predicts and introduce an improvement of it called the pruned FFT distinguisher. Finally, we indicate, via extensive experiments, that the sample dependency due to both LF2 and sample amplification is limited.",

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

year = "2021",

doi = "10.1109/ISIT45174.2021.9518190",

language = "English",

isbn = "978-1-5386-8210-4",

booktitle = "IEEE International Symposium on Information Theory (ISIT)",

publisher = "IEEE - Institute of Electrical and Electronics Engineers Inc.",

address = "United States",

note = "2021 IEEE International Symposium on Information Theory, ISIT ; Conference date: 12-07-2021 Through 20-07-2021",

url = "https://2021.ieee-isit.org/",

}

Guo, Q , Mårtensson, E & Stankovski Wagner, P 2021, On the Sample Complexity of solving LWE using BKW-Style Algorithms. i IEEE International Symposium on Information Theory (ISIT). IEEE - Institute of Electrical and Electronics Engineers Inc., 2021 IEEE International Symposium on Information Theory, Melbourne, Australien, 2021/07/12. https://doi.org/10.1109/ISIT45174.2021.9518190

TY - GEN

T1 - On the Sample Complexity of solving LWE using BKW-Style Algorithms

AU - Guo, Qian

AU - Mårtensson, Erik

AU - Stankovski Wagner, Paul

PY - 2021

Y1 - 2021

N2 - The Learning with Errors (LWE) problem receives much attention in cryptography, mainly due to its fundamental significance in post-quantum cryptography. Among its solving algorithms, the Blum-Kalai-Wasserman (BKW) algorithm, originally proposed for solving the Learning Parity with Noise (LPN) problem, performs well, especially for certain parameter settings with cryptographic importance. The BKW algorithm consists of two phases, the reduction phase and the solving phase.In this work, we study the performance of distinguishers used in the solving phase. We show that the Fast Fourier Transform (FFT) distinguisher from Eurocrypt'15 has the same sample complexity as the optimal distinguisher, when making the same number of hypotheses. We also show that it performs much better than theory predicts and introduce an improvement of it called the pruned FFT distinguisher. Finally, we indicate, via extensive experiments, that the sample dependency due to both LF2 and sample amplification is limited.

AB - The Learning with Errors (LWE) problem receives much attention in cryptography, mainly due to its fundamental significance in post-quantum cryptography. Among its solving algorithms, the Blum-Kalai-Wasserman (BKW) algorithm, originally proposed for solving the Learning Parity with Noise (LPN) problem, performs well, especially for certain parameter settings with cryptographic importance. The BKW algorithm consists of two phases, the reduction phase and the solving phase.In this work, we study the performance of distinguishers used in the solving phase. We show that the Fast Fourier Transform (FFT) distinguisher from Eurocrypt'15 has the same sample complexity as the optimal distinguisher, when making the same number of hypotheses. We also show that it performs much better than theory predicts and introduce an improvement of it called the pruned FFT distinguisher. Finally, we indicate, via extensive experiments, that the sample dependency due to both LF2 and sample amplification is limited.

U2 - 10.1109/ISIT45174.2021.9518190

DO - 10.1109/ISIT45174.2021.9518190

M3 - Paper in conference proceeding

SN - 978-1-5386-8210-4

BT - IEEE International Symposium on Information Theory (ISIT)

PB - IEEE - Institute of Electrical and Electronics Engineers Inc.

T2 - 2021 IEEE International Symposium on Information Theory

Y2 - 12 July 2021 through 20 July 2021

ER -

On the Sample Complexity of solving LWE using BKW-Style Algorithms

Sammanfattning

Konferens

Ämnesklassifikation (UKÄ)

Tillgång till dokument

Fingeravtryck

Forskningsoutput

Some Notes on Post-Quantum Cryptanalysis

Citera det här