CryptoDB
Non-malleable Codes for Decision Trees
| Authors: | |
|---|---|
| Download: |
|
| 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^{\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. |
Video from CRYPTO 2019
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
}