**Cryptanalysis on the Multilinear Map over the Integers and its Related Problems**

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

**Abstract: **The CRT-ACD problem is to find the primes p_1,...,p_n given polynomially many instances of CRT_{(p_1,...,p_n)}(r_1,...,r_n) for small integers r_1,...,r_n. The CRT-ACD problem is regarded as a hard problem, but its hardness is not proven yet. In this paper, we analyze the CRT-ACD problem when given one more input CRT_{(p_1,...,p_n)}(x_0/p_1,...,x_0/p_n) for x_0=\prod\limits_{i=1}^n p_i and propose a polynomial-time algorithm for this problem by using products of the instances and auxiliary input.

This algorithm yields a polynomial-time cryptanalysis of the (approximate) multilinear map of Coron, Lepoint and Tibouchi (CLT): We show that by multiplying encodings of zero with zero-testing parameters properly in the CLT scheme, one can obtain a required input of our algorithm: products of CRT-ACD instances and auxiliary input. This leads to a total break: all the quantities that were supposed to be kept secret can be recovered in an efficient and public manner.

We also introduce polynomial-time algorithms for the Subgroup Membership, Decision Linear, and Graded External Diffie-Hellman problems, which are used as the base problems of several cryptographic schemes constructed on multilinear maps.

**Category / Keywords: **Multilinear maps, Graded encoding schemes, Decision linear problem, Subgroup membership problem, Graded external Diffie-Hellman problem.

**Date: **received 3 Nov 2014, last revised 15 Sep 2017

**Contact author: **cocomi11 at snu ac kr

**Available format(s): **PDF | BibTeX Citation

**Version: **20170915:120747 (All versions of this report)

**Short URL: **ia.cr/2014/906

[ Cryptology ePrint archive ]