Welcome to the resource topic for 2013/564
Title:
Capacity of Non-Malleable Codes
Authors: Mahdi Cheraghchi, Venkatesan Guruswami
Abstract:Non-malleable codes, introduced by Dziembowski, Pietrzak and Wichs (ICS 2010), encode messages s in a manner so that tampering the codeword causes the decoder to either output s or a message that is independent of s. While this is an impossible goal to achieve against unrestricted tampering functions, rather surprisingly non-malleable coding becomes possible against every fixed family F of tampering functions that is not too large (for instance, when |F| \le \exp(2^{\alpha n}) for some \alpha \in [0, 1) where n is the number of bits in a codeword). In this work, we study the “capacity of non-malleable coding”, and establish optimal bounds on the achievable rate as a function of the family size, answering an open problem from Dziembowski et al. (ICS 2010). Specifically, 1. We prove that for every family F with |F| \le \exp(2^{\alpha n}), there exist non-malleable codes against F with rate arbitrarily close to 1-\alpha (this is achieved w.h.p. by a randomized construction). 2. We show the existence of families of size \exp(n^{O(1)} 2^{\alpha n}) against which there is no non-malleable code of rate 1-\alpha (in fact this is the case w.h.p for a random family of this size). 3. We also show that 1-\alpha is the best achievable rate for the family of functions which are only allowed to tamper the first \alpha n bits of the codeword, which is of special interest. As a corollary, this implies that the capacity of non-malleable coding in the split-state model (where the tampering function acts independently but arbitrarily on the two halves of the codeword) equals 1/2. We also give an efficient Monte Carlo construction of codes of rate close to 1 with polynomial time encoding and decoding that is non-malleable against any fixed c > 0 and family F of size \exp(n^c), in particular tampering functions with, say, cubic size circuits.
ePrint: https://eprint.iacr.org/2013/564
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .