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.
Category / Keywords: cryptographic protocols / Information Theory, Tamper-Resilient Cryptography, Coding Theory, Error detection, Probabilistic Method Date: received 4 Sep 2013 Contact author: cheraghchi at gmail com Available format(s): PDF | BibTeX Citation Version: 20130905:205538 (All versions of this report) Short URL: ia.cr/2013/564