Modeling and Simulating the Sample Complexity of solving LWE using BKW-Style Algorithms

ePrint Report: Modeling and Simulating the Sample Complexity of solving LWE using BKW-Style Algorithms

Qian Guo, Erik Mårtensson, Paul Stankovski Wagner

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 …

algorithms complexity eprint report modeling