[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},
}