Analysis of an AI based code distinguisher

A new analysis of DeepDistinguisher, a transformer-like machine-learning distinguisher that separates Goppa codes from random linear codes, found the model partly relies on a low-weight-row artifact present in its training instances, but retains significant accuracy after that artifact is removed. The researchers report that DeepDistinguisher's predictions are highly correlated with a pairwise XOR rule between rows of the generator matrix, especially for high-rate codes, and that the neural distinguisher loses most of its predictive power on random matrices satisfying both the minimum distance and XOR constraints. The findings suggest transformer-based architectures exploit general combinatorial properties of a code rather than a hidden underlying algebraic structure.

Recently, DeepDistinguisher demonstrated the capability of transformer-like architectures to accurately distinguish Goppa codes from linear codes randomly generated, outperforming traditional distinguishers in certain settings. The purpose of our research is to examine the working mechanism of the mentioned machine learning algorithm. In particular, we explore the performance of the distinguisher using saliency maps and attention visualization techniques. We first identify a low-weight-row artifact present in the random instances used during training and show that the model partially relies on this feature. After removing this artifact, the distinguisher still achieves significant accuracy, suggesting the use of more structural properties. Inspired by the constraints induced by the minimum distance of Goppa codes, we proposed a rule based on pairwise XOR operation between the rows of the generator matrix. Our experiments have shown that the predictions made by DeepDistinguisher and XOR-based rule are highly correlated especially for high-rate codes. Furthermore, when evaluated on random matrices satisfying both the minimum distance and XOR constraints, the neural distinguisher loses most of its predictive power. This suggests that transformer-based architectures exploit general combinatorial properties of a code rather than some hidden underlying algebraic structure.