Cryptology ePrint Archive: Report 2018/408

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

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

Abstract: 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.

Category / Keywords: Obfuscation, multilinear maps, graded encoding schemes, NTRU

Original Publication (with minor differences): IACR-CRYPTO-2018

Date: received 2 May 2018, last revised 6 Jun 2018

Contact author: hhan_ at snu ac kr

Available format(s): PDF | BibTeX Citation

Note: minor revisions

Version: 20180607:041229 (All versions of this report)

Short URL: ia.cr/2018/408


[ Cryptology ePrint archive ]