Scholarlink

<p>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.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

An improved BKW algorithm on the learning with rounding problem

  • 期刊论文

  • 出版模式：

    开放获取

  • 发表日期：

    2025年6月13日

查看全文
  • Yu Wei,
  • Lei Bi,
  • Kunpeng Wang,
  • Xianhui Lu

摘要

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.