Paper 2019/379

Non-Malleable Codes for Decision Trees

Marshall Ball, Siyao Guo, and Daniel Wichs


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.

Available format(s)
Publication info
Preprint. MINOR revision.
non-malleable codesdecision treessmall-depth circuitsAC0leakage-resilienceleakage-resilient split-state
Contact author(s)
marshall @ cs columbia edu
2019-04-16: received
Short URL
Creative Commons Attribution


      author = {Marshall Ball and Siyao Guo and Daniel Wichs},
      title = {Non-Malleable Codes for Decision Trees},
      howpublished = {Cryptology ePrint Archive, Paper 2019/379},
      year = {2019},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.