Mathematical Analysis of Multilinear Maps over the Integers

Abstract

Multilinear maps have lots of cryptographic applications. Until now, there are three types of multilinear maps: the first is constructed using ideal lattices, the second is defined over the integers, and the last is graph-induced one. However none of them have reduction to well-known hard problems. More serious matter is that they are all proven insecure when low-level encodings of zero are provided .

Especially, for multilinear maps over the integers, construction and analysis are being repeated. At {\sc Crypto} 2013, Coron, Lepoint, and Tibouchi proposed a multilinear map using CRT (CLT13). However, it was revealed to be insecure so-called CHLRS attack (CHL$^+$15). After then, several attempts have been made to repair the scheme, but quickly proven insecure by extended CHLRS attack. The same authors revised their scheme at {\sc Crypto} 2015 again.

In this thesis, we describe attacks against CLT15. Our attacks share the essence of the cryptanalysis of CLT13 and exploits low level encodings of zero, provided by a ladder, as well as other public parameters. As in CHL$^+$15, this leads to finding all the secret parameters of $\kappa$-multilinear maps in polynomial time of the security parameter. As a result, CLT15 is fully broken for all possible applications, while the security of CLT13 is not known when low-level encodings are not provided.