Abstract
Informally, non-malleable codes provide a means of transforming an adversarial channel into a channel whose output is either identical to or unrelated to the input. 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^δ bits, where n is the total number of bits in a codeword and 0≤δ<1 a constant. Notably, this tampering class includes NC^0.
Joint work with Marshall Ball, Dana Dachman-Soled, and Mukul Kulkarni.