Cryptology ePrint Archive: Report 2020/776

Non-Malleable Codes for Bounded Polynomial Depth Tampering

Dana Dachman-Soled and 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.

Category / Keywords: foundations / Non-malleable codes, polynomial size tampering, bounded depth, plain model

Date: received 23 Jun 2020

Contact author: ilan komargodski at ntt-research com

Available format(s): PDF | BibTeX Citation

Version: 20200624:075807 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]