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
[ Cryptology ePrint archive ]