Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

Modeling and simulating the sample complexity of solving LWE using BKW-style algorithms

Guo, Qian LU ; Mårtensson, Erik LU orcid and Stankovski Wagner, Paul LU (2023) In Cryptography and Communications 15(2). p.331-350
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... (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 via simulation that it performs much better than previous theory predicts and develop a sample complexity model that matches the simulations better. We also introduce an improved, pruned version of the 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
Contribution to journal
publication status
published
subject
in
Cryptography and Communications
volume
15
issue
2
pages
20 pages
publisher
Springer
external identifiers
  • scopus:85135810051
ISSN
1936-2455
DOI
10.1007/s12095-022-00597-0
project
Lightweight Cryptography for Autonomous Vehicles
language
English
LU publication?
yes
id
f3868cf4-18fd-4e60-96ad-bcf6eeaf2a73
date added to LUP
2022-08-30 12:00:01
date last changed
2024-02-18 07:40:35
@article{f3868cf4-18fd-4e60-96ad-bcf6eeaf2a73,
  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 via simulation that it performs much better than previous theory predicts and develop a sample complexity model that matches the simulations better. We also introduce an improved, pruned version of the 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}},
  issn         = {{1936-2455}},
  language     = {{eng}},
  number       = {{2}},
  pages        = {{331--350}},
  publisher    = {{Springer}},
  series       = {{Cryptography and Communications}},
  title        = {{Modeling and simulating the sample complexity of solving LWE using BKW-style algorithms}},
  url          = {{http://dx.doi.org/10.1007/s12095-022-00597-0}},
  doi          = {{10.1007/s12095-022-00597-0}},
  volume       = {{15}},
  year         = {{2023}},
}