### In Praise of Twisted Embeddings

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

##### Abstract

Our main result in this work is the extension of the Ring-LWE problem in lattice-based cryptography to include algebraic lattices, realized through twisted embeddings. We define the class of problems Twisted Ring-LWE, which replaces the canonical embedding by an extended form. We prove that our generalization for Ring-LWE is secure by providing a security reduction from Ring-LWE to Twisted Ring-LWE in both search and decision forms. It is also shown that the addition of a new parameter, the torsion factor defining the twisted embedding, does not affect the asymptotic approximation factors in the worst-case to average-case reductions. Thus, Twisted Ring-LWE maintains the consolidated hardness guarantee of Ring-LWE and increases the existing scope of algebraic lattices that can be considered for cryptographic applications. Additionally, we expand on the results of Ducas and Durmus (Public-Key Cryptography, 2012) on spherical Gaussian distributions to the proposed class of lattices under certain restrictions. Thus, sampling from a spherical Gaussian distribution can be done directly in the respective number field, while maintaining its shape and standard deviation when seen in $\mathbb{R}^n$ via twisted embeddings.

Available format(s)
Category
Foundations
Publication info
Preprint. MINOR revision.
Keywords
Lattice-based cryptographyTwisted embeddingsRing-LWESpherical Gaussian samplingZn-equivalent lattices
Contact author(s)
jheyne ortiz @ ic unicamp br
History
2021-03-30: last of 3 revisions
See all versions
Short URL
https://ia.cr/2018/356

CC BY

BibTeX

@misc{cryptoeprint:2018/356,
author = {Jheyne N.  Ortiz and Robson R.  de Araujo and Diego F.  Aranha and Sueli I.  R.  Costa and Ricardo Dahab},
title = {In Praise of Twisted Embeddings},
howpublished = {Cryptology ePrint Archive, Paper 2018/356},
year = {2018},
note = {\url{https://eprint.iacr.org/2018/356}},
url = {https://eprint.iacr.org/2018/356}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.