Paper 2015/1037

Cryptanalysis of GGH15 Multilinear Maps

Jean-Sebastien Coron, Moon Sung Lee, Tancrede Lepoint, and Mehdi Tibouchi


We describe a cryptanalysis of the GGH15 multilinear maps. Our attack breaks in polynomial time the multipartite key-agreement protocol by generating an equivalent user private key. Our attack only applies to GGH15 without safeguards; for GGH15 with safeguards we only have a partial cryptanalysis that can recover any ratio of secret exponents. We also describe attacks against variants of the GGH13 multilinear maps proposed by Halevi (ePrint 2015/866) aiming at supporting graph-induced constraints, as in GGH15.

Note: We describe an extended attack that also breaks GGH15 with the safeguards.

Available format(s)
Publication info
A minor revision of an IACR publication in CRYPTO 2016
Public-key cryptanalysismultilinear maps
Contact author(s)
jscoron @ gmail com
2016-06-02: last of 3 revisions
2015-10-28: received
See all versions
Short URL
Creative Commons Attribution


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