Paper 2013/702

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

Sebastian Faust, Pratyay Mukherjee, Daniele Venturi, and Daniel Wichs


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$. 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 work we show ``the next best thing'': for any polynomial bound $s$ given a-priori, there is an efficient non-malleable code that protects against all tampering functions $f$ computable by a circuit of size $s$. More generally, for any family of tampering functions $\F$ of size $|\F| \leq 2^{s}$, there is an efficient non-malleable code that protects against all $f \in \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'' (CRS) 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 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.

Available format(s)
Publication info
Preprint. MINOR revision.
information theorynon-malleabilitycodes
Contact author(s)
wichs @ ccs neu edu
2014-05-15: revised
2013-10-28: received
See all versions
Short URL
Creative Commons Attribution


      author = {Sebastian Faust and Pratyay Mukherjee and Daniele Venturi and Daniel Wichs},
      title = {Efficient Non-Malleable Codes and Key-Derivation for Poly-Size Tampering Circuits},
      howpublished = {Cryptology ePrint Archive, Paper 2013/702},
      year = {2013},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.