Mathematical Analysis of Cryptographic Multilinear Maps

Abstract

Multilinear maps are a very powerful tool in cryptography. Nonetheless, to date, only three types of multilinear maps have been published relying on a graded encoding scheme. The first candidate is proposed by Garg, Gentry, and Halevi (GGH) relying on an ideal lattice [GGH13a], the second one is dened on integers as established by Coron, Lepoint, and Tibouchi (CLT) [CLT13], and the last one is provided by Gentry, Gorbunov, and Halevi (GGH15) relying on a graph induced graded encoding scheme [GGH15]. These multilinear maps have led to a number of applications in cryptography such as one round key exchange protocol, witness encryptions, and even indistinguishable obfuscations. The security of the applications depends on some hardness problems derived from a graded encoding scheme.

However, none of them have reduction to well-known hard problems. For that reasons, many researches attempt to investigate the hardness of the problems. Actually, when low-level encodings of zero are given, the GGH scheme is known to be insecure by Hu and Jia [HJ16] and the last candidate of a multilinear map GGH15 is known to be insecure [CLLT16].

In the thesis, we describe an algebraic analysis on the hardness problems of two GGH and CLT multilinear maps. Common to two candidates are constructed by graded encoding schemes and provide an additional public information zerotesting parameter, which is used to determine whether the hidden message is zero or not. Exploiting the structure of graded encoding scheme and additional input, we study how to solve the hardness problems in three cases.

First, we show another approach to break the GGH scheme with low level encodings of zero. According to the original GGH paper, finding a short vector for a given principal ideal lattice enables to break the scheme. Therefore, the parameters are set to be invulnerable to the best known algorithm for finding a short vector on ideal lattice. By proposing an improved lattice reduction algorithm to find a short vector, we prove that the multilinear map is broken within quasi polynomial time of the suggested parameters.

Second, we describe that how to construct a level-0 encoding of zero from GGH public parameter without level encodings of zero in the quasi polynomial time of the suggested parameters. The obtained encoding of zero serves as a low level encoding of zero in the first study. Thus we also show that GGH without low level encodings of zero is insecure.

Finally, for CLT scheme with low level encodings of zero, we attempt to reveal the all secret elements of scheme in polynomial time. By multiplying encodings of zero to zerotesting parameter appropriately, one can obtain an integer matrix of secret quantities. Next we recover the secret elements by computing eigenvalues.