Non-malleable Reductions and Applications

Non-malleable codes, introduced by Dziembowski, Pietrzak and Wichs [DPW10], provide a useful message integrity guarantee in situations where traditional error-correction (and even error-detection) is impossible; for example, when the attacker can completely overwrite the encoded message. Informally, a code is non-malleable if the message contained in a modified codeword is either the original message, or a completely "unrelated value". Although such codes do not exist if the family of "tampering functions" F allowed to modify the original codeword is completely unrestricted, they are known to exist for many broad tampering families F. The family which received the most attention [DPW10, LL12, DKO13, ADL14, CG14a, CG14b] is the family of tampering functions in the so called (2-part) split-state model: here the message x is encoded into two shares L and R, and the attacker is allowed to arbitrarily tamper with each L and R individually. Despite this attention, the following problem remained open: Build efficient, information-theoretically secure non-malleable codes in the split-state model with constant encoding rate: |L| = |R| = O(|x|). In this work, we resolve this open problem.

Published in:
STOC '15: Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, 459-468
Presented at:
47th Annual Symposium on the Theory of Computing, Portland, Oregon, USA, June 15-17, 2015

 Record created 2015-08-31, last modified 2018-03-17

Download fulltext

Rate this document:

Rate this document:
(Not yet reviewed)