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

Jung Hee Cheon; Minki Hhan; Jiseung Kim; Changmin Lee

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

Abstract

In this paper, we propose cryptanalyses of all existing indistinguishability obfuscation ( $i O$ ) 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 to rule out attacks from the subfield algorithm for NTRU where is the multilinearity level and the security parameter.

Note: minor revisions

Metadata

Available format(s): PDF
Publication info: A minor revision of an IACR publication in CRYPTO 2018
Keywords: Obfuscation multilinear maps graded encoding schemes NTRU
Contact author(s): hhan_ @ snu ac kr
History: 2018-06-07: last of 2 revisions; 2018-05-10: received; See all versions
Short URL: https://ia.cr/2018/408
License: CC BY

BibTeX

@misc{cryptoeprint:2018/408,
      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},
      url = {https://eprint.iacr.org/2018/408}
}