**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].

**Category / Keywords: **foundations / Lattice techniques, number theory, canonical embedding.

**Date: **received 16 Apr 2018

**Contact author: **jheyne ortiz at ic unicamp br

**Available format(s): **PDF | BibTeX Citation

**Version: **20180418:203010 (All versions of this report)

**Short URL: **ia.cr/2018/356

[ Cryptology ePrint archive ]