Paper 2013/183

Practical Multilinear Maps over the Integers

Jean-Sebastien Coron, Tancrede Lepoint, and Mehdi Tibouchi

Abstract

Extending bilinear elliptic curve pairings to multilinear maps is a long-standing open problem. The first plausible construction of such multilinear maps has recently been described by Garg, Gentry and Halevi, based on ideal lattices. In this paper we describe a different construction that works over the integers instead of ideal lattices, similar to the DGHV fully homomorphic encryption scheme. We also describe a different technique for proving the full randomization of encodings: instead of Gaussian linear sums, we apply the classical leftover hash lemma over a quotient lattice. We show that our construction is relatively practical: for reasonable security parameters a one-round 7-party Diffie-Hellman key exchange requires about $25$ seconds per party.

Note: An extended abstract will appear at Crypto 2013. This is the full version.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
A minor revision of an IACR publication in CRYPTO 2013
Contact author(s)
jscoron @ tranef com
History
2017-07-07: last of 4 revisions
2013-04-01: received
See all versions
Short URL
https://ia.cr/2013/183
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2013/183,
      author = {Jean-Sebastien Coron and Tancrede Lepoint and Mehdi Tibouchi},
      title = {Practical Multilinear Maps over the Integers},
      howpublished = {Cryptology ePrint Archive, Paper 2013/183},
      year = {2013},
      note = {\url{https://eprint.iacr.org/2013/183}},
      url = {https://eprint.iacr.org/2013/183}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.