Paper 2025/2205

Selective ML-Guided Beam Search for Differential-Trail Discovery in GIFT-64 and PRESENT-64

Abstract

Beam search is practical for differential-trail exploration, but its cost grows quickly with the number of reachable intermediate differences. We test whether a lightweight tail-cost estimate can reduce deterministic bounded beam-search work without taking control of the search. At each horizon, a regressor predicts a residual tail cost from an active-nibble heuristic using the current difference and target endpoint. The learned signal is applied after classical selection. With four or two rounds remaining, the frozen policy protects the best $25\%$ of the classical frontier, removes at most $30\%$ of accepted states, and abstains when fewer than five states can be pruned. We develop the method on a state-grouped GIFT-64 corpus and evaluate it on $D=8$ and $D=12$ holdouts and a $D=16$ stress test. It preserves target recovery and the best classical cost on all $48$ holdout cases and all $18$ stress cases. Aggregate node reductions are $6.832\%$, $0.099\%$, and $0.040\%$ at $D=8$, $D=12$, and $D=16$, respectively. In a frozen-policy replication on PRESENT-64, retraining only the model weights preserves all $18$ $D=12$ cases with a $3.881\%$ aggregate node reduction, but one of the $18$ $D=8$ targets is missed. Learned guidance can therefore serve as a limited auxiliary signal, but its benefit is depth dependent and empirical preservation does not automatically transfer across ciphers. All comparisons are relative to the bounded classical baseline; no claim is made about globally optimal trails.