Paper 2014/645

Graph-Induced Multilinear Maps from Lattices

Craig Gentry, Sergey Gorbunov, and Shai Halevi

Abstract

Graded multilinear encodings have found extensive applications in cryptography ranging from non-interactive key exchange protocols, to broadcast and attribute-based encryption, and even to software obfuscation. Despite seemingly unlimited applicability, essentially only two candidate constructions are known (GGH and CLT). In this work, we describe a new graph-induced multilinear encoding scheme from lattices. In a graph-induced multilinear encoding scheme the arithmetic operations that are allowed are restricted through an explicitly defined directed graph (somewhat similar to the "asymmetric variant" of previous schemes). Our construction encodes Learning With Errors (LWE) samples in short square matrices of higher dimensions. Addition and multiplication of the encodings corresponds naturally to addition and multiplication of the LWE secrets.

Metadata
Available format(s)
PDF
Publication info
Preprint. MINOR revision.
Keywords
LatticesLWEMultilinear Maps
Contact author(s)
sergeyg @ mit edu
History
2014-11-12: last of 2 revisions
2014-08-27: received
See all versions
Short URL
https://ia.cr/2014/645
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2014/645,
      author = {Craig Gentry and Sergey Gorbunov and Shai Halevi},
      title = {Graph-Induced Multilinear Maps from Lattices},
      howpublished = {Cryptology ePrint Archive, Paper 2014/645},
      year = {2014},
      note = {\url{https://eprint.iacr.org/2014/645}},
      url = {https://eprint.iacr.org/2014/645}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.