International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: Non-Malleable Codes for Bounded Parallel-Time Tampering

Dana Dachman-Soled , University of Maryland
Ilan Komargodski , Hebrew University and NTT Research
Rafael Pass , Cornell Tech
DOI: 10.1007/978-3-030-84252-9_18 (login may be required)
Search ePrint
Search Google
Conference: CRYPTO 2021
Abstract: Non-malleable codes allow one to encode data in such a way that once a codeword is being tampered with, the modified codeword is either an encoding of the original message, or a completely unrelated one. Since the introduction of this notion by Dziembowski, Pietrzak, and Wichs (ICS '10 and J. ACM '18), there has been a large body of works 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, no code which is non-malleable for \emph{bounded} polynomial size attackers is known and obtaining such a code has been a major open problem. We present the first construction of a non-malleable code secure against all polynomial size tampering functions that have {bounded} parallel time. This is an even larger class than all bounded polynomial size functions. In particular, this class includes 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 can obtain (sub-)exponentially small error.
Video from CRYPTO 2021
  title={Non-Malleable Codes for Bounded Parallel-Time Tampering},
  author={Dana Dachman-Soled and Ilan Komargodski and Rafael Pass},