Paper 2018/1081

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

Jung Hee Cheon, Wonhee Cho, Minki Hhan, 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).

Note: We revise some errata of proof in Prop 3.1

Metadata
Available format(s)
PDF
Publication info
A minor revision of an IACR publication in CRYPTO 2019
Keywords
Cryptanalysisindistinguishability obfuscationmultilinear map
Contact author(s)
tory154 @ snu ac kr
History
2019-11-02: last of 3 revisions
2018-11-09: received
See all versions
Short URL
https://ia.cr/2018/1081
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/1081,
      author = {Jung Hee Cheon and Wonhee Cho and Minki Hhan and Jiseung Kim and Changmin Lee},
      title = {Statistical Zeroizing Attack: Cryptanalysis of Candidates of BP Obfuscation over GGH15 Multilinear Map},
      howpublished = {Cryptology ePrint Archive, Paper 2018/1081},
      year = {2018},
      note = {\url{https://eprint.iacr.org/2018/1081}},
      url = {https://eprint.iacr.org/2018/1081}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.