Capacity and Constructions of Non-Malleable Codes
November 6, 2013
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 every fixed family of tampering functions that is not too large.
In this talk, I will discuss the following:
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.
Based on joint work with Venkatesan Guruswami and papers arXiv:1309.0458 and arXiv:1309.1151.
In this talk, I will discuss the following:
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.
Based on joint work with Venkatesan Guruswami and papers arXiv:1309.0458 and arXiv:1309.1151.