Paper 2025/2205

ML-Guided Beam Search for Differential Trail Discovery in SPN Ciphers: A Case Study on GIFT-64

Abstract

This paper introduces an ML-guided scoring heuristic for differential trail beam search in substitution--permutation network (SPN) ciphers. Instead of replacing classical search procedures or relying on heavy learning architectures, we take a residual-learning approach: a gradient boosting regressor is trained to predict the error of a simple nibble-count lower bound on the remaining trail cost. At search time, the predicted residual is fused multiplicatively into the beam scoring function, using per-layer robust normalization and a conservative floor to preserve safety. This design keeps the underlying search structure such as beam width, pruning rules, and lower-bound guarantees unchanged, while aiming to improve the ranking of partial trails. We instantiate the method on the 64-bit block cipher GIFT-64 under the classical Markov differential model. Our implementation reproduces state of the art differential trails with identical weights and round by round differences, and achieves 10--40\% reductions in the number of expanded nodes in moderate-depth searches, with runtime trade-offs analyzed across different model horizons. The results suggest a practical, non-invasive paradigm for enhancing classical cryptanalytic search with learned corrections, without redesigning existing algorithms or probability models, and are in principle applicable to a range of SPN designs.