The MMap Strikes Back: Obfuscation and New Multilinear Maps Immune to CLT13 Zeroizing Attacks

Fermi Ma, Mark Zhandry

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

8 Scopus citations

Abstract

All known multilinear map candidates have suffered from a class of attacks known as “zeroizing” attacks, which render them unusable for many applications. We provide a new construction of polynomial-degree multilinear maps and show that our scheme is provably immune to zeroizing attacks under a strengthening of the Branching Program Un-Annihilatability Assumption (Garg et al., TCC 2016-B). Concretely, we build our scheme on top of the CLT13 multilinear maps (Coron et al., CRYPTO 2013). In order to justify the security of our new scheme, we devise a weak multilinear map model for CLT13 that captures zeroizing attacks and generalizations, reflecting all known classical polynomial-time attacks on CLT13. In our model, we show that our new multilinear map scheme achieves ideal security, meaning no known attacks apply to our scheme. Using our scheme, we give a new multiparty key agreement protocol that is several orders of magnitude more efficient that what was previously possible. We also demonstrate the general applicability of our model by showing that several existing obfuscation and order-revealing encryption schemes, when instantiated with CLT13 maps, are secure against known attacks. These are schemes that are actually being implemented for experimentation, but until our work had no rigorous justification for security.

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
Pages513-543
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)

Keywords

  • Branching Programs
  • Multilinear Maps
  • Obfuscator
  • Order-revealing Encryption (ORE)
  • Zeroizing Attacks

Fingerprint

Dive into the research topics of 'The MMap Strikes Back: Obfuscation and New Multilinear Maps Immune to CLT13 Zeroizing Attacks'. Together they form a unique fingerprint.

Cite this