Paper 2018/204

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

Serge Fehr, Pierre Karpman, and Bart Mennink

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||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 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\tau$ (where $\tau$ is the security parameter, e.g., 128 bits), without significant security penalty.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Published by the IACR in FSE 2018
Keywords
Non-malleable codesplit-state tampering modelrelated-key securityblock cipher
Contact author(s)
pierre karpman @ univ-grenoble-alpes fr
History
2018-02-22: received
Short URL
https://ia.cr/2018/204
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/204,
      author = {Serge Fehr and Pierre Karpman and Bart Mennink},
      title = {Short Non-Malleable Codes from Related-Key Secure Block Ciphers},
      howpublished = {Cryptology ePrint Archive, Paper 2018/204},
      year = {2018},
      note = {\url{https://eprint.iacr.org/2018/204}},
      url = {https://eprint.iacr.org/2018/204}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.