Paper 2015/162

New Multilinear Maps over the Integers

Jean-Sebastien Coron, Tancrede Lepoint, and Mehdi Tibouchi


In the last few years, cryptographic multilinear maps have proved their tremendous potential as building blocks for new constructions, in particular the first viable approach to general program obfuscation. After the first candidate construction by Garg, Gentry and Halevi (GGH) based on ideal lattices, a second construction over the integers was described by Coron, Lepoint and Tibouchi (CLT). However the CLT scheme was recently broken by Cheon et al.; the attack works by computing the eigenvalues of a diagonalizable matrix over Q derived from the multilinear map. In this paper we describe a new candidate multilinear map over the integers. Our construction is based on CLT but with a new arithmetic technique that makes the zero-testing element non-linear in the encoding, which prevents the Cheon et al. attack. Our new construction is relatively practical as its efficiency is comparable to the original CLT scheme. Moreover the subgroup membership and decisional linear assumptions appear to hold in the new setting.

Note: Removed extension to GGH, due to security concern.

Available format(s)
Public-key cryptography
Publication info
A minor revision of an IACR publication in CRYPTO 2015
Multilinear mapsCheon et alattackCLT scheme
Contact author(s)
jean-sebastien coron @ uni lu
2015-05-16: revised
2015-02-27: received
See all versions
Short URL
Creative Commons Attribution


      author = {Jean-Sebastien Coron and Tancrede Lepoint and Mehdi Tibouchi},
      title = {New Multilinear Maps over the Integers},
      howpublished = {Cryptology ePrint Archive, Paper 2015/162},
      year = {2015},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.