Paper 2017/040

Practical Non-Malleable Codes from $\ell$-more Extractable Hash Functions

Aggelos Kiayias
Feng-Hao Liu
Yiannis Tselekounis

In this work, we significantly improve the efficiency of non-malleable codes in the split state model, by constructing a code with codeword length $|s|+O(k)$, where $|s|$ is the length of the message, and $k$ is the security parameter. This is a substantial improvement over previous constructions, both asymptotically and concretely. Our construction relies on a new primitive which we define and study, called $\ell$-more extractable hash functions. This notion, which may be of independent interest, guarantees that any adversary that is given access to $\ell \in \mathbb{N}$ precomputed hash values $v_{1},\dots, v_{\ell}$, and produces a new valid hash value $\tilde v$, then it must know a pre-image of $\tilde v$. This is a stronger notion that the one by Bitansky et al. (Eprint '11) and Goldwasser et al. (ITCS '12, Eprint '14), which considers adversaries that get no access to precomputed hash values prior to producing their own value. By appropriately relaxing the extractability requirement (without hurting the applicability of the primitive) we instantiate $\ell$-more extractable hash functions under the same assumptions used for the previous extractable hash functions by Bitansky et al. and Goldwasser et al. (a variant of the Knowledge of Exponent Assumption).

Note: Extended abstract and minor intro changes.

Available format(s)
Publication info
Published elsewhere. ACM Conference on Computer and Communications Security 2016
Non-malleable codes hash functions split-state model
Contact author(s)
tselekounis @ sians org
2022-12-19: last of 5 revisions
2017-01-18: received
See all versions
Short URL
Creative Commons Attribution


      author = {Aggelos Kiayias and Feng-Hao Liu and Yiannis Tselekounis},
      title = {Practical Non-Malleable Codes from $\ell$-more Extractable Hash Functions},
      howpublished = {Cryptology ePrint Archive, Paper 2017/040},
      year = {2017},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.