International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: Cryptanalysis of CLT13 Multilinear Maps with Independent Slots

Jean-Sébastien Coron
Luca Notarnicola
DOI: 10.1007/978-3-030-34621-8_13
Search ePrint
Search Google
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, with a plaintext ring $$\bigoplus _{i=1}^n \mathbb {Z}/g_i\mathbb {Z}$$ for small primes $$g_i$$ ’s. 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 the recovery of all the secret parameters of CLT13, assuming that low-level encodings of almost zero plaintexts are available. We 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.
  title={Cryptanalysis of CLT13 Multilinear Maps with Independent Slots},
  booktitle={Advances in Cryptology – ASIACRYPT 2019},
  series={Advances in Cryptology – ASIACRYPT 2019},
  author={Jean-Sébastien Coron and Luca Notarnicola},