Capacity of Non-Malleable Codes

<p>Non-malleable codes, introduced by Dziembowski, Pietrzak and Wichs (ICS 2010), encode messages <em>s</em> in a manner so that tampering the codeword causes the decoder to either output <em>s</em> or a message that is independent of <em>s</em>. While this is an impossible goal to achieve against unrestricted tampering functions, rather surprisingly non-malleable coding becomes possible against every fixed family <em>F</em> of tampering functions that is not too large (for instance, when l<em>F</em>| ≤ 2^{2^α<em>n</em>} for some α < 1 where <em>n</em> is the number of bits in a codeword).</p> <p>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,</p> <ul> <li>We prove that for every family <em>F</em> with l<em>F</em>| ≤ 2^{2^α<em>n</em>}, there exist non-malleable codes against <em>F</em> with rate arbitrarily close to 1 - α (this is achieved w.h.p. by a randomized construction).</li> <li>We show the existence of families of size exp(;<em>n</em>^O(1) 2^α<em>n</em>) against which there is no non-malleable code of rate 1 - α (in fact this is the case w.h.p for a random family of this size).</li> <li>We also show that 1 - α is the best achievable rate for the family of functions which are only allowed to tamper the first α<em>n</em> bits of the codeword, which is of special interest.</li> <li>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, a model which has received some attention recently) equals 1/2.</li> </ul> <p>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 <em>c</em> > 0 and family <em>F</em> of size 2^{<em>n</em>^<em>c</em>}, in particular tampering functions with, say, cubic size circuits.</p>