Short Non-Malleable Codes from Related-Key Secure Block Ciphers

A non-malleable code is an unkeyed randomized encoding scheme that offers the strong guarantee that decoding a tampered codeword either results in the original message, or in an unrelated one.  We consider the simplest possible construction in the computational split-state model, which encodes a message $m$ simply as $k||E_k(m)$ for a uniformly random key $k$, where $E$ is a block cipher.  This construction is comparable to, but greatly simplifies over, the one of Kiayias et al. (ACM CCS 2016), who eschewed this simple scheme in fear of related-key attacks on $E$.  In this work, we prove this construction to be a strong non-malleable code in the split-state tampering model as long as $E$ is (i) a pseudorandom permutation under leakage and (ii) related-key secure with respect to an arbitrary but fixed key relation.  Both properties are believed to hold for ``good'' block ciphers, such as the AES, making this non-malleable code very efficient with short codewords of length $|m| + 2\\kappa$ (where $\\kappa$ is the security parameter), without significant security penalty.

This is a joint work with Serge Fehr and Bart Mennink.