Fourier Analysis of Neural Distinguishers

Recent studies have consistently demonstrated the significant potential of deep learning for distinguishing attacks in cryptanalysis. A considerable body of research has focused on progressively improving the accuracy of these methods across various block ciphers. However, to date, there is still little theoretical understanding of why these approaches succeed. Furthermore, a notable deficiency lies in their interpretability; specifically, researchers are unable to discern the features learned by the machine learning algorithms in a human-understandable form. To a certain extent, this limitation impedes further research into the security of block ciphers and extension attacks. Motivated by this gap, we propose a method based on the Goldreich- Levin algorithm to analyze and interpret what black-box distinguishers learn. With this approach, we reinterpret some established advanced neural distinguishers in terms of Fourier representation. Specifically, it is able to resolve the previous neural distinguisher in several Fourier terms. Notably, we identify a new distinguisher technique from neural networks, which can be considered as a generalization of the Differential-Linear (DL) distinguishers. Moreover, we demonstrate that the neural network not only learned the optimal DL distinguishers found using the existing MILP/MIQCP model, but also discovered even superior ones. Finally, we discuss how to determine the weights of Fourier representation using a statistical method.