Paper 2014/906
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.
Metadata
- Available format(s)
- Publication info
- Preprint. MINOR revision.
- Keywords
- Multilinear mapsGraded encoding schemesDecision linear problemSubgroup membership problemGraded external Diffie-Hellman problem.
- Contact author(s)
- cocomi11 @ snu ac kr
- History
- 2017-09-15: last of 6 revisions
- 2014-11-03: received
- See all versions
- Short URL
- https://ia.cr/2014/906
- License
-
CC BY