Paper 2022/1100

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

Gianluca Brian, Sapienza University of Rome
Antonio Faonio, EURECOM
João Ribeiro, Carnegie Mellon University
Daniele Venturi, Sapienza University of Rome

We construct non-malleable codes in the split-state model with codeword length $m + 3\lambda$ or $m+5\lambda$, where $m$ is the message size and $\lambda$ is the security parameter, depending on how conservative one is. Our scheme is very simple and involves a single call to a block cipher meeting a new security notion which we dub entropic fixed-related-key security, which essentially means that the block cipher behaves like a pseudorandom permutation when queried upon inputs sampled from a distribution with sufficient min-entropy, even under related-key attacks with respect to an arbitrary but fixed key relation. Importantly, indistinguishability only holds with respect to the original secret key (and not with respect to the tampered secret key). In a previous work, Fehr, Karpman, and Mennink (ToSC 2018) used a related assumption (where the block cipher inputs can be chosen by the adversary, and where indistinguishability holds even with respect to the tampered key) to construct a non-malleable code in the split-state model with codeword length $m + 2\lambda$. Unfortunately, no block cipher (even an ideal one) satisfies their assumption when the tampering function is allowed to be cipher-dependent. In contrast, we are able to show that entropic fixed-related-key security holds in the ideal cipher model with respect to a large class of cipher-dependent tampering attacks (including those which break the assumption of Fehr, Karpman, and Mennink).

Available format(s)
Cryptographic protocols
Publication info
A minor revision of an IACR publication in TOSC 2022
non-malleability split-state model block ciphers related-key security
Contact author(s)
brian @ di uniroma1 it
antonio faonio @ eurecom fr
jlourenc @ cs cmu edu
venturi @ di uniroma1 it
2022-08-29: revised
2022-08-25: received
See all versions
Short URL
Creative Commons Attribution


      author = {Gianluca Brian and Antonio Faonio and João Ribeiro and Daniele Venturi},
      title = {Short Non-Malleable Codes from Related-Key Secure Block Ciphers, Revisited},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1100},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.