Paper 2013/183 Original: eprint.iacr.org/2013/183 ↗
Practical Multilinear Maps over the Integers
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.
Metadata
- Available format(s)
PDF- Category
- Public-key cryptography
- Publication info
- Preprint.
- History
- 2017-07-07: last updated
- 2013-04-01: published
- Short URL
- https://ia.cr/2013/183
- License
- https://creativecommons.org/licenses/by/4.0/
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},
url = {https://eprint.iacr.org/2013/183}
}