Paper 2018/356

In Praise of Twisted Canonical Embedding

Jheyne N. Ortiz and Robson R. de Araujo and Ricardo Dahab and Diego F. Aranha and Sueli I. R. Costa

Abstract

In ideal-lattice cryptography, lattices are generated by defining a bijective map between an ideal of a ring of integers and a subset of $\mathbb{C}^n$. This map can be taken to be the coefficient embedding and, along with the Ring-LWE problem, the canonical embedding. However, some lattices cannot be generated using the canonical embedding in a straightforward manner. In this paper, we introduce a new class of problems called $\alpha$-Ring-LWE, which combines Ring-LWE with the twisted canonical embedding. In this context, $\alpha$ stands to be a number field element that distorts the canonical embedding coordinates. We prove the hardness of $\alpha$-Ring-LWE by providing a reduction between the Ring-LWE problem to $\alpha$-Ring-LWE for both search and decision variants. As a result, we obtain a hardness result based on a hard problem over ideal lattices. The addition of a torsion factor enables the construction of a broader class of lattices as rotated lattices. An example is the construction of the integer lattice $\mathbb{Z}^n$ by embedding the ring of integers of the totally real subfield of a cyclotomic number field $\mathbb{Q}(\zeta_p)$ with $p$ being a prime number [BFOV04].