@article{Fehr_Karpman_Mennink_2018, title={Short Non-Malleable Codes from Related-Key Secure Block Ciphers}, volume={2018}, url={https://tosc.iacr.org/index.php/ToSC/article/view/854}, DOI={10.13154/tosc.v2018.i1.336-352}, abstractNote={A non-malleable code is an unkeyed randomized encoding scheme that offers the strong guarantee that decoding a <em>tampered</em> codeword either results in the original message, or in an <em>unrelated message</em>. We consider the simplest possible construction in the computational split-state model, which simply encodes a message <em>m</em> as <em>k</em>||<em>E</em><sub><em>k</em></sub>(<em>m</em>) for a uniformly random key <em>k</em>, where <em>E</em> is a block cipher. This construction is comparable to, but greatly simplifies over, the one of Kiayias <em>et al.</em> (ACM CCS 2016), who eschewed this simple scheme in fear of related-key attacks on <em>E</em>. In this work, we prove this construction to be a strong non-malleable code as long as <em>E</em> 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 |<em>m</em>|+2τ (where τ is the security parameter, e.g., 128 bits), without significant security penalty.}, number={1}, journal={IACR Transactions on Symmetric Cryptology}, author={Fehr, Serge and Karpman, Pierre and Mennink, Bart}, year={2018}, month={Mar.}, pages={336–352} }