Paper 2013/293

A Toolkit for Ring-LWE Cryptography

Vadim Lyubashevsky, Chris Peikert, and Oded Regev


Recent advances in lattice cryptography, mainly stemming from the development of ring-based primitives such as ring-$\lwe$, have made it possible to design cryptographic schemes whose efficiency is competitive with that of more traditional number-theoretic ones, along with entirely new applications like fully homomorphic encryption. Unfortunately, realizing the full potential of ring-based cryptography has so far been hindered by a lack of practical algorithms and analytical tools for working in this context. As a result, most previous works have focused on very special classes of rings such as power-of-two cyclotomics, which significantly restricts the possible applications. We bridge this gap by introducing a toolkit of fast, modular algorithms and analytical techniques that can be used in a wide variety of ring-based cryptographic applications, particularly those built around ring-\lwe. Our techniques yield applications that work in \emph{arbitrary} cyclotomic rings, with \emph{no loss} in their underlying worst-case hardness guarantees, and very little loss in computational efficiency, relative to power-of-two cyclotomics. To demonstrate the toolkit's applicability, we develop two illustrative applications: a public-key cryptosystem and a ``somewhat homomorphic'' symmetric encryption scheme. Both apply to arbitrary cyclotomics, have tight parameters, and very efficient implementations.

Available format(s)
Publication info
Published elsewhere. Extended abstract appears in Eurocrypt 2013
Contact author(s)
cpeikert @ cc gatech edu
2013-05-23: received
Short URL
Creative Commons Attribution


      author = {Vadim Lyubashevsky and Chris Peikert and Oded Regev},
      title = {A Toolkit for Ring-LWE Cryptography},
      howpublished = {Cryptology ePrint Archive, Paper 2013/293},
      year = {2013},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.