Paper 2019/309

Cryptanalysis of CLT13 Multilinear Maps with Independent Slots

Jean-Sebastien Coron and Luca Notarnicola

Abstract

Many constructions based on multilinear maps require independent slots in the plaintext, so that multiple computations can be performed in parallel over the slots. Such constructions are usually based on CLT13 multilinear maps, since CLT13 inherently provides a composite encoding space. However, a vulnerability was identified at Crypto 2014 by Gentry, Lewko and Waters, with a lattice-based attack in dimension 2, and the authors have suggested a simple countermeasure. In this paper, we identify an attack based on higher dimension lattice reduction that breaks the author’s countermeasure for a wide range of parameters. Combined with the Cheon et al. attack from Eurocrypt 2015, this leads to a total break of CLT13 multilinear maps with independent slots. We also show how to apply our attack against various constructions based on composite-order CLT13. For the [FRS17] construction, our attack enables to recover the secret CLT13 plaintext ring for a certain range of parameters; however, breaking the indistinguishability of the branching program remains an open problem.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published by the IACR in ASIACRYPT 2019
Keywords
Multilinear mapslattice cryptanalysis.
Contact author(s)
jscoron @ gmail com
History
2021-06-24: last of 3 revisions
2019-03-20: received
See all versions
Short URL
https://ia.cr/2019/309
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2019/309,
      author = {Jean-Sebastien Coron and Luca Notarnicola},
      title = {Cryptanalysis of CLT13 Multilinear Maps with Independent Slots},
      howpublished = {Cryptology ePrint Archive, Paper 2019/309},
      year = {2019},
      note = {\url{https://eprint.iacr.org/2019/309}},
      url = {https://eprint.iacr.org/2019/309}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.