Cryptology ePrint Archive: Report 2014/906

Cryptanalysis of the Multilinear Map over the Integers

Jung Hee Cheon and Kyoohyung Han and Changmin Lee and Hansol Ryu and Damien Stehle

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.

Category / Keywords: public-key cryptography / Multilinear maps, graded encoding schemes.

Date: received 3 Nov 2014, last revised 24 Feb 2015

Contact author: damien stehle at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20150224:140551 (All versions of this report)

Short URL: ia.cr/2014/906

Discussion forum: Show discussion | Start new discussion