Cryptology ePrint Archive: Report 2013/183

Practical Multilinear Maps over the Integers

Jean-Sebastien Coron and 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.

Category / Keywords: public-key cryptography /

Original Publication (with minor differences): IACR-CRYPTO-2013

Date: received 1 Apr 2013, last revised 5 Mar 2015

Contact author: jscoron at tranef com

Available format(s): PDF | BibTeX Citation

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

Version: 20150305:124501 (All versions of this report)

Short URL: ia.cr/2013/183

Discussion forum: Show discussion | Start new discussion