LJKDeterministic Models and Algorithms: CASYS Seminar

On Thursday October 12 2017 at 9h30 in Room 106  IMAG Building

Seminary of Mr Pierre KARPMAN

Short NonMalleable Codes from RelatedKey Secure Block Ciphers

Summary

A nonmalleable 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 one. We consider the simplest possible construction in the computational splitstate model, which encodes a message $m$ simply as $kE_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 relatedkey attacks on $E$. In this work, we prove this construction to be a strong nonmalleable code in the splitstate tampering model as long as $E$ is (i) a pseudorandom permutation under leakage and (ii) relatedkey secure with respect to an arbitrary but fixed key relation. Both properties are believed to hold for ``good'' block ciphers, such as the AES, making this nonmalleable code very efficient with short codewords of length $m + 2\\kappa$ (where $\\kappa$ is the security parameter), without significant security penalty.
This is a joint work with Serge Fehr and Bart Mennink.
