池上 輝
In recent years, advances in quantum computing have raised serious concerns about the security of existing public-key cryptosystems. Consequently, evaluating the security of the Ring-Learning with Errors (Ring-LWE) problem, which underlies lattice-based cryptography, has become an important research topic. The Ring-LWE problem consists of two variants: the decision problem of distinguishing Ring-LWE samples from uniformly random samples, and the search problem of recovering the secret key. The Blum-Kalai-Wasserman (BKW) algorithm, a method for solving the LWE search problem, consists of three steps: a sample-reduction step to reduce the sample dimension, a hypothesis-testing step to estimate secret key components from the dimension-reduced samples, and a back-substitution step to determine the remaining components. In BKW algorithm-based secret key recovery, the final recovery performance strongly depends on the number of available samples and the magnitude of accumulated errors introduced during the sample-reduction phase. For Ring-LWE, the Ring-BKW algorithm extends BKW by exploiting the algebraic structure of the underlying ring. Previous work by Hirose et al. introduced dynamic block size selection to increase the number of usable samples; however, full secret key recovery and success probability analysis under error growth have not yet been achieved. Furthermore, existing hypothesis-testing approaches for Ring-LWE largely reuse techniques developed for standard LWE, without fully exploiting the algebraic structure of the polynomial ring. In this work, we perform full secret key recovery using samples generated by Ring-BKW with dynamic block size selection. Specifically, we propose a multidimensional FFT-based hypothesis-testing method that simultaneously exploits multiple coefficients while taking the ring structure into account. Through empirical evaluation, we identify parameter settings suitable for successful recovery and analyze the impact of block size selection on recovery performance.
