Cryptology ePrint Archive: Report 2013/293

A Toolkit for Ring-LWE Cryptography

Vadim Lyubashevsky and Chris Peikert and Oded Regev

Abstract: 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.

Category / Keywords: foundations / lattices, ring-LWE

Publication Info: Extended abstract appears in Eurocrypt 2013

Date: received 16 May 2013, last revised 16 May 2013

Contact author: cpeikert at cc gatech edu

Available format(s): PDF | BibTeX Citation

Version: 20130523:162730 (All versions of this report)

Short URL: ia.cr/2013/293