Non-Malleable Codes for Small-Depth Circuits.

We construct efficient, unconditional non-malleable codes that are secureagainst tampering functions computed by small-depth circuits. Forconstant-depth circuits of polynomial size (i.e. $\mathsf{AC^0}$ tamperingfunctions), our codes have codeword length $n = k^{1+o(1)}$ for a $k$-bitmessage. This is an exponential improvement of the previous best constructiondue to Chattopadhyay and Li (STOC 2017), which had codeword length$2^{O(\sqrt{k})}$. Our construction remains efficient for circuit depths aslarge as $\Theta(\log(n)/\log\log(n))$ (indeed, our codeword length remains$n\leq k^{1+\epsilon})$, and extending our result beyond this would requireseparating $\mathsf{P}$ from $\mathsf{NC^1}$.

We obtain our codes via a new efficient non-malleable reduction fromsmall-depth tampering to split-state tampering. A novel aspect of our work isthe incorporation of techniques from unconditional derandomization into theframework of non-malleable reductions. In particular, a key ingredient in ouranalysis is a recent pseudorandom switching lemma of Trevisan and Xue (CCC2013), a derandomization of the influential switching lemma from circuitcomplexity; the randomness-efficiency of this switching lemma translates intothe rate-efficiency of our codes via our non-malleable reduction.