Capacity and Constructions of Non-Malleable Codes
Date: Tuesday, December 03, 2013
Time: 4:15 PM to 5:15 PM Note: all times are in the Eastern Time Zone
Refreshments: 3:45 PM
Host: Costis Daskalakis, Dana Moshkovitz
Contact: Holly A Jones, firstname.lastname@example.org
Relevant URL: http://toc.csail.mit.edu/node/374
Speaker URL: None
email@example.com, firstname.lastname@example.org, email@example.com
TALK: 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 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 articles arXiv:1309.0458 (ITCS 2014) and arXiv:1309.1151 (TCC 2014).
Created by Holly A Jones at Monday, November 18, 2013 at 3:36 PM.