Paper 2018/511

Return of GGH15: Provable Security Against Zeroizing Attacks

James Bartusek, Jiaxin Guan, Fermi Ma, and Mark Zhandry

Abstract

The GGH15 multilinear maps have served as the foundation for a number of cutting-edge cryptographic proposals. Unfortunately, many schemes built on GGH15 have been explicitly broken by so-called ``zeroizing attacks,'' which exploit leakage from honest zero-test queries. The precise settings in which zeroizing attacks are possible have remained unclear. Most notably, none of the current indistinguishability obfuscation (iO) candidates from GGH15 have any formal security guarantees against zeroizing attacks. In this work, we demonstrate that all known zeroizing attacks on GGH15 implicitly construct algebraic relations between the results of zero-testing and the encoded plaintext elements. We then propose a ``GGH15 zeroizing model" as a new general framework which greatly generalizes known attacks. Our second contribution is to describe a new GGH15 variant, which we formally analyze in our GGH15 zeroizing model. We then construct a new iO candidate using our multilinear map, which we prove secure in the GGH15 zeroizing model. This implies resistance to all known zeroizing strategies. The proof relies on the Branching Program Un-Annihilatability (BPUA) Assumption of Garg et al. [TCC 16-B] (which is implied by PRFs in NC^1 secure against P/Poly) and the complexity-theoretic p-Bounded Speedup Hypothesis of Miles et al. [ePrint 14] (a strengthening of the Exponential Time Hypothesis).

Note: improved exposition, added comparison to CLT13 weak model, new title.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
A major revision of an IACR publication in TCC 2018
Keywords
multilinear mapsobfuscationGGH15
Contact author(s)
fermima1 @ gmail com
History
2018-10-28: last of 2 revisions
2018-05-26: received
See all versions
Short URL
https://ia.cr/2018/511
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/511,
      author = {James Bartusek and Jiaxin Guan and Fermi Ma and Mark Zhandry},
      title = {Return of GGH15: Provable Security Against Zeroizing Attacks},
      howpublished = {Cryptology ePrint Archive, Paper 2018/511},
      year = {2018},
      note = {\url{https://eprint.iacr.org/2018/511}},
      url = {https://eprint.iacr.org/2018/511}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.