International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

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

Authors:
Serge Fehr , CWI, Amsterdam
Pierre Karpman , Univ. Grenoble Alpes, CNRS, Grenoble INP, LJK, 38000 Grenoble
Bart Mennink , CWI, Amsterdam; Digital Security Group, Radboud University, Nijmegen
Download:
DOI: 10.13154/tosc.v2018.i1.336-352
URL: https://tosc.iacr.org/index.php/ToSC/article/view/854
Search ePrint
Search Google
Abstract: 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.
BibTeX
@article{tosc-2018-28402,
  title={Short Non-Malleable Codes from Related-Key Secure Block Ciphers},
  journal={IACR Trans. Symmetric Cryptol.},
  publisher={Ruhr-Universität Bochum},
  volume={2018, Issue 1},
  pages={336-352},
  url={https://tosc.iacr.org/index.php/ToSC/article/view/854},
  doi={10.13154/tosc.v2018.i1.336-352},
  author={Serge Fehr and Pierre Karpman and Bart Mennink},
  year=2018
}