Paper 2015/941

Cryptanalysis of the New Multilinear Map over the Integers

Brice Minaud and Pierre-Alain Fouque

Abstract

This article describes a polynomial attack on the new multilinear map over the integers presented by Coron, Lepoint and Tibouchi at CRYPTO 2015 (CLT15). This version is a fix of the first multilinear map over the integers presented by the same authors at CRYPTO 2013 (CLT13) and broken by Cheon et al. at EUROCRYPT 2015. The attack essentially downgrades CLT15 to its original version CLT13, and leads to a full break of the multilinear map for virtually all applications. In addition to the main attack, we present an alternate probabilistic attack underpinned by a different technique, as well as an instant-time attack on the optimized variant of the scheme.

Metadata
Available format(s)
PDF
Publication info
Preprint. MINOR revision.
Keywords
Multilinear mapsgraded encoding schemes
Contact author(s)
brice minaud @ gmail com
History
2015-10-08: revised
2015-09-28: received
See all versions
Short URL
https://ia.cr/2015/941
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/941,
      author = {Brice Minaud and Pierre-Alain Fouque},
      title = {Cryptanalysis of the New Multilinear Map over the Integers},
      howpublished = {Cryptology ePrint Archive, Paper 2015/941},
      year = {2015},
      note = {\url{https://eprint.iacr.org/2015/941}},
      url = {https://eprint.iacr.org/2015/941}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.