Shortest Vectors in Lattices of Bai-Galbraith's Embedding Attack on the LWR Problem.

The Learning With Rounding (LWR) problem has attracted increasing attention as a foundation for post-quantum cryptosystems. It is known to be a variant of the Learning With Errors (LWE) problem, and so far the computational hardness of the LWE problem has been analyzed through various types of attacks using the structure of lattices. Bai-Galbraith’s embedding attack is one of the most effective attacks against the LWE problem. Their embedding attack is also applicable to the LWR problem - through the transformation from the LWR problem to the LWE problem - and its effect on the LWR problem has been directly analyzed with the structure of a certain lattice (referred to as a BG-lattice in this paper) constructed in the LWE problem. However, the structure of a BG-lattice in the LWR problem is not the same as that in the LWE problem with this transformation; thus, it requires more concrete investigation for the security analysis of LWR-based cryptosystems. In this paper, we study the structure of a BG-lattice constructed in the LWR problem through the transformation from the LWR problem to the LWE problem. Specifically, we explicitly find a certain vector in the lattice that can be the shortest, and formulate the condition where such a vector is surely the shortest one. The existence of such a shortest vector causes a situation that the second shortest vector linearly independent of the shortest vector in a BG-lattice is different from the expected. We also study the probability that this situation occurs, and obtain a relation between the probability and parameters of the LWR problem. Our experimental results confirm the existence of this shortest vector and the aforementioned relation. Note that the focus of this paper is a theoretical analysis, and applying it to the security analysis of LWR-based cryptosystems will be conducted in future work.