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 <> 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| ≤ 2s, there is an efficient nonmalleable code that protects against all f ∈ 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 Davı, Dziembowski and Venturi (SCN ’10) and, as a result of independent interest, we also significantly improve on the parameters of such schemes.


Published in:
Advances in Cryptology – EUROCRYPT 2014, 111-128
Presented at:
33rd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Copenhagen, Denmark, May 11 – 15, 2014
Year:
2014
Publisher:
Berlin, Springer
ISBN:
978-3-642-55219-9
Laboratories:




 Record created 2014-05-26, last modified 2018-09-13

n/a:
Download fulltext
PDF

Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)