Non-malleable codes from average-case hardness:, decision trees, and streaming space-bounded tampering

Marshall Ball, Dana Dachman-Soled, Mukul Kulkarni, Tal Malkin

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

Abstract

We show a general framework for constructing non-malleable codes against tampering families with average-case hardness bounds. Our framework adapts ideas from the Naor-Yung double encryption paradigm such that to protect against tampering in a class$${\mathcal {F}}$$, it suffices to have average-case hard distributions for the class, and underlying primitives (encryption and non-interactive, simulatable proof systems) satisfying certain properties with respect to the class. We instantiate our scheme in a variety of contexts, yielding efficient, non-malleable codes (NMC) against the following tampering classes: Computational NMC against$${\mathsf {A}}{\mathsf {C}}^0$$ tampering, in the CRS model, assuming a PKE scheme with decryption in$${\mathsf {A}}{\mathsf {C}}^0$$ and NIZK.Computational NMC against bounded-depth decision trees (of depth$$n^\epsilon $$, where n is the number of input variables and constant$$0<\epsilon<1$$ ), in the CRS model and under the same computational assumptions as above.Information theoretic NMC (with no CRS) against a streaming, space-bounded adversary, namely an adversary modeled as a read-once branching program with bounded width. Ours are the first constructions that achieve each of the above in an efficient way, under the standard notion of non-malleability.

Original languageEnglish (US)
Title of host publicationAdvances in Cryptology - EUROCRYPT 2018 - 37th Annual International Conference on the Theory and Applications of Cryptographic Techniques, 2018 Proceedings
EditorsJesper Buus Nielsen, Vincent Rijmen
PublisherSpringer Verlag
Pages618-650
Number of pages33
ISBN (Print)9783319783710
DOIs
StatePublished - 2018
Event37th Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2018 - Tel Aviv, Israel
Duration: Apr 29 2018May 3 2018

Publication series

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

Other

Other37th Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2018
Country/TerritoryIsrael
CityTel Aviv
Period4/29/185/3/18

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint

Dive into the research topics of 'Non-malleable codes from average-case hardness:, decision trees, and streaming space-bounded tampering'. Together they form a unique fingerprint.

Cite this