Paper 2013/702
Efficient Non-Malleable Codes and Key-Derivation for Poly-Size Tampering Circuits
Sebastian Faust, Pratyay Mukherjee, Daniele Venturi, and Daniel Wichs
Abstract
Non-malleable codes, defined by Dziembowski, Pietrzak and Wichs (ICS '10), provide roughly the following guarantee: if a codeword encoding some message is tampered to such that , then the tampered message contained in reveals no information about . 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 . However, in this work we show ``the next best thing'': for any polynomial bound given a-priori, there is an efficient non-malleable code that protects against all tampering functions computable by a circuit of size . More generally, for any family of tampering functions of size , there is an efficient non-malleable code that protects against all . The rate of our codes, defined as the ratio of message to codeword size, approaches . 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'' (CRS) model.
We also introduce a new notion of non-malleable key derivation, which uses randomness to derive a secret key in such a way that, even if is tampered to a different value , the derived key does not reveal any information about . 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 Davi, Dziembowski and Venturi (SCN '10) and, as a result of independent interest, we also significantly improve on the parameters of such schemes.
Note: The last revision fixed a few typos.