Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

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

Guo, Qian LU ; Mårtensson, Erik LU orcid and Stankovski Wagner, Paul LU (2021) 2021 IEEE International Symposium on Information Theory
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... (More)
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. (Less)
Please use this url to cite or link to this publication:
author
; and
organization
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
subject
host publication
IEEE International Symposium on Information Theory (ISIT)
publisher
IEEE - Institute of Electrical and Electronics Engineers Inc.
conference name
2021 IEEE International Symposium on Information Theory
conference location
Melbourne, Australia
conference dates
2021-07-12 - 2021-07-20
external identifiers
  • scopus:85115106421
ISBN
978-1-5386-8210-4
978-1-5386-8209-8
DOI
10.1109/ISIT45174.2021.9518190
language
English
LU publication?
yes
id
771b0359-d65b-40ca-a6de-3b26d96b6972
alternative location
https://arxiv.org/abs/2102.02126
date added to LUP
2021-06-01 10:28:26
date last changed
2024-04-06 04:18:30
@inproceedings{771b0359-d65b-40ca-a6de-3b26d96b6972,
  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.<br/><br/>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       = {{Guo, Qian and Mårtensson, Erik and Stankovski Wagner, Paul}},
  booktitle    = {{IEEE International Symposium on Information Theory (ISIT)}},
  isbn         = {{978-1-5386-8210-4}},
  language     = {{eng}},
  publisher    = {{IEEE - Institute of Electrical and Electronics Engineers Inc.}},
  title        = {{On the Sample Complexity of solving LWE using BKW-Style Algorithms}},
  url          = {{http://dx.doi.org/10.1109/ISIT45174.2021.9518190}},
  doi          = {{10.1109/ISIT45174.2021.9518190}},
  year         = {{2021}},
}