Paper 2015/1134

$\Lambda \circ \lambda$: Functional Lattice Cryptography

Eric Crockett and Chris Peikert

Abstract

This work describes the design, implementation, and evaluation of \lol, a general-purpose software framework for lattice-based cryptography. The \lol framework has several novel properties that distinguish it from prior implementations of lattice cryptosystems, including the following. \emph{Generality, modularity, concision:} \lol defines a collection of general, highly composable interfaces for mathematical operations used across lattice cryptography, allowing for a wide variety of schemes to be expressed very naturally and at a high level of abstraction. For example, we implement an advanced fully homomorphic encryption (FHE) scheme in as few as 2--5 lines of code per feature, via code that very closely matches the scheme's mathematical definition. \emph{Theory affinity:} \lol is designed from the ground-up around the specialized ring representations, fast algorithms, and worst-case hardness proofs that have been developed for the Ring-LWE problem and its cryptographic applications. In particular, it implements fast algorithms for sampling from \emph{theory-recommended} error distributions over \emph{arbitrary} cyclotomic rings, and provides tools for maintaining tight control of error growth in cryptographic schemes. \emph{Safety:} \lol has several facilities for reducing code complexity and programming errors, thereby aiding the \emph{correct} implementation of lattice cryptosystems. In particular, it uses strong typing to \emph{statically enforce}---i.e., at compile time---a wide variety of constraints among the various parameters. \emph{Advanced features:} \lol exposes the rich \emph{hierarchy} of cyclotomic rings to cryptographic applications. We use this to give the first-ever implementation of a collection of FHE operations known as ``ring switching,'' and also define and analyze a more efficient variant that we call ``ring tunneling.'' Lastly, this work defines and analyzes a variety of mathematical objects and algorithms for the recommended usage of Ring-LWE in cyclotomic rings, which we believe will serve as a useful knowledge base for future implementations.

Note: Updated with new performance data, comparisons to computer algebra systems.

Metadata
Available format(s)
PDF
Category
Implementation
Publication info
Published elsewhere. Major revision. ACM CCS 2016
DOI
10.1145/2976749.2978402
Keywords
lattice cryptographyRing-LWEfully homomorphic encryption
Contact author(s)
cpeikert @ alum mit edu
ecrockett0 @ gmail com
History
2016-08-17: last of 2 revisions
2015-11-26: received
See all versions
Short URL
https://ia.cr/2015/1134
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/1134,
      author = {Eric Crockett and Chris Peikert},
      title = {$\Lambda \circ \lambda$: Functional Lattice Cryptography},
      howpublished = {Cryptology ePrint Archive, Paper 2015/1134},
      year = {2015},
      doi = {10.1145/2976749.2978402},
      note = {\url{https://eprint.iacr.org/2015/1134}},
      url = {https://eprint.iacr.org/2015/1134}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.