Cryptanalysis of GGH15 Multilinear Maps

Jean-Sebastien Coron; Moon Sung Lee; Tancrede Lepoint; Mehdi Tibouchi

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 cryptanalysis multilinear 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: 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},
      url = {https://eprint.iacr.org/2015/1037}
}