Paper 2018/408

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

Jung Hee Cheon, Minki Hhan, Jiseung Kim, and Changmin Lee


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.

Note: minor revisions

Available format(s)
Publication info
A minor revision of an IACR publication in CRYPTO 2018
Obfuscationmultilinear mapsgraded encoding schemesNTRU
Contact author(s)
hhan_ @ snu ac kr
2018-06-07: last of 2 revisions
2018-05-10: received
See all versions
Short URL
Creative Commons Attribution


      author = {Jung Hee Cheon and Minki Hhan and Jiseung Kim and Changmin Lee},
      title = {Cryptanalyses of Branching Program Obfuscations over GGH13 Multilinear Map from the NTRU Problem},
      howpublished = {Cryptology ePrint Archive, Paper 2018/408},
      year = {2018},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.