Efficient Non-Malleable Codes and Key Derivation for Poly-Size Tampering Circuits.

Non-malleable codes, defined by Dziembowski, Pietrzak, and Wichs (ICS ’10), provide roughly the following guarantee: if a codeword c encoding some message x is tampered to c' = f(c) such that c' \neq c , then the tampered message x' contained in c' reveals no information about x . The non-malleable codes have applications to immunizing cryptosystems against tampering attacks and related-key attacks. One cannot have an efficient non-malleable code that protects against all efficient tampering functions f . However, in this paper we show “the next best thing”: for any polynomial bound s of size | \mathcal F| \leq 2^s , there is an efficient non-malleable code that protects against all f \in \mathcal F . The rate of our codes, defined as the ratio of message to codeword size, approaches 1. Our results are information-theoretic and our main proof technique relies on a careful probabilistic method argument using limited independence. As a result, we get an efficiently samplable family of efficient codes, such that a random member of the family is non-malleable with overwhelming probability. Alternatively, we can view the result as providing an efficient non-malleable code in the “common reference string” model. We also introduce a new notion of non-malleable key derivation, which uses randomness $x$ to derive a secret key $y = h(x)$ in such a way that, even if $x$ is tampered to a different value $x' = f(x)$ , the derived key $y' = h(x')$ does not reveal any information about $y$ . Our results for non-malleable key derivation are analogous to those for non-malleable codes. As a useful tool in our analysis, we rely on the notion of “leakage-resilient storage” of Davì, Dziembowski, and Venturi (SCN ’10), and, as a result of independent interest, we also significantly improve on the parameters of such schemes. [ABSTRACT FROM PUBLISHER]