## CryptoDB

### Paper: Non-malleable Codes for Decision Trees

Authors: Marshall Ball Siyao Guo Daniel Wichs DOI: 10.1007/978-3-030-26948-7_15 Search ePrint Search Google 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^{\varOmega (1)})$ -secure against constant-depth circuits of $\exp (n^{\varOmega (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.
##### BibTeX
@article{crypto-2019-29868,
title={Non-malleable Codes for Decision Trees},
booktitle={Advances in Cryptology – CRYPTO 2019},
series={Lecture Notes in Computer Science},
publisher={Springer},
volume={11692},
pages={413-434},
doi={10.1007/978-3-030-26948-7_15},
author={Marshall Ball and Siyao Guo and Daniel Wichs},
year=2019
}