Cryptology ePrint Archive: Report 2015/934

Cryptanalysis of the New CLT Multilinear Maps

Jung Hee Cheon and Changmin Lee and Hansol Ryu

Abstract: Multilinear maps have many cryptographic applications. The first candidate construction of multilinear maps was proposed by Garg, Gentry, and Halevi (GGH13) in 2013, and a bit later another candidate was suggested by Coron, Lepoint, and Tibouchi (CLT13) over the integers. However, both of them turned out to be insecure from so-called zeroizing attack (HJ15, CHL$^+$15). As a fix of CLT13, Coron, Lepoint, and Tibouchi proposed another candidate of new multilinear maps over the integers (CLT15).

In this paper, we describe an attack against CLT15. Our attack shares the essence of cryptanalysis of CLT13 and exploits low level encodings of zero as well as other public parameters. As in the CHL$^+$15, this leads to find all the secret parameters of $\kappa$-multiliear maps in polynomial time of security parameter.

Category / Keywords: Multilinear maps, graded encoding schemes, zeroizing attack.

Date: received 24 Sep 2015

Contact author: jhcheon at snu ac kr

Available format(s): PDF | BibTeX Citation

Version: 20150927:092632 (All versions of this report)

Short URL: ia.cr/2015/934

Discussion forum: Show discussion | Start new discussion