TY - GEN
T1 - Non-malleable Codes for Decision Trees
AU - Ball, Marshall
AU - Guo, Siyao
AU - Wichs, Daniel
N1 - Funding Information:
Acknowledgements. We would like to thank Dana Dachman-Soled, Tal Malkin, and Li Yang Tan for many insightful conversations and helping to pose the initial question and its connections to small depth circuits. We would like to additionally thank Justin Holmgren and Ron Rothblum for stimulating discussions. The first author is supported by an IBM Research PhD Fellowship, NSF grant CCF1423306, and the Leona M. & Harry B. Helmsley Charitable Trust. Part of this work was completed while the author was visiting IDC Herzilya. The second author is supported by NSF grants CNS1314722 and CNS-1413964. The third author is supported by NSF grants CNS-1314722, CNS-1413964, CNS-1750795 and the Alfred P. Sloan Research Fellowship.
Publisher Copyright:
© 2019, International Association for Cryptologic Research.
PY - 2019
Y1 - 2019
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=85071768875&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85071768875&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-26948-7_15
DO - 10.1007/978-3-030-26948-7_15
M3 - Conference contribution
AN - SCOPUS:85071768875
SN - 9783030269470
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 413
EP - 434
BT - Advances in Cryptology – CRYPTO 2019 - 39th Annual International Cryptology Conference, Proceedings
A2 - Micciancio, Daniele
A2 - Boldyreva, Alexandra
PB - Springer Verlag
T2 - 39th Annual International Cryptology Conference, CRYPTO 2019
Y2 - 18 August 2019 through 22 August 2019
ER -