A New Scaling Approach to Bai-Galbraith's Embedding for Solving LWE over Rings

The learning with errors (LWE) problem is a computational problem of solving an approximate linear system over the ring [Formula: see text] of integers modulo an odd prime [Formula: see text]. The security of many modern lattice-based cryptosystems relies on the hardness of solving variants of the LWE problem over rings or modules. In this paper, we present a new approach to rescale the Bai-Galbraith embedding lattice for solving the LWE problem over [Formula: see text], where the secret has small coefficients in [Formula: see text]. Specifically, we construct a projected lattice [Formula: see text] from an integer lattice by applying rotations to the coefficient vectors of elements in [Formula: see text]. For coefficient vectors [Formula: see text] of the secret and the error in an LWE instance, the projected lattice [Formula: see text] includes [Formula: see text], strictly shorter than the shortest vector [Formula: see text] embedded in the Bai-Galbraith lattice [Formula: see text]. The ranks of [Formula: see text] and [Formula: see text] are the same, but the volume of [Formula: see text] is smaller by a factor of [Formula: see text]. This is equivalent to the scaled Bai-Galbraith lattice with scaling factor [Formula: see text], in terms of the ratio between the first successive minimum and the [Formula: see text]-th root of the volume of a lattice [Formula: see text] of rank [Formula: see text]. Our embedding is particularly effective when [Formula: see text]. Moreover, it enables us to recover [Formula: see text] by working directly with the integer lattice underlying [Formula: see text].