[Resource Topic] 2018/207: Non-Malleable Codes for Small-Depth Circuits

Welcome to the resource topic for 2018/207

Non-Malleable Codes for Small-Depth Circuits

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


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.

ePrint: https://eprint.iacr.org/2018/207

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .