Cryptology ePrint Archive: Report 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, such as [FRS17]. Finally, we suggest a set of secure parameters for CLT13 multilinear maps that prevents our attack.

Category / Keywords: public-key cryptography / Multilinear maps, lattice cryptanalysis.

Date: received 18 Mar 2019

Contact author: jscoron at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20190320:103841 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]