Paper 2015/1037

Cryptanalysis of GGH15 Multilinear Maps

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

Abstract

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.

Metadata
Available format(s)
PDF
Publication info
A minor revision of an IACR publication in CRYPTO 2016
Keywords
Public-key cryptanalysismultilinear maps
Contact author(s)
jscoron @ gmail com
History
2016-06-02: last of 3 revisions
2015-10-28: received
See all versions
Short URL
https://ia.cr/2015/1037
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/1037,
      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{https://eprint.iacr.org/2015/1037}},
      url = {https://eprint.iacr.org/2015/1037}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.