.png){kind=icon}
.png){kind=icon}
Return
An improved BKW algorithm on the learning with rounding problem
.png){kind=icon}
OA
AI
DOI：10.1186/s42400-024-00339-0.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
The Blum-Kalai-Wasserman (BKW) algorithm is a significant combinatorial algorithm used to tackle the Learning with Errors (LWE) and Learning with Rounding (LWR) problems. In 2015, Duc et al. (in: Oswald and Fischlin (eds) EUROCRYPT 2015, Springer, Berlin, 2015) proposed the first BKW algorithm applied directly to LWR, which consists of the reduction phase and the solving phase. In this paper, we propose an improved LWR-solving BKW algorithm. For the reduction phase, we design a novel coding method with relaxed collision conditions and introduce a post-processing stage and for the solving phase, we switch to a more efficient Fast Fourier Transform (FFT) distinguisher with pruning. Compared to previous LWR-solving BKW algorithms, our new BKW algorithm achieves a time complexity improvement of 4.0–48.5 bits for the instances considered. Additionally, by incorporating a novel heuristic method in the reduction phase, our algorithm further improves the sample complexity by 3.7–48.7 bits.
Keywords:
Post-quantum cryptography
Learning with rounding problem
Learning with errors problem
The BKW algorithm
Journal
C
IF:
3.7
Papers:
574
Citations:
1.0K