Non-malleable codes provide a useful and meaningful security 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 is completely unrestricted, they are known to exist for many broad tampering families F. One such natural family is the family of tampering functions in the so called split-state model. Here the message m is encoded into two shares, and the attacker is allowed to arbitrarily tamper with each share individually.
As our main result, we give several constructions of efficient, multi-bit, information-theoretically-secure non-malleable code in the split-state model, culminating in the first explicit construction achieving a constant encoding rate. The key to obtaining our results is a simple notion of non-malleable reductions, which is of independent interest.
Joint works with Divesh Aggarwal, Tomasz Kazana, Shachar Lovett and Maciej Obremski.