Welcome to the resource topic for 2019/379
Title:
Non-Malleable Codes for Decision Trees
Authors: Marshall Ball, Siyao Guo, Daniel Wichs
Abstract:We construct efficient, unconditional non-malleable codes that are secure against tampering functions computed by decision trees of depth d = n^{1/4-o(1)}. In particular, each bit of the tampered codeword is set arbitrarily after adaptively reading up to d arbitrary locations within the original codeword. Prior to this work, no efficient unconditional non-malleable codes were known for decision trees beyond depth O(\log^2 n). Our result also yields efficient, unconditional non-malleable codes that are \exp(-n^{\Omega(1)})-secure against constant-depth circuits of \exp(n^{\Omega(1)})-size. Prior work of Chattopadhyay and Li (STOC 2017) and Ball et al. (FOCS 2018) only provide protection against \exp(O(\log^2n))-size circuits with \exp(-O(\log^2n))-security. We achieve our result through simple non-malleable reductions of decision tree tampering to split-state tampering. As an intermediary, we give a simple and generic reduction of leakage-resilient split-state tampering to split-state tampering with improved parameters. Prior work of Aggarwal et al. (TCC 2015) only provides a reduction to split-state non-malleable codes with decoders that exhibit particular properties.
ePrint: https://eprint.iacr.org/2019/379
Talk: https://www.youtube.com/watch?v=z8DHOG5onew
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 .