[CLT13] Practical Multilinear Maps over the Integers

Authors: Jean-Sébastien Coron, Tancrède Lepoint, Mehdi Tibouchi | Venue: CRYPTO 2013 | Source

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 seconds per party.

BibTeX

@Inproceedings{C:CorLepTib13,
  author = {Jean-S{\'e}bastien Coron and Tancr{\`e}de Lepoint and Mehdi Tibouchi},
  title = {Practical Multilinear Maps over the Integers},
  pages = {476--493},
  editor = {Ran Canetti and Juan A. Garay},
  booktitle = {Advances in Cryptology -- {CRYPTO}~2013, Part~I},
  volume = {8042},
  series = {Lecture Notes in Computer Science},
  address = {Santa Barbara, CA, USA},
  month = {aug~18--22},
  publisher = {Springer Berlin Heidelberg, Germany},
  year = {2013},
  doi = {10.1007/978-3-642-40041-4_26},
}