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 | 2 2 αn for some α < 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, • We prove that for every family F with |F | 2 2 αn , there exist non-malleable codes against F with rate arbitrarily close to 1 − α (this is achieved w.h.p. by a randomized construction). • We show the existence of families of size exp(n O(1) 2 αn ) 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). • We also show that 1 − α is the best achievable rate for the family of functions which are only allowed to tamper the first αn bits of the codeword, which is of special interest. Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from permissions@acm.org. ITCS'14, January 12-14, 2014, Princeton, New Jersey, USA. Copyright 2014 ACM 978-1-4503-2698 As a corollary, this implies that the capacity of nonmalleable 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. 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 2 n c , in particular tampering functions with say cubic size circuits.
Bound on the rate of non-malleable codes was first studied in REF .
Capacity of non-malleable codes
ITCS '14
Mathematics Computer Science