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


  • Serge Fehr Centrum Wiskunde & Informatica (CWI), Amsterdam, The Netherlands
  • Pierre Karpman Université Grenoble Alpes, The French National Centre for Scientific Research (CNRS) , Institute of Engineering Univ. Grenoble Alpes (Grenoble INP), Jean Kuntzmann Laboratory (LJK) , 38000 Grenoble, France
  • Bart Mennink Centrum Wiskunde & Informatica (CWI), Amsterdam, The Netherlands;Digital Security Group, Radboud University, Nijmegen, The Netherlands



Non-malleable code, split-state tampering model, related-key security, block cipher


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 message. We consider the simplest possible construction in the computational split-state model, which simply encodes a message m as k||Ek(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 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 AES-128, making this non-malleable code very efficient with short codewords of length |m|+2τ (where τ is the security parameter, e.g., 128 bits), without significant security penalty.



How to Cite

Fehr, S., Karpman, P., & Mennink, B. (2018). Short Non-Malleable Codes from Related-Key Secure Block Ciphers. IACR Transactions on Symmetric Cryptology, 2018(1), 336–352.