Yufei Yuan, Wenling Wu, Lei Zhang, Ruichen Wu

Fourier Analysis of Neural Distinguishers

Introduction

Fourier analysis of neural distinguishers. Explores interpretability of neural network cryptanalysis via Fourier analysis. Reinterprets existing distinguishers and uncovers new, superior Differential-Linear techniques.

Abstract

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.

Review

This paper addresses a crucial and timely challenge in the application of deep learning to cryptanalysis: the lack of theoretical understanding and interpretability behind the success of neural network-based distinguishers. While deep learning has repeatedly demonstrated its effectiveness in identifying cryptographic attacks, the "black-box" nature of these models has hindered insights into the specific features they learn, thereby limiting further advancements in block cipher security analysis and extension attacks. The authors are motivated by this significant gap, proposing an innovative approach to unravel the hidden mechanisms of these powerful yet opaque neural distinguishers. The core contribution of this work lies in introducing a method, inspired by the Goldreich-Levin algorithm, to analyze and interpret what these black-box distinguishers learn. By reinterpreting established neural distinguishers through the lens of Fourier representation, the authors provide unprecedented clarity into their operation. Notably, they successfully resolve previous neural distinguishers into several distinct Fourier terms, leading to a remarkable discovery: a new distinguisher technique derived directly from neural networks, which is presented as a generalization of Differential-Linear (DL) distinguishers. Furthermore, the paper robustly demonstrates that neural networks not only replicate the optimal DL distinguishers found by existing MILP/MIQCP models but can even discover superior ones, showcasing the potential for AI to surpass traditional cryptanalytic search methods. The work concludes by outlining a statistical method for determining the weights of these Fourier representations, adding a practical dimension to their theoretical insights. This research marks a significant step forward in bridging the interpretability gap between deep learning and cryptanalysis. By providing a human-understandable framework for analyzing neural distinguishers through Fourier analysis, the paper offers invaluable theoretical insights into *why* these methods succeed and *what* features they exploit. The identification of a new, generalized DL distinguisher and the demonstration of neural networks discovering superior distinguishers underscore the profound potential of this interpretive approach to drive future cryptographic research. Such insights are critical for advancing the security evaluation of block ciphers, informing the design of new ciphers, and guiding the development of more effective extension attacks, ultimately fostering a deeper understanding of cryptographic security.

Full Text

Comments

You need to be logged in to post a comment.