A toolkit for ring-LWE cryptography

Vadim Lyubashevsky, Chris Peikert, Oded Regev

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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 arbitrary cyclotomic rings, with 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.

Original languageEnglish (US)
Title of host publicationAdvances in Cryptology, EUROCRYPT 2013 - 32nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings
Pages35-54
Number of pages20
DOIs
StatePublished - 2013
Event32nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2013 - Athens, Greece
Duration: May 26 2013May 30 2013

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume7881 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other32nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2013
CountryGreece
CityAthens
Period5/26/135/30/13

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'A toolkit for ring-LWE cryptography'. Together they form a unique fingerprint.

  • Cite this

    Lyubashevsky, V., Peikert, C., & Regev, O. (2013). A toolkit for ring-LWE cryptography. In Advances in Cryptology, EUROCRYPT 2013 - 32nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings (pp. 35-54). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7881 LNCS). https://doi.org/10.1007/978-3-642-38348-9_3