Paper 2014/906
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 CRTACD 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 CRTACD problem is regarded as a hard problem, but its hardness is not proven yet. In this paper, we analyze the CRTACD 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 polynomialtime algorithm for this problem by using products of the instances and auxiliary input. This algorithm yields a polynomialtime cryptanalysis of the (approximate) multilinear map of Coron, Lepoint and Tibouchi (CLT): We show that by multiplying encodings of zero with zerotesting parameters properly in the CLT scheme, one can obtain a required input of our algorithm: products of CRTACD 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 polynomialtime algorithms for the Subgroup Membership, Decision Linear, and Graded External DiffieHellman problems, which are used as the base problems of several cryptographic schemes constructed on multilinear maps.
Metadata
 Available format(s)
 Publication info
 Preprint. MINOR revision.
 Keywords
 Multilinear mapsGraded encoding schemesDecision linear problemSubgroup membership problemGraded external DiffieHellman problem.
 Contact author(s)
 cocomi11 @ snu ac kr
 History
 20170915: last of 6 revisions
 20141103: received
 See all versions
 Short URL
 https://ia.cr/2014/906
 License

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} }