Name
Title | ||
|---|---|---|
Non-Malleable Codes from Average-Case Hardness: AC0, Decision Trees, and Streaming Space-Bounded Tampering. |
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: - Computational NMC against AC(0) tampering, in the CRS model, assuming a PKE scheme with decryption in AC(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. |
Year | DOI | Venue |
|---|---|---|
2017 | 10.1007/978-3-319-78372-7_20 | ADVANCES IN CRYPTOLOGY - EUROCRYPT 2018, PT III |
Field | DocType | Volume |
Decision tree,Discrete mathematics,Mathematics,Bounded function | Journal | 10822 |
ISSN | Citations | PageRank |
0302-9743 | 4 | 0.39 |
References | Authors | |
2 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Marshall Ball | 1 | 44 | 8.81 |
| Dana Dachman-Soled | 2 | 446 | 28.69 |
| Mukul Kulkarni | 3 | 6 | 1.45 |
| Tal G. Malkin | 4 | 2633 | 152.56 |