廣瀬 健二朗
Currently, widely used public-key cryptosystems base their security on computationally hard problems in number theory, such as integer factorization and the discrete logarithm problem. However, with the development of quantum computers, it has been proven that these problems can be solved in polynomial time, necessitating the urgent implementation of post-quantum cryptography. The Ring-Learning with Errors (Ring-LWE) problem is a type of mathematical problem that forms the basis for lattice-based cryptography, which is a promising candidate for post-quantum cryptography. Algorithms for solving the Ring-LWE problem can be broadly classified into four categories: methods based on lattice basis reduction algorithms, algebraic approaches, combinatorial methods, and exhaustive search algorithms. Among these, this study focuses on the Blum-Kalai-Wasserman (BKW) algorithm, a combinatorial method that has not been extensively explored in existing research. The BKW algorithm consists of three steps, with the Reduction step being the bottleneck due to the large number of samples required to obtain those necessary for decryption. Consequently, research has focused on methods to process samples efficiently, even when limited in quantity. In particular, the Ring-BKW algorithm leverages the properties of rings to increase the number of available samples. In this study, we propose a new attack method by introducing a mechanism to dynamically determine the block size, which was previously fixed, during the Reduction step of the Ring-BKW algorithm. This approach aims to increase the number of samples available for decryption, thereby enhancing the attack's effectiveness.
