Cryptology ePrint Archive: Report 2017/1061

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

Marshall Ball and Dana Dachman-Soled and 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.

Category / Keywords: Foundations / non-malleable, codes, streaming, bounded space, small circuits, decision trees

Date: received 31 Oct 2017, last revised 21 Feb 2018

Contact author: mukul at terpmail umd edu

Available format(s): PDF | BibTeX Citation

Version: 20180222:034403 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]