Almost pairwise independence and resilience to deep learning attacks
Authors
Rustem Takhanov
Rustem Takhanov
Nazarbayev University, Astana, Kazakhstan
rustem dot takhanov at nu dot edu dot kz
rustem dot takhanov at nu dot edu dot kz
Keywords:
pairwise independence
decorrelation theory
Learning With Errors (LWE)
Substitution-Permutations Networks (SPN)
barren plateau phenomenon
information content of the gradient
hardness of learning
Abstract
Almost pairwise independence (API) is a quantitative property of a class of functions that is desirable in many cryptographic applications. This property is satisfied by Learning with errors (LWE)-mappings and by special Substitution-Permutation Networks (SPN). API block ciphers are known to be resilient to differential and linear cryptanalysis attacks. Recently, security of protocols against neural network-based attacks became a major trend in cryptographic studies. Therefore, it is relevant to study the hardness of learning a target function from an API class of functions by gradient-based methods.
We propose a theoretical analysis based on the study of the variance of the gradient of a general machine learning objective with respect to a random choice of target function from a class. We prove an upper bound and verify that, indeed, such a variance is extremely small for API classes of functions. This implies the resilience of actual LWE-based primitives against deep learning attacks, and to some extent, the security of SPNs. The hardness of learning reveals itself in the form of the barren plateau phenomenon during the training process, or in other words, in a low information content of the gradient about the target function. Yet, we emphasize that our bounds hold for the case of a regular parameterization of a neural network and the gradient may become informative if a class is mildly pairwise independent and a parameterization is non-regular. We demonstrate our theory in experiments on the learnability of LWE mappings.
References
[AGM03]
Noga Alon, Oded Goldreich, and Yishay Mansour. Almost k-wise independence versus k-wise independence. Information Processing Letters, 88(3):107-110, 2003. DOI: https://doi.org/10.1016/S0020-0190(03)00359-4
[AKJM21]
Ezat Ahmadzadeh, Hyunil Kim, Ongee Jeong, and Inkyu Moon. A Novel Dynamic Attack on Classical Ciphers Using an Attention-Based LSTM Encoder-Decoder Model. IEEE Access, 9:60960-60970, 2021. DOI: 10.1109/ACCESS.2021.3074268
[Ala12]
Mohammed M. Alani. Neuro-Cryptanalysis of DES and Triple-DES. In Tingwen Huang, Zhigang Zeng, Chuandong Li, and Chi Sing Leung, editors, Neural Information Processing, pages 637–646, Berlin, Heidelberg. 2012. Springer Berlin Heidelberg. DOI: 10.1007/978-3-642-34500-5_75
[BBV15]
Céline Blondeau, Aslı Bay, and Serge Vaudenay. Protecting Against Multidimensional Linear and Truncated Differential Cryptanalysis by Decorrelation. In Gregor Leander, editor, Fast Software Encryption, pages 73–91, Berlin, Heidelberg. 2015. Springer Berlin Heidelberg. DOI: 10.1007/978-3-662-48116-5_4
[BDK+18]
Joppe Bos, Leo Ducas, Eike Kiltz, T Lepoint, Vadim Lyubashevsky, John M. Schanck, Peter Schwabe, Gregor Seiler, and Damien Stehle. CRYSTALS - Kyber: A CCA-Secure Module-Lattice-Based KEM. In 2018 IEEE European Symposium on Security and Privacy (EuroS&P), pages 353-367. 2018. DOI: 10.1109/EuroSP.2018.00032
[BFJ+94]
Avrim Blum, Merrick L. Furst, Jeffrey C. Jackson, Michael J. Kearns, Yishay Mansour, and Steven Rudich. Weakly learning DNF and characterizing statistical query learning using Fourier analysis. In Frank Thomson Leighton and Michael T. Goodrich, editors, Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, 23-25 May 1994, Montréal, Québec, Canada, pages 253–262. 1994. ACM. DOI: 10.1145/195058.195147
[BHK+99]
J. Black, S. Halevi, H. Krawczyk, T. Krovetz, and P. Rogaway. UMAC: Fast and Secure Message Authentication. In Michael Wiener, editor, Advances in Cryptology — CRYPTO' 99, pages 216–233, Berlin, Heidelberg. 1999. Springer Berlin Heidelberg. DOI: 10.1007/3-540-48405-1_14
[BK20]
Seunggeun Baek and Kwangjo Kim. Recent Advances of Neural Attacks against Block Ciphers. In Symposium on Cryptography and Information Security. 2020.
[BLP+13]
Zvika Brakerski, Adeline Langlois, Chris Peikert, Oded Regev, and Damien Stehlé. Classical Hardness of Learning with Errors. In Proceedings of the Forty-Fifth Annual ACM Symposium on Theory of Computing, pages 575–584, New York, NY, USA. 2013. Association for Computing Machinery. DOI: 10.1145/2488608.2488680
[CKLS18]
Jung Hee Cheon, Duhyeong Kim, Joohee Lee, and Yongsoo Song. Lizard: Cut Off the Tail! A Practical Post-quantum Public-Key Encryption from LWE and LWR. In Dario Catalano and Roberto De Prisco, editors, Security and Cryptography for Networks, pages 160–177, Cham. 2018. Springer International Publishing. DOI: 10.1007/978-3-319-98113-0_9
[CMLea22]
Lily Chen, Dustin Moody, Yi-Kai Liu, and et al. Announcing Four Candidates to be Standardized, Plus Fourth Round Candidates. Accessed: 2023-12-12. https://csrc.nist.gov/News/2022/pqc-candidates-to-be-standardized-and-round-4. 2022.
[CN11]
Yuanmi Chen and Phong Q. Nguyen. BKZ 2.0: Better Lattice Security Estimates. In Dong Hoon Lee and Xiaoyun Wang, editors, Advances in Cryptology – ASIACRYPT 2011, pages 1–20, Berlin, Heidelberg. 2011. Springer Berlin Heidelberg. DOI: 10.1007/978-3-642-25385-0_1
[CW79]
J.Lawrence Carter and Mark N. Wegman. Universal classes of hash functions. Journal of Computer and System Sciences, 18(2):143-154, 1979. DOI: https://doi.org/10.1016/0022-0000(79)90044-8
[CY21]
Yi Chen and Hongbo Yu. Bridging Machine Learning and Cryptanalysis via EDLCT. https://eprint.iacr.org/2021/705. Cryptology ePrint Archive, Paper 2021/705. 2021.
[DNGW23]
Elena Dubrova, Kalle Ngo, Joel Gärtner, and Ruize Wang. Breaking a Fifth-Order Masked Implementation of CRYSTALS-Kyber by Copy-Paste. In Proceedings of the 10th ACM Asia Public-Key Cryptography Workshop, pages 10–20, New York, NY, USA. 2023. Association for Computing Machinery. DOI: 10.1145/3591866.3593072
[Dra04]
Sever S Dragomir. On the Boas-Bellman inequality in inner product spaces. Bulletin of the Australian Mathematical Society, 69(2):217–225, 2004. DOI: 10.1017/S0004972700035954
[FGV17]
Vitaly Feldman, Cristóbal Guzmán, and Santosh S. Vempala. Statistical Query Algorithms for Mean Vector Estimation and Stochastic Convex Optimization. In Philip N. Klein, editor, Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19, pages 1265–1277. 2017. SIAM. DOI: 10.1137/1.9781611974782.82
[FPY15]
Hilary Finucane, Ron Peled, and Yariv Yaari. A recursive construction of t-wise uniform permutations. Random Structures & Algorithms, 46(3):531-540, 2015. DOI: https://doi.org/10.1002/rsa.20509
[HKM18]
Gottfried Herold, Elena Kirshanova, and Alexander May. On the asymptotic complexity of solving LWE. Designs, Codes and Cryptography, 86(1):55-83, January 2018. DOI: 10.1007/s10623-016-0326-0
[HMMR05]
Shlomo Hoory, Avner Magen, Steven Myers, and Charles Rackoff. Simple permutations mix well. Theoretical Computer Science, 348(2):251-261, 2005. Automata, Languages and Programming: Algorithms and Complexity (ICALP-A 2004) DOI: https://doi.org/10.1016/j.tcs.2005.09.016
[ITYY21]
Mohamed Fadl Idris, Je Sen Teh, Jasy Liew Suet Yan, and Wei-Zhu Yeoh. A Deep Learning Approach for Active S-Box Prediction of Lightweight Generalized Feistel Block Ciphers. IEEE Access, 9:104205-104216, 2021. DOI: 10.1109/ACCESS.2021.3099802
[JEP+21]
John Jumper, Richard Evans, Alexander Pritzel, Tim Green, Michael Figurnov, Olaf Ronneberger, Kathryn Tunyasuvunakool, Russ Bates, Augustin Žídek, Anna Potapenko, Alex Bridgland, Clemens Meyer, Simon A A Kohl, Andrew J Ballard, Andrew Cowie, Bernardino Romera-Paredes, Stanislav Nikolov, Rishub Jain, Jonas Adler, Trevor Back, Stig Petersen, David Reiman, Ellen Clancy, Michal Zielinski, Martin Steinegger, Michalina Pacholska, Tamas Berghammer, Sebastian Bodenstein, David Silver, Oriol Vinyals, Andrew W Senior, Koray Kavukcuoglu, Pushmeet Kohli, and Demis Hassabis. Highly accurate protein structure prediction with AlphaFold. Nature, 596(7873):583–589, July 2021. DOI: 10.1038/s41586-021-03819-2
[Kea93]
Michael J. Kearns. Efficient noise-tolerant learning from statistical queries. In S. Rao Kosaraju, David S. Johnson, and Alok Aggarwal, editors, Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, May 16-18, 1993, San Diego, CA, USA, pages 392–401. 1993. ACM. DOI: 10.1145/167088.167200
[KEI+22]
Hayato Kimura, Keita Emura, Takanori Isobe, Ryoma Ito, Kazuto Ogawa, and Toshihiro Ohigashi. Output Prediction Attacks on Block Ciphers Using Deep Learning. In Applied Cryptography and Network Security Workshops, pages 248–276, Cham. 2022. Springer International Publishing. DOI: 10.1007/978-3-031-16815-4_15
[KNR09]
Eyal Kaplan, Moni Naor, and Omer Reingold. Derandomized Constructions of k-Wise (Almost) Independent Permutations. Algorithmica, 55(1):113-133, September 2009. DOI: 10.1007/s00453-008-9267-y
[KR06]
Ted Krovetz and Phillip Rogaway. Variationally universal hashing. Information Processing Letters, 100(1):36-39, 2006. DOI: https://doi.org/10.1016/j.ipl.2005.11.026
[KV94]
Michael Kearns and Leslie Valiant. Cryptographic limitations on learning Boolean formulae and finite automata. J. ACM, 41(1):67–95, January 1994. DOI: 10.1145/174644.174647
[KvHW19]
Wouter Kool, Herke van Hoof, and Max Welling. Attention, Learn to Solve Routing Problems!. In International Conference on Learning Representations. 2019.
[LCK18]
Zhuwen Li, Qifeng Chen, and Vladlen Koltun. Combinatorial optimization with graph convolutional networks and guided tree search. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, pages 537–546, Red Hook, NY, USA. 2018. Curran Associates Inc.. DOI: 10.5555/3326943.3326993
[LSW+23]
Cathy Yuanchen Li, Jana Sotáková, Emily Wenger, Mohamed Malhou, Evrard Garcelon, François Charton, and Kristin Lauter. SalsaPicante: A Machine Learning Attack on LWE with Binary Secrets. In Proceedings of the 2023 ACM SIGSAC Conference on Computer and Communications Security, pages 2606–2620, New York, NY, USA. 2023. Association for Computing Machinery. DOI: 10.1145/3576915.3623076
[LTV21]
Tianren Liu, Stefano Tessaro, and Vinod Vaikuntanathan. The t-wise Independence of Substitution-Permutation Networks. In Tal Malkin and Chris Peikert, editors, Advances in Cryptology – CRYPTO 2021, pages 454–483, Cham. 2021. Springer International Publishing. DOI: 10.1007/978-3-030-84259-8_16
[LW06]
Michael Luby and Avi Wigderson. Pairwise Independence and Derandomization. Foundations and Trends® in Theoretical Computer Science, 1(4):237-301, 2006. DOI: 10.1561/0400000009
[LWAZ+23]
Cathy Li, Emily Wenger, Zeyuan Allen-Zhu, Francois Charton, and Kristin E. Lauter. SALSA VERDE: a machine learning attack on LWE with sparse small secrets. In A. Oh, T. Naumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine, editors, Advances in Neural Information Processing Systems, volume 36, pages 53343–53361. 2023. Curran Associates, Inc.. DOI: 10.5555/3666122.3668444
[LYDD22]
Zidu Liu, Li-Wei Yu, L.-M. Duan, and Dong-Ling Deng. Presence and Absence of Barren Plateaus in Tensor-Network Based Machine Learning. Phys. Rev. Lett., 129:270501, December 2022. DOI: 10.1103/PhysRevLett.129.270501
[MBS+18]
Jarrod R. McClean, Sergio Boixo, Vadim N. Smelyanskiy, Ryan Babbush, and Hartmut Neven. Barren plateaus in quantum neural network training landscapes. Nature Communications, 9(1):4812, November 2018. DOI: 10.1038/s41467-018-07090-4
[NDJ23]
Kalle Ngo, Elena Dubrova, and Thomas Johansson. A side-channel attack on a masked and shuffled software implementation of Saber. Journal of Cryptographic Engineering, 13(4):443-460, November 2023. DOI: 10.1007/s13389-023-00315-3
[Ope22]
OpenAI. Introducing ChatGPT. Accessed: 2023-05-30. https://openai.com/blog/chatgpt. 2022.
[PSMF20]
David Pfau, James S. Spencer, Alexander G. D. G. Matthews, and W. M. C. Foulkes. Ab initio solution of the many-electron Schrödinger equation with deep neural networks. Phys. Rev. Res., 2:033429, September 2020. DOI: 10.1103/PhysRevResearch.2.033429
[RBA+19]
Nasim Rahaman, Aristide Baratin, Devansh Arpit, Felix Draxler, Min Lin, Fred Hamprecht, Yoshua Bengio, and Aaron Courville. On the Spectral Bias of Neural Networks. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 5301–5310. 09–15 Jun 2019. PMLR.
[Reg05]
Oded Regev. On Lattices, Learning with Errors, Random Linear Codes, and Cryptography. In Proceedings of the Thirty-Seventh Annual ACM Symposium on Theory of Computing, pages 84–93, New York, NY, USA. 2005. Association for Computing Machinery. DOI: 10.1145/1060590.1060603
[Sha18]
Ohad Shamir. Distribution-Specific Hardness of Learning Neural Networks. J. Mach. Learn. Res., 19:32:1–32:29, 2018. DOI: 10.5555/3291125.3291157
[SHM+16]
David Silver, Aja Huang, Chris J Maddison, Arthur Guez, Laurent Sifre, George van den Driessche, Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam, Marc Lanctot, Sander Dieleman, Dominik Grewe, John Nham, Nal Kalchbrenner, Ilya Sutskever, Timothy Lillicrap, Madeleine Leach, Koray Kavukcuoglu, Thore Graepel, and Demis Hassabis. Mastering the game of Go with deep neural networks and tree search. Nature, 529(7587):484–489, January 2016. DOI: 10.1038/NATURE16961
[Sho05]
Victor Shoup. A computational introduction to number theory and algebra. Cambridge University Press, USA 2005. DOI: 10.5555/1529931
[SLB+19]
Daniel Selsam, Matthew Lamm, Benedikt Bünz, Percy Liang, Leonardo de Moura, and David L. Dill. Learning a SAT Solver from Single-Bit Supervision. In International Conference on Learning Representations. 2019.
[SSS17]
Shai Shalev-Shwartz, Ohad Shamir, and Shaked Shammah. Failures of Gradient-Based Deep Learning. In Doina Precup and Yee Whye Teh, editors, Proceedings of the 34th International Conference on Machine Learning, ICML 2017, Sydney, NSW, Australia, 6-11 August 2017, volume 70 of Proceedings of Machine Learning Research, pages 3067–3075. 2017. PMLR. DOI: 10.5555/3305890.3305998
[TTJ23]
Wei Jian Teng, Je Sen Teh, and Norziana Jamil. On the security of lightweight block ciphers against neural distinguishers: Observations on LBC-IoT and SLIM. Journal of Information Security and Applications, 76:103531, 2023. DOI: https://doi.org/10.1016/j.jisa.2023.103531
[TTP+24]
Rustem Takhanov, Maxat Tezekbayev, Artur Pak, Arman Bolatov, and Zhenisbek Assylbekov. Gradient Descent Fails to Learn High-frequency Functions and Modular Arithmetic. 2024.
[Vau03]
Serge Vaudenay. Decorrelation: A Theory for Block Cipher Security. Journal of Cryptology, 16(4):249-286, September 2003. DOI: 10.1007/s00145-003-0220-6
[WC81]
Mark N. Wegman and J.Lawrence Carter. New hash functions and their use in authentication and set equality. Journal of Computer and System Sciences, 22(3):265-279, 1981. DOI: https://doi.org/10.1016/0022-0000(81)90033-7
[WCCL22]
Emily Wenger, Mingjie Chen, François Charton, and Kristin E. Lauter. SALSA: Attacking Lattice Cryptography with Transformers. In NeurIPS. 2022.
[Yan01]
Ke Yang. On Learning Correlated Boolean Functions Using Statistical Queries (Extended Abstract). In Naoki Abe, Roni Khardon, and Thomas Zeugmann, editors, Algorithmic Learning Theory, pages 59–76, Berlin, Heidelberg. 2001. Springer Berlin Heidelberg. DOI: 10.1007/3-540-45583-3_7
PDF
History
Submitted: 2024-07-08
Accepted: 2024-09-02
Published: 2024-10-07
Accepted: 2024-09-02
Published: 2024-10-07
How to cite
Rustem Takhanov, Almost pairwise independence and resilience to deep learning attacks. IACR Communications in Cryptology, vol. 1, no. 3, Oct 07, 2024, doi: 10.62056/a3ksa69p1.
License
Copyright is held by the author(s)
This work is licensed under a Creative Commons Attribution (CC BY) license.