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)
- 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
-
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}, url = {https://eprint.iacr.org/2019/309} }