Cryptology ePrint Archive: Report 2018/1081

Statistical Zeroizing Attack: Cryptanalysis of Candidates of BP Obfuscation over GGH15 Multilinear Map

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

Abstract: We present a new cryptanalytic algorithm on obfuscations based on GGH15 multilinear map. Our algorithm, statistical zeroizing attack, directly distinguishes two distributions from obfuscation while it follows the zeroizing attack paradigm, that is, it uses evaluations of zeros of obfuscated programs.

Our attack breaks the recent indistinguishability obfuscation candidate suggested by Chen et al. (CRYPTO'18) for the optimal parameter settings. More precisely, we show that there are two functionally equivalent branching programs whose CVW obfuscations can be efficiently distinguished by computing the sample variance of evaluations.

This statistical attack gives a new perspective on the security of the indistinguishability obfuscations: we should consider the shape of the distributions of evaluation of obfuscation to ensure security.

In other words, while most of the previous (weak) security proofs have been studied with respect to algebraic attack model or ideal model, our attack shows that this algebraic security is not enough to achieve indistinguishability obfuscation. In particular, we show that the obfuscation scheme suggested by Bartusek et al. (TCC'18) does not {achieve} the desired security in a certain parameter regime, in which their algebraic security proof still holds.

The correctness of statistical zeroizing attacks holds under a mild assumption on the preimage sampling algorithm with a lattice trapdoor. We experimentally verify this assumption for implemented obfuscation by Halevi et al. (ACM CCS'17).

Category / Keywords: Cryptanalysis, indistinguishability obfuscation, multilinear map

Date: received 7 Nov 2018, last revised 13 Feb 2019

Contact author: tory154 at snu ac kr

Available format(s): PDF | BibTeX Citation

Note: We add an assumption on preimage sampling algorithm, and the parameter conditions for our attack. In particular, BGMZ obfuscation with optimal parameter is not broken by our attack.

Version: 20190214:062701 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]