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 of cryptographic multilinear map (MMap). Despite weaknesses uncovered by Hu and Jia (EUROCRYPT 2016), this candidate is still used with tweaks in cryptographic constructions, in particular indistinguishability obfuscation (iO). The naive version of the GGH13 scheme was deemed susceptible to averaging attacks, i.e., a statistical leak (yet no precise attack was claimed). A countermeasure was therefore devised, but it remains heuristic. Recently, to reach MMaps with low noise and modulus, variants of this countermeasure were developed by Döttling et al. (EPRINT:2016/599), but their effectiveness is even less clear than in the original scheme. In this work, we propose a systematic study of this statistical leak, to conclude on the effectiveness of the countermeasure and its variants. In particular, among the two variants proposed by Döttling et al., the so-called conservative method is in fact ineffective: a sensitive secret value is leaked, the very same value as in the unprotected method. Additionally, we note that the other methods also leak secret values, but they seem less sensitive. 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: - Added mention that the leak is not limited to degree $\kappa=2$.