An Attack on Ring-LWE Using a Dynamically Adjustable Block Size BKW Algorithm

The Ring-LWE problem is a fundamental component of lattice-based cryptography, and evaluating its security is a crucial challenge. The algorithms for solving the Ring-LWE problem can be classified into four categories: lattice basis reduction algorithms, algebraic methods, combinatorial methods and exhaustive search algorithms. However, the combinatorial approach, the Ring-BKW algorithm, remains insufficiently analyzed. The Ring-BKW algorithm primarily consists of two steps, with the Reduction step being the bottleneck because many samples are required for decryption. In existing implementations of the Ring-BKW Reduction step, the block size remains fixed, preventing it from adapting to the sample reduction process and efficiently inducing collisions. In this study, we introduce a method that allows the block size in the Reduction step of the Ring-BKW algorithm to be variable. We propose two approaches: a static decision method, where users manually specify the block size for each reduction step, and a dynamic decision method, where the algorithm autonomously adjusts the block size. The proposed method increases the number of collisions compared to existing methods, resulting in approximately 55-fold and 425-fold more reduced samples for static and dynamic block size selection, respectively, in the Ring-LWE setting with q=17, n=2^4.