Non-asymptotic complexity estimates for attacks on Learning with Errors (LWE) problems are critically important. The Meet-LWE algorithm, proposed by May at CRYPTO 2021, presents an advanced attack method with non-asymptotic complexity estimates [1]. However, detailed discussions of its parameter selection is in lack. In this paper, we first investigate Meet-LWE, analyze specific parameter selection criteria, including the determination of search tree depths and the value of \(\epsilon \) , a parameter employed to expand the representation space. Our results show that in practical attacks, \(\epsilon \) is often constrained to remain within a limited range, preventing Meet-LWE from achieving its expected performance under certain parameters. Secondly, we follow the line of Wenger et al.’s work [2], characterize the real-world memory consumption of solving LWE with sparse secrets building upon May’s method. We have implemented a real-world attack against weakened Kyber, and achieved optimizations in both time and memory consumption. Compared to the hybrid dual lattice attack proposed in [2], we optimize memory consumption by approximately 15 times.

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

Further Research on Meet-LWE and Its Application to Weakened Kyber

  • Shengye Song,
  • Zhongxiao Wang,
  • Hong Xu,
  • Qunxiong Zheng,
  • Xiaoxin Zhao

摘要

Non-asymptotic complexity estimates for attacks on Learning with Errors (LWE) problems are critically important. The Meet-LWE algorithm, proposed by May at CRYPTO 2021, presents an advanced attack method with non-asymptotic complexity estimates [1]. However, detailed discussions of its parameter selection is in lack. In this paper, we first investigate Meet-LWE, analyze specific parameter selection criteria, including the determination of search tree depths and the value of \(\epsilon \) , a parameter employed to expand the representation space. Our results show that in practical attacks, \(\epsilon \) is often constrained to remain within a limited range, preventing Meet-LWE from achieving its expected performance under certain parameters. Secondly, we follow the line of Wenger et al.’s work [2], characterize the real-world memory consumption of solving LWE with sparse secrets building upon May’s method. We have implemented a real-world attack against weakened Kyber, and achieved optimizations in both time and memory consumption. Compared to the hybrid dual lattice attack proposed in [2], we optimize memory consumption by approximately 15 times.