Name
Abstract | ||
|---|---|---|
We construct efficient, unconditional non-malleable codes that are secure against tampering functions computed by small-depth circuits. For constant-depth circuits of polynomial size (i.e. AC
<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">0</sup>
tampering functions), our codes have codeword length n = k
<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1+0(1)</sup>
for a k-bit message. This is an exponential improvement of the previous best construction due to Chattopadhyay and Li (STOC 2017), which had codeword length 2
<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">O(√k)</sup>
. Our construction remains efficient for circuit depths as large as Θ(log(n)/loglog(n)) (indeed, our codeword length remains n ≤ k
<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1+ε</sup>
), and extending our result beyond this would require separating P from NC
<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1</sup>
. We obtain our codes via a new efficient non-malleable reduction from small-depth tampering to split-state tampering. A novel aspect of our work is the incorporation of techniques from unconditional derandomization into the framework of non-malleable reductions. In particular, a key ingredient in our analysis is a recent pseudorandom switching lemma of Trevisan and Xue (CCC 2013), a derandomization of the influential switching lemma from circuit complexity; the randomness-efficiency of this switching lemma translates into the rate-efficiency of our codes via our non-malleable reduction. |
Year | DOI | Venue |
|---|---|---|
2018 | 10.1109/FOCS.2018.00083 | 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS) |
Keywords | DocType | Volume |
Non-Malleable Codes,Small-depth Circuits,Switching Lemma | Journal | 25 |
ISSN | ISBN | Citations |
1523-8288 | 978-1-5386-4231-3 | 1 |
PageRank | References | Authors |
0.35 | 36 | 5 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Marshall Ball | 1 | 44 | 8.81 |
| Dana Dachman-Soled | 2 | 446 | 28.69 |
| Siyao Guo | 3 | 50 | 5.01 |
| Tal G. Malkin | 4 | 2633 | 152.56 |
| Li-Yang Tan | 5 | 159 | 24.26 |