Paper 2017/482

On the Statistical Leak of the GGH13 Multilinear Map and some Variants

Léo Ducas and Alice Pellet--Mary

Abstract

At EUROCRYPT 2013, Garg, Gentry and Halevi proposed a candidate construction (later referred as GGH13) of cryptographic multilinear map (MMap). Despite weaknesses uncovered by Hu and Jia (EUROCRYPT 2016), this candidate is still used for designing obfuscators. The naive version of the GGH13 scheme was deemed susceptible to averaging attacks, i.e., it could suffer from a statistical leak (yet no precise attack was described). A variant was therefore devised, but it remains heuristic. Recently, to obtain MMaps with low noise and modulus, two variants of this countermeasure were developed by Döttling et al. (EPRINT:2016/599). In this work, we propose a systematic study of this statistical leak for all these GGH13 variants. In particular, we confirm the weakness of the naive version of GGH13. We also show that, among the two variants proposed by Döttling et al., the so-called conservative method is not so effective: it leaks the same value as the unprotected method. Luckily, the leak is more noisy than in the unprotected method, making the straightforward attack unsuccessful. Additionally, we note that all the other methods also leak values correlated with secrets. As a conclusion, we propose yet another countermeasure, for which this leak is made unrelated to all secrets. On our way, we also make explicit and tighten the hidden exponents in the size of the parameters, as an effort to assess and improve the efficiency of MMaps.

Note: Add acknowledgements.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
CryptanalysisMultilinear MapsStatistical LeaksIdeal Lattices.
Contact author(s)
ducas @ cwi nl
History
2017-11-06: last of 3 revisions
2017-05-30: received
See all versions
Short URL
https://ia.cr/2017/482
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/482,
      author = {Léo Ducas and Alice Pellet--Mary},
      title = {On the Statistical Leak of the GGH13 Multilinear Map and some Variants},
      howpublished = {Cryptology ePrint Archive, Paper 2017/482},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/482}},
      url = {https://eprint.iacr.org/2017/482}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.