Name
Abstract | ||
|---|---|---|
We construct efficient, unconditional non-malleable codes that are secure against tampering functions computed by decision trees of depth d = n(1/4-o(1)). In particular, each bit of the tampered codeword is set arbitrarily after adaptively reading up to d arbitrary locations within the original codeword. Prior to this work, no efficient unconditional non-malleable codes were known for decision trees beyond depth O(log(2) n). Our result also yields efficient, unconditional non-malleable codes that are exp(-n(Omega(1)))-secure against constant-depth circuits of exp(n(Omega(1)))-size. Prior work of Chattopadhyay and Li (STOC 2017) and Ball et al. (FOCS 2018) only provide protection against exp(O(log(2) n))-size circuits with exp(-O(log(2) n))-security. We achieve our result through simple non-malleable reductions of decision tree tampering to split-state tampering. As an intermediary, we give a simple and generic reduction of leakage-resilient split-state tampering to split-state tampering with improved parameters. Prior work of Aggarwal et al. (TCC 2015) only provides a reduction to split-state non-malleable codes with decoders that exhibit particular properties. |
Year | DOI | Venue |
|---|---|---|
2019 | 10.1007/978-3-030-26948-7_15 | ADVANCES IN CRYPTOLOGY - CRYPTO 2019, PT 1 |
DocType | Volume | ISSN |
Conference | 11692 | 0302-9743 |
Citations | PageRank | References |
0 | 0.34 | 0 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Marshall Ball | 1 | 44 | 8.81 |
| Siyao Guo | 2 | 16 | 4.26 |
| Daniel Wichs | 3 | 1918 | 73.41 |