Paper 2015/934

Cryptanalysis of the New CLT Multilinear Maps

Jung Hee Cheon, Changmin Lee, and Hansol Ryu

Abstract

Multilinear maps have many cryptographic applications. The first candidate construction of multilinear maps was proposed by Garg, Gentry, and Halevi (GGH13) in 2013, and soon afterwards, another candidate was suggested by Coron, Lepoint, and Tibouchi (CLT13) that works over the integers. However, both of these were found to be insecure in the face of a so-called zeroizing attack (HJ15, CHL+15). To improve on CLT13, Coron, Lepoint, and Tibouchi proposed another candidate of new multilinear maps over the integers (CLT15). In this paper, we describe an attack against CLT15. Our attack shares the essence of the cryptanalysis of CLT13 and exploits low level encodings of zero, as well as other public parameters. As in CHL+15, this leads to finding all the secret parameters of \kappa-multilinear maps in polynomial time of the security parameter.

Metadata
Available format(s)
PDF
Publication info
Preprint. Minor revision.
Keywords
Multilinear mapsgraded encoding schemeszeroizing attack.
Contact author(s)
cocomi11 @ snu ac kr
sol8586 @ snu ac kr
jhcheon @ snu ac kr
History
2016-01-15: revised
2015-09-27: received
See all versions
Short URL
https://ia.cr/2015/934
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/934,
      author = {Jung Hee Cheon and Changmin Lee and Hansol Ryu},
      title = {Cryptanalysis of the New CLT Multilinear Maps},
      howpublished = {Cryptology ePrint Archive, Paper 2015/934},
      year = {2015},
      note = {\url{https://eprint.iacr.org/2015/934}},
      url = {https://eprint.iacr.org/2015/934}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.