Paper 2016/135

Cryptanalysis of the New CLT Multilinear Map over the Integers

Jung Hee Cheon, Pierre-Alain Fouque, Changmin Lee, Brice Minaud, and Hansol Ryu

Abstract

Multilinear maps serve as a basis for a wide range of cryptographic applications. The first candidate construction of multilinear maps was proposed by Garg, Gentry, and Halevi in 2013, and soon afterwards, another construction was suggested by Coron, Lepoint, and Tibouchi (CLT13), which works over the integers. However, both of these were found to be insecure in the face of so-called zeroizing attacks, by Hu and Jia, and by Cheon, Han, Lee, Ryu and Stehlé. To improve on CLT13, Coron, Lepoint, and Tibouchi proposed another candidate construction of multilinear maps over the integers at Crypto 2015 (CLT15). This article presents two polynomial attacks on the CLT15 multilinear map, which share ideas similar to the cryptanalysis of CLT13. Our attacks allow recovery of all secret parameters in time polynomial in the security parameter, and lead to a full break of the CLT15 multilinear map for virtually all applications.

Note: This is a merge of 2015/934 and 2015/941 for publication at Eurocrypt.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published by the IACR in EUROCRYPT 2016
Keywords
Multilinear mapsGraded Encoding Schemes.
Contact author(s)
brice minaud @ gmail com
History
2016-02-15: received
Short URL
https://ia.cr/2016/135
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/135,
      author = {Jung Hee Cheon and Pierre-Alain Fouque and Changmin Lee and Brice Minaud and Hansol Ryu},
      title = {Cryptanalysis of the New CLT Multilinear Map over the Integers},
      howpublished = {Cryptology ePrint Archive, Paper 2016/135},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/135}},
      url = {https://eprint.iacr.org/2016/135}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.