Paper 2018/207

Non-Malleable Codes for Small-Depth Circuits

Marshall Ball, Dana Dachman-Soled, Siyao Guo, Tal Malkin, and Li-Yang Tan

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.~$\mathsf{AC^0}$ tampering functions), our codes have codeword length $n = k^{1+o(1)}$ 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^{O(\sqrt{k})}$. Our construction remains efficient for circuit depths as large as $\Theta(\log(n)/\log\log(n))$ (indeed, our codeword length remains $n\leq k^{1+\epsilon})$, and extending our result beyond this would require separating $\mathsf{P}$ from $\mathsf{NC^1}$. 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.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint.
Keywords
non-malleable codessmall-depth circuitswitching lemma
Contact author(s)
marshall @ cs columbia edu
History
2018-02-22: received
Short URL
https://ia.cr/2018/207
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/207,
      author = {Marshall Ball and Dana Dachman-Soled and Siyao Guo and Tal Malkin and Li-Yang Tan},
      title = {Non-Malleable Codes for Small-Depth Circuits},
      howpublished = {Cryptology ePrint Archive, Paper 2018/207},
      year = {2018},
      note = {\url{https://eprint.iacr.org/2018/207}},
      url = {https://eprint.iacr.org/2018/207}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.