Non-Malleable Codes for Bounded Depth Circuits
Marshall Ball

Abstract:

We show how to construct efficient, unconditionally secure non-malleable codes for the class of functions with bounded output locality. In particular, our scheme is resilient against functions such that any output bit is dependent on at most c√ n /log(n) bits, where n is the total number of bits in a codeword and c is a constant. Notably, this tampering class includes NC⁰.

Joint work with Dana Dachman-Soled, Mukul Kulkarni, and Tal Malkin.