Return of GGH15: Provable Security Against Zeroizing Attacks

James Bartusek, Jiaxin Guan, Fermi Ma, Mark Zhandry

Research output: Chapter in Book/Report/Conference proceedingConference contribution

12 Scopus citations

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 secure against) and the complexity-theoretic p-Bounded Speedup Hypothesis of Miles et al. [ePrint 14] (a strengthening of the Exponential Time Hypothesis).

Original languageEnglish (US)
Title of host publicationTheory of Cryptography - 16th International Conference, TCC 2018, Proceedings
EditorsAmos Beimel, Stefan Dziembowski
PublisherSpringer Science and Business Media Deutschland GmbH
Pages544-574
Number of pages31
ISBN (Print)9783030038090
DOIs
StatePublished - 2018
Event16th International Conference on Theory of Cryptography, TCC 2018 - Panaji, India
Duration: Nov 11 2018Nov 14 2018

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume11240 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference16th International Conference on Theory of Cryptography, TCC 2018
Country/TerritoryIndia
CityPanaji
Period11/11/1811/14/18

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint

Dive into the research topics of 'Return of GGH15: Provable Security Against Zeroizing Attacks'. Together they form a unique fingerprint.

Cite this