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 less than 40 seconds per party. Moreover, in contrast with previous work, multilinear analogues of useful, base group assumptions like DLIN appear to hold in our setting.
Type de document :
Communication dans un congrès
Canetti, Ran and Garay, Juan A. CRYPTO 2013 - 33rd Annual Cryptology Conference Advances in Cryptology, Aug 2013, Santa-Barbara, United States. Springer, 8042, pp.476-493, 2013, Advances in Cryptology - CRYPTO 2013. 〈10.1007/978-3-642-40041-4_26〉
Liste complète des métadonnées

https://hal.inria.fr/hal-00872773
Contributeur : Tancrède Lepoint <>
Soumis le : lundi 14 octobre 2013 - 13:59:33
Dernière modification le : jeudi 11 janvier 2018 - 06:22:10

Identifiants

Collections

Citation

Tancrède Lepoint, Jean-Sébastien Coron, Mehdi Tibouchi. Practical Multilinear Maps over the Integers. Canetti, Ran and Garay, Juan A. CRYPTO 2013 - 33rd Annual Cryptology Conference Advances in Cryptology, Aug 2013, Santa-Barbara, United States. Springer, 8042, pp.476-493, 2013, Advances in Cryptology - CRYPTO 2013. 〈10.1007/978-3-642-40041-4_26〉. 〈hal-00872773〉

Partager

Métriques

Consultations de la notice

224