Welcome to the resource topic for 2020/776
Title:
Non-Malleable Codes for Bounded Polynomial-Depth Tampering
Authors: Dana Dachman-Soled, Ilan Komargodski, 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.
ePrint: https://eprint.iacr.org/2020/776
Talk: https://www.youtube.com/watch?v=WEuNmi4iPIc
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .