Revisiting an Extension of Kannan’s Embedding for Ring-LWE

Lattice-based cryptography has garnered significant attention in conjunction with the standardization of post-quantum cryptography by the National Institute of Standards and Technology. The Learning With Errors (LWE) problem is a mathematical issue ensuring the security of lattice-based cryptography. However, cryptographic schemes based on the LWE problem are noted for their inefficiency due to their large key sizes. The Ring-LWE problem was devised to reduce key size. Lattice attacks for Ring-LWE include finding shortest vectors of lattices using Kannan’s embedding method. Nakamura and Yasuda proposed an extension of Kannan’s embedding method that finds the shortest vector with higher probability. Nakamura et al. only considered to attack the Ring-LWE over \(2^k\) -th cyclotomic fields, but it is important to anlyze the security of Ring-LWE over various number fields. In this paper, we propose to apply the extension of Kannan’s embedding method for Ring-LWE over various number fields and demonstrate its effectiveness through a theoretical analysis and experiments.