Capacity and Constructions of Non-Malleable Codes

Non-malleable codes, introduced by Dziembowski, Pietrzak and Wichs (ICS 2010) and motivated by applications in tamper-resilient cryptography, encode messages in a manner so that tampering the codeword causes the decoder to either output the correct message or an uncorrelated message. While this relaxation of error detection is an impossible goal to achieve against unrestricted tampering functions, rather surprisingly non-malleable coding becomes possible against any fixed family of tampering functions that is not too large.

In this talk, I will discuss a subset of the following topics (depending on the time):

1. "Capacity" of non-malleable codes: For any tampering family of a prescribed size, we derive an explicit lower bound on the maximum possible rate of a non-malleable code against the given family. Furthermore, we show that this bound is essentially optimal.

2. An efficient Monte-Carlo construction of non-malleable codes against any family of tampering functions of exponential size (e.g., polynomial-sized Boolean circuits). Codes obtained by this construction achieve rates arbitrarily close to 1 and do not rely on any unproven assumptions.

3. The specific family of bit-tampering adversaries, that is adversaries that independently act on each encoded bit. For this family, we are able to obtain an explicit construction of non-malleable codes achieving rate arbitrarily close to 1.

4. We initiate the study of seedless non-malleable extractors as a natural variation of the notion of non-malleable extractors introduced by Dodis and Wichs (STOC 2009). We show that construction of non-malleable codes for the split-state model reduces to construction of non-malleable two-source extractors. We prove a general result on existence of seedless non-malleable extractors, which implies that codes obtained from our reduction can achieve rates arbitrarily close to 1/5 and exponentially small error.

Based on joint work with Venkatesan Guruswami and articles arXiv:1309.0458 (ITCS 2014) and arXiv:1309.1151 (TCC 2014).