Paper 2020/776

Non-Malleable Codes for Bounded Polynomial-Depth Tampering

Dana Dachman-Soled, Ilan Komargodski, and Rafael Pass


Non-malleable codes allow one to encode data in such a way that, after tampering, the modified codeword is guaranteed to decode to either the original message, or a completely unrelated one. Since the introduction of the notion by Dziembowski, Pietrzak, and Wichs (ICS '10 and J. ACM '18), a large body of work has focused on realizing such coding schemes secure against various classes of tampering functions. It is well known that there is no efficient non-malleable code secure against all polynomial size tampering functions. Nevertheless, non-malleable codes in the plain model (i.e., no trusted setup) secure against $\textit{bounded}$ polynomial size tampering are not known and obtaining such a code has been a major open problem. We present the first construction of a non-malleable code secure against $\textit{all}$ polynomial size tampering functions that have $\textit{bounded polynomial depth}$. This is an even larger class than all bounded polynomial $\textit{size}$ functions and, in particular, we capture all functions in non-uniform $\mathbf{NC}$ (and much more). Our construction is in the plain model (i.e., no trusted setup) and relies on several cryptographic assumptions such as keyless hash functions, time-lock puzzles, as well as other standard assumptions. Additionally, our construction has several appealing properties: the complexity of encoding is independent of the class of tampering functions and we obtain sub-exponentially small error.

Available format(s)
Publication info
A major revision of an IACR publication in CRYPTO 2021
Non-malleable codespolynomial size tamperingbounded depthplain model
Contact author(s)
ilan komargodski @ ntt-research com
2021-11-18: revised
2020-06-24: received
See all versions
Short URL
Creative Commons Attribution


      author = {Dana Dachman-Soled and Ilan Komargodski and Rafael Pass},
      title = {Non-Malleable Codes for Bounded Polynomial-Depth Tampering},
      howpublished = {Cryptology ePrint Archive, Paper 2020/776},
      year = {2020},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.