Paper 2016/307

Non-Malleable Codes for Bounded Depth, Bounded Fan-in Circuits

Marshall Ball and Dana Dachman-Soled and Mukul Kulkarni and Tal Malkin

Abstract

We show how to construct efficient, unconditionally secure non-malleable codes for bounded output locality. In particular, our scheme is resilient against functions such that any output bit is dependent on at most $n^{\delta}$ bits, where $n$ is the total number of bits in a codeword and $0 \leq \delta < 1$ a constant. Notably, this tampering class includes $\mathsf{NC}^0$.