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

Jung Hee Cheon, Kyoohyung Han, Changmin Lee, 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.

Available format(s)
Publication info
Preprint. MINOR revision.
Keywords
Contact author(s)
cocomi11 @ snu ac kr
History
2017-09-15: last of 6 revisions
See all versions
Short URL
https://ia.cr/2014/906

CC BY

BibTeX

@misc{cryptoeprint:2014/906,
author = {Jung Hee Cheon and Kyoohyung Han and Changmin Lee and Hansol Ryu and Damien Stehle},
title = {Cryptanalysis on the Multilinear Map over the Integers and its Related Problems},
howpublished = {Cryptology ePrint Archive, Paper 2014/906},
year = {2014},
note = {\url{https://eprint.iacr.org/2014/906}},
url = {https://eprint.iacr.org/2014/906}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.