TY - GEN
T1 - Non-malleable Codes for Decision Trees
AU - Ball, Marshall
AU - Guo, Siyao
AU - Wichs, Daniel
N1 - 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 -