Non-Malleable Codes for Bounded Polynomial-Depth Tampering

Dana Dachman-Soled, Ilan Komargodski, and Rafael Pass

Abstract

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)
Category
Foundations
Publication info
A major revision of an IACR publication in CRYPTO 2021
Keywords
Non-malleable codespolynomial size tamperingbounded depthplain model
Contact author(s)
ilan komargodski @ ntt-research com
History
2021-11-18: revised
See all versions
Short URL
https://ia.cr/2020/776

CC BY

BibTeX

@misc{cryptoeprint:2020/776,
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{https://eprint.iacr.org/2020/776}},
url = {https://eprint.iacr.org/2020/776}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.