Welcome to the resource topic for 2018/408
Title:
Cryptanalyses of Branching Program Obfuscations over GGH13 Multilinear Map from the NTRU Problem
Authors: Jung Hee Cheon, Minki Hhan, Jiseung Kim, 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.
ePrint: https://eprint.iacr.org/2018/408
Talk: https://www.youtube.com/watch?v=ZjK7vYeW4mM
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .