Paper 2018/356

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.

Metadata
Available format(s)
PDF
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
2018-04-18: received
See all versions
Short URL
https://ia.cr/2018/356
License
Creative Commons Attribution
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.