Cryptanalyses of Branching Program Obfuscations over GGH13 Multilinear Map from the NTRU Problem

In this paper, we propose cryptanalyses of all existing indistinguishability obfuscation ($iO$) candidates based on branching programs (BP) over GGH13 multilinear map for all recommended parameter settings. To achieve this, we introduce two novel techniques, program converting using NTRU-solver and matrix zeroizing, which can be applied to a wide range of obfuscation constructions and BPs compared to previous attacks. We then prove that, for the suggested parameters, the existing general-purpose BP obfuscations over GGH13 do not have the desired security. Especially, the first candidate indistinguishability obfuscation with input-unpartitionable branching programs (FOCS 2013) and the recent BP obfuscation (TCC 2016) are not secure against our attack when they use the GGH13 with recommended parameters. Previously, there has been no known polynomial time attack for these cases. Our attack shows that the lattice dimension of GGH13 must be set much larger than previous thought in order to maintain security. More precisely, the underlying lattice dimension of GGH13 should be set to $n=\tilde\Theta( \kappa^2 \lambda)$ to rule out attacks from the subfield algorithm for NTRU where $\kappa$ is the multilinearity level and $\lambda$ the security parameter