Candidate Multilinear Maps from Ideal Lattices

Sanjam Garg, Craig Gentry, and Shai Halevi

Abstract

We describe plausible lattice-based constructions with properties that approximate the sought-after multilinear maps in hard-discrete-logarithm groups, and show an example application of such multilinear maps that can be realized using our approximation. The security of our constructions relies on seemingly hard problems in ideal lattices, which can be viewed as extensions of the assumed hardness of the NTRU function.

Note: Added description of attacks on the analogues of subgroup-membership and decision-linear

Available format(s)
Category
Public-key cryptography
Publication info
Published elsewhere. Unknown where it was published
Keywords
Multilinear maps
Contact author(s)
sanjamg @ cs ucla edu
History
2013-03-17: last of 4 revisions
See all versions
Short URL
https://ia.cr/2012/610

CC BY

BibTeX

@misc{cryptoeprint:2012/610,
author = {Sanjam Garg and Craig Gentry and Shai Halevi},
title = {Candidate Multilinear Maps from Ideal Lattices},
howpublished = {Cryptology ePrint Archive, Paper 2012/610},
year = {2012},
note = {\url{https://eprint.iacr.org/2012/610}},
url = {https://eprint.iacr.org/2012/610}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.