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

Abstract

We construct non-malleable codes in the split-state model with codeword length m + 3λ or m + 5λ, where m is the message size and λ is the security parameter, depending on how conservative one is. Our scheme is very simple and involves a single call to a block cipher meeting a new security notion which we dub entropic fixed-related-key security, which essentially means that the block cipher behaves like a pseudorandom permutation when queried upon inputs sampled from a distribution with sufficient min-entropy, even under related-key attacks with respect to an arbitrary but fixed key relation. Importantly, indistinguishability only holds with respect to the original secret key (and not with respect to the tampered secret key).
In a previous work, Fehr, Karpman, and Mennink (ToSC 2018) used a related assumption (where the block cipher inputs can be chosen by the adversary, and where indistinguishability holds even with respect to the tampered key) to construct a nonmalleable code in the split-state model with codeword length m + 2λ. Unfortunately, no block cipher (even an ideal one) satisfies their assumption when the tampering function is allowed to be cipher-dependent. In contrast, we are able to show that entropic fixed-related-key security holds in the ideal cipher model with respect to a large class of cipher-dependent tampering attacks (including those which break the assumption of Fehr, Karpman, and Mennink).