Welcome to the resource topic for 2018/1015
Title:
Non-Malleable Codes Against Bounded Polynomial Time Tampering
Authors: Marshall Ball, Dana Dachman-Soled, Mukul Kulkarni, Huijia Lin, Tal Malkin
Abstract:We construct efficient non-malleable codes (NMC) that are (computationally) secure against tampering by functions computable in any fixed polynomial time. Our construction is in the plain (no-CRS) model and requires the assumptions that (1) \mathbf{E} is hard for \mathbf{NP} circuits of some exponential 2^{\beta n} (\beta>0) size (widely used in the derandomization literature), (2) sub-exponential trapdoor permutations exist, and (3) \mathbf{P} certificates with sub-exponential soundness exist. While it is impossible to construct NMC secure against arbitrary polynomial-time tampering (Dziembowski, Pietrzak, Wichs, ICS '10), the existence of NMC secure against O(n^c)-time tampering functions (for any fixed c), was shown (Cheraghchi and Guruswami, ITCS '14) via a probabilistic construction. An explicit construction was given (Faust, Mukherjee, Venturi, Wichs, Eurocrypt '14) assuming an untamperable CRS with length longer than the runtime of the tampering function. In this work, we show that under computational assumptions, we can bypass these limitations. Specifically, under the assumptions listed above, we obtain non-malleable codes in the plain model against O(n^c)-time tampering functions (for any fixed c), with codeword length independent of the tampering time bound. Our new construction of NMC draws a connection with non-interactive non-malleable commitments. In fact, we show that in the NMC setting, it suffices to have a much weaker notion called quasi non-malleable commitments—these are non-interactive, non-malleable commitments in the plain model, in which the adversary runs in O(n^c)-time, whereas the honest parties may run in longer (polynomial) time. We then construct a 4-tag quasi non-malleable commitment from any sub-exponential OWF and the assumption that \mathbf{E} is hard for some exponential size \mathbf{NP}-circuits, and use tag amplification techniques to support an exponential number of tags.
ePrint: https://eprint.iacr.org/2018/1015
Talk: https://www.youtube.com/watch?v=yAA420WbcLo
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 .