Paper 2013/564
Capacity of NonMalleable Codes
Mahdi Cheraghchi and Venkatesan Guruswami
Abstract
Nonmalleable 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 nonmalleable 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 nonmalleable 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 nonmalleable 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 nonmalleable 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 nonmalleable coding in the splitstate 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 nonmalleable against any fixed $c > 0$ and family $F$ of size $\exp(n^c)$, in particular tampering functions with, say, cubic size circuits.
Metadata
 Available format(s)
 Category
 Cryptographic protocols
 Publication info
 Preprint. MINOR revision.
 Keywords
 Information TheoryTamperResilient CryptographyCoding TheoryError detectionProbabilistic Method
 Contact author(s)
 cheraghchi @ gmail com
 History
 20130905: received
 Short URL
 https://ia.cr/2013/564
 License

CC BY
BibTeX
@misc{cryptoeprint:2013/564, author = {Mahdi Cheraghchi and Venkatesan Guruswami}, title = {Capacity of NonMalleable Codes}, howpublished = {Cryptology ePrint Archive, Paper 2013/564}, year = {2013}, note = {\url{https://eprint.iacr.org/2013/564}}, url = {https://eprint.iacr.org/2013/564} }