Paper 2017/1061

Non-Malleable Codes from Average-Case Hardness: AC0, Decision Trees, and Streaming Space-Bounded Tampering

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

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 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: 1. Computational NMC against AC0 tampering, in the CRS model, assuming a PKE scheme with decryption in AC0 and NIZK. 2. Computational NMC against bounded-depth decision trees (of depth $t^\epsilon$, where $t$ is the number of input variables and constant $0<\epsilon<1$), in the CRS model and under the same computational assumptions as above. 3. 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.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint. MINOR revision.
Keywords
non-malleablecodesstreamingbounded spacesmall circuitsdecision trees
Contact author(s)
mukul @ terpmail umd edu
History
2018-02-22: last of 2 revisions
2017-11-03: received
See all versions
Short URL
https://ia.cr/2017/1061
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/1061,
      author = {Marshall Ball and Dana Dachman-Soled and Mukul Kulkarni and Tal Malkin},
      title = {Non-Malleable Codes from Average-Case Hardness: AC0, Decision Trees, and Streaming Space-Bounded Tampering},
      howpublished = {Cryptology ePrint Archive, Paper 2017/1061},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/1061}},
      url = {https://eprint.iacr.org/2017/1061}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.