Cryptanalysis of the Multilinear Map over the Integers
Jung Hee Cheon, Kyoohyung Han, Changmin Lee, Hansol Ryu and Damien Stehlé
Abstract: We describe a polynomial-time cryptanalysis of the
(approximate) multilinear map of Coron, Lepoint and Tibouchi (CLT).
The attack relies on an adaptation of the so-called zeroizing attack
against the Garg, Gentry and Halevi (GGH) candidate multilinear
map. Zeroizing is much more devastating for CLT than for GGH. In the
case of GGH, it allows to break generalizations of the Decision Linear
and Subgroup Membership problems from pairing-based cryptography. For
CLT, this leads to a total break: all quantities meant to be kept
secret can be efficiently and publicly recovered.