Key-Equitable Multi-Round Neural Distinguishers on a Data Budget

Neural differential cryptanalysis replaces the cryptanalyst's hand-derived statistical test with a small classifier that learns to tell ciphertext pairs (produced by encrypting two plaintexts that differ in a fixed way) from random pairs. It has produced real breaks of round-reduced Speck and Simon, but it carries two problems that the field treats as unavoidable. First, it is data-hungry: the standard benchmark trains on ten million pairs, while in a realistic attack the adversary cannot force a target to encrypt petabytes of chosen input — data, not compute, is the bottleneck. Second, it is only average-case correct: the systematization of five years of this line of work reports that these models routinely overfit the particular random keys seen during training and fail quietly on other parts of the key space SoK: 5 Years of Neural Differential Cryptanalysis. For an attacker who does not know the key in advance, a distinguisher that works on most keys but not all is a much weaker tool than its headline accuracy suggests.

This proposal argues that both problems share one root cause: current training optimizes a single objective (accuracy at one round count, averaged over random keys) through sequential, hand-staged fine-tuning. We instead train one network, simultaneously, on all reduced-round versions of a cipher as conflicting objectives, under an explicit worst-key-group constraint, and we evaluate the result as a Pareto frontier over distinguishing margin, key equity, data budget, and model size. The hypothesis is that the strong statistical signal at low rounds — currently thrown away or forgotten as training climbs the rounds — can be kept alive and used as scaffolding for the faint signal at high rounds, while multi-round supervision extracts far more information per training pair, exactly the regime where multi-task learning is known to help most Optimal criterion for feature learning of two-layer linear neural network in high dimensional interpolation regime.

Core Claim

Three connected claims. First, treating round counts as simultaneous conflicting objectives with preference-conditioned training (rather than the incumbent curriculum that fine-tunes from round $r$ to $r+1$ Improving Differential-Neural Cryptanalysis) should push the "round wall" further out and sharply cut the training-data budget, because every ciphertext pair encrypted to round $R$ supplies supervision for all rounds up to $R$. Second, a worst-key-group accuracy constraint — the accuracy-fairness lens re-pointed from demographic subgroups to subspaces of the master key — converts an average-case distinguisher into one with a per-key margin guarantee, which is what an attacker actually needs. Third, the attack-quality trade-off between margin, data, model size, and key equity should be reported as an explicit frontier, replacing the ad-hoc post-hoc knowledge distillation used to shrink models in prior work Improving Differential-Neural Cryptanalysis.

Research Program

The architecture reuses what is known to work and changes only the training problem. A single shared encoder built from the multi-scale convolutional blocks of Improving Differential-Neural Cryptanalysis feeds one classification head per round count $r$ in a set $\mathcal{R}$ (for Speck32/64, roughly rounds 4 through 10). Two additions define the method. The round-$r$ head's output gates the round-$(r{+}1)$ head, so the strong low-round decision scaffolds the weak high-round one — the same pattern by which an acoustic onset detector gates framewise pitch predictions in polyphonic transcription Onsets and Frames: Dual-Objective Piano Transcription, and consistent with the broader finding that low-level and high-level supervision reinforce each other in shared networks UberNet. And the network is conditioned on a preference vector $w$ over rounds, so one set of weights traces the whole frontier at test time, in the spirit of single-network Pareto navigation Policy Manifold Gradient Algorithm (PMGA).

Training replaces the weighted-sum-of-losses habit with a Chebyshev-style aggregation, because the round losses differ by orders of magnitude (roughly 0.99 accuracy at 5 rounds versus 0.51 at 9 rounds on DES-style suites Improving the Accuracy of Differential-Neural Distinguisher for DES, Chaskey, and PRESENT), and linear scalarization both drowns small objectives and provably misses non-convex parts of fronts Cheng et al.:

$$\mathcal{L}(\theta; w) \;=\; \max_{r \in \mathcal{R}}\; w_r \,\frac{L_r(\theta)}{\bar{L}_r}$$

Here $L_r(\theta)$ is the cross-entropy of the round-$r$ head, $\bar{L}_r$ a running normalization constant that equalizes loss scales across rounds, and $w$ a simplex-valued preference vector swept during training. This form is adapted from the Weighted-Chebyshev penalty with single-loop updates and finite-time convergence guarantees A Tale of Two Problems: Multi-Task Bilevel Learning Meets Equality Constrained Multi-Objective Optimization, combined with the direction-based objective alignment that stopped large-magnitude objectives from washing out small ones in preference-conditioned learning PD-MORL: Preference-Driven Multi-Objective Reinforcement Learning Algorithm. On top of this sits the key-equity constraint: partition the key space into groups $\mathcal{G}$ (by master-key Hamming-weight classes, by subkey nibble classes, and by classical weak-key-style partitions in the spirit of the Pilsung study Row, Row, Row Your Boat: How to Not Find Weak Keys in Pilsung), and require

$$\min_{g \in \mathcal{G}}\; \min_{r \in \mathcal{R}_{\text{target}}}\; A_{r,g}(\theta) \;\ge\; \tau$$

where $A_{r,g}$ is the round-$r$ distinguishing accuracy under keys drawn from group $g$ and $\tau$ is a floor chosen per round. The floor is enforced end-to-end during training rather than patched afterwards, following the evidence that declarative constraint layers satisfy fairness definitions at a 100% rate where penalty and post-hoc projection methods frequently fail, and that end-to-end training beats post-hoc projection by 1.46% mean AUC on constrained problems Differentiable Optimization Layers for Guaranteed Fairness in Deep Learning. The "no harm" criterion from Achieving Fairness Without Harm via Selective Demographic Experts — constraint satisfaction must never push any group below the unconstrained baseline — transfers directly: raising the worst key group must not sink the average.

Evaluation adopts the Pareto-curve methodology of FairLib: A Unified Framework for Assessing and Improving Fairness, including its Distance-To-Optimal scalar (Euclidean distance in objective space to the utopia point of perfect margin at all rounds and zero key gap), repurposed for cryptanalysis. FairLib's own finding — that hyperparameter tuning often moves the frontier more than switching methods — sets our experimental discipline: every comparison gets an equal tuning budget. One analogy motivates the key-equity study design rather than its method: the "fairness lottery," where identical-accuracy classifiers hide large variance across subgroups depending only on random seed On the Impact of Random Seeds on the Fairness of Clinical Classifiers; we expect the same pathology in distinguishers and will measure it across seeds.

Scope is deliberately bounded. We target 32- and 64-bit block ciphers, not the 128-bit state-size barrier, and we claim distinguishers and reduced-round key recovery, not learning a key from ciphertext pairs, which is provably hard under standard assumptions on AES Hardness of Learning AES Key (Student Abstract).

Proposed Experiments

The primary study uses the Speck32/64 distinguisher suite with fixed input difference $0x0040/0000$ and the standard $10^7$/$10^6$ train/test sizes Improving Differential-Neural Cryptanalysis, plus deliberately starved budgets of $10^4$–$10^5$ pairs to trace data-complexity curves. Metrics are per-round accuracy, the minimum over target rounds (forgetting check), worst-key-group accuracy and the max-min key gap across all partitions, and — for full attacks — data complexity of key recovery. Success against the incumbent means any of: a distinguisher at 10 or more rounds of Speck32/64 at usable accuracy (incumbent: 9 rounds); 13-round key recovery with data complexity below the reported $2^{27}$; or matching incumbent 9-round performance with at most 1% of the training pairs. A second study repeats this on Simon32/64 (incumbent: 12-round distinguisher, 17-round recovery Improving Differential-Neural Cryptanalysis) and on the DES, Chaskey, and PRESENT suites, where the incumbent numbers to beat are 0.5114 at 7-round DES, 0.5181 at 5-round Chaskey, and 0.5416 at 8-round PRESENT Improving the Accuracy of Differential-Neural Distinguisher for DES, Chaskey, and PRESENT. A third study isolates key equity: measure the key-fairness lottery of the incumbent under seed variation, then test whether the constrained training closes the worst-group gap without violating the no-harm criterion, mirroring the Harvard-GF glaucoma result where max-min expert training raised average AUC from 80.54 to 81.2 while shrinking the group gap to 1.81 Achieving Fairness Without Harm via Selective Demographic Experts. A secondary cross-cipher experiment asks whether a shared encoder trained jointly on Speck and Simon — both addition-rotation-XOR designs — transfers, which no prior work has tested (all models are trained per-cipher SoK: 5 Years of Neural Differential Cryptanalysis); this is exploratory and not a success condition. Finally, model-size versus accuracy is mapped as a frontier rather than one distilled point, against the incumbent's single reported distillation of 9.5M parameters to 33K at accuracy 0.8128 falling to 0.8053 Improving Differential-Neural Cryptanalysis.

Baselines

The do-nothing reference is a single-round, single-objective distinguisher trained by standard empirical risk minimization on uniformly random keys with the incumbent architecture and full data — the exact recipe of Improving Differential-Neural Cryptanalysis — evaluated not only on aggregate accuracy but on our worst-key-group metrics; its random-guess floor is 0.50, and its key-gap measurement establishes how large the equity problem actually is, in the spirit of the fairness-lottery finding On the Impact of Random Seeds on the Fairness of Clinical Classifiers. The strongest competitor is the staged-curriculum Inception distinguisher of Improving Differential-Neural Cryptanalysis, the incumbent state of the art on Speck32/64 with its 9-round distinguisher, 14-round key recovery, and 13-round data complexity of $2^{27}$; we will re-run it ourselves on identical data generation, the same architecture family, the same GPU hours, and the same hyperparameter search budget, and additionally evaluate its models on all round counts simultaneously to expose forgetting that its per-round evaluation hides. Beating it means the numbers above plus simultaneous multi-round retention. The closest methodological competitor is plain weighted-sum multi-round training (one shared encoder, per-round heads, summed losses with tuned weights) — the simplest version of our own idea — run with the same budget, since it tests whether Chebyshev aggregation and preference conditioning add anything over averaging. The multi-pair Inception distinguishers of Improving the Accuracy of Differential-Neural Distinguisher for DES, Chaskey, and PRESENT serve as the incumbent on the second cipher suite. Finally, three ablations isolate the ingredients: preference conditioning removed (uniform $w$), the worst-key constraint removed, and the round-gating scaffold removed; if the full method wins while these lose, the win is attributable to the specific mechanisms rather than to generic multi-task capacity.

Why not just…?

Why not just sum the per-round losses with fixed weights? This is the most serious alternative, and we treat it as a first-class baseline rather than an argument. The evidence against it is that objectives with different magnitudes drown each other out under weighted sums, while direction-based alignment preserved balance and expanded hypervolume by 25% in preference-conditioned learning PD-MORL: Preference-Driven Multi-Objective Reinforcement Learning Algorithm, and linear scalarization provably cannot reach non-convex frontier regions Cheng et al. — with round accuracies spanning 0.5 to 0.99, the low-round losses will dominate any fixed weighting unless normalized, which is precisely what our Chebyshev form does. But the honest position is that the decisive experiment, not the theory, settles it: if tuned weighted sums trace the same frontier under equal budget, we will report that the contribution is the key-equity constraint and the frontier evaluation, not the aggregation scheme.

Why not just keep the incumbent curriculum training? Because it is one model per round with no retention guarantee, no worst-key property, and a ten-million-pair appetite; and because multi-output supervision is provably able to expose shared structure that single-target training cannot, even if the existing proof is limited to two-layer linear networks Optimal criterion for feature learning of two-layer linear neural network in high dimensional interpolation regime. That said, we expect curriculum training to remain stronger at the full data budget, and we say so in advance: the win condition for this proposal is the low-data regime and the equity guarantee, and we will report negative results at high data budgets plainly.

Why not just pretrain an autoencoder and feed its features to the distinguisher? This exact idea was tried on the Speck distinguisher and failed to improve anything, despite near-perfect reconstruction, because unsupervised reconstruction does not preserve the non-linear bit interactions cryptanalysis needs Deep Neural Networks Aiding Cryptalysis: A Case Study of the Speck Distinguisher. Our supervision is discriminative and round-labeled, not reconstructive, which is the relevant difference; we will still run one autoencoder variant to confirm the failure transfers to our setting.

Why not just calibrate per key group after training? Post-hoc fixes fail on two counts. Empirically, post-hoc projection degrades accuracy because the representation was never trained to respect the constraint, costing 1.46% mean AUC relative to end-to-end constrained training in the loan-default experiments Differentiable Optimization Layers for Guaranteed Fairness in Deep Learning, and post-processing routinely violates no-harm on subgroups Achieving Fairness Without Harm via Selective Demographic Experts. Structurally it is worse here: group-expert methods need the group label at inference time, and an attacker by definition does not know the key, so no per-key routing or thresholding is available at test time.

Why not just collect more training pairs? Because the entire premise of low-data cryptanalysis is that data, not compute, is the operationally scarce resource — an attacker can rent compute but cannot make a target encrypt chosen petabytes — so the meaningful axis is accuracy per pair, which is exactly what our data-complexity curves measure.

Decisive Checks

The proposal stands or falls on three comparisons, all at matched compute and tuning budgets. First, the frontier comparison on Speck32/64: simultaneous multi-objective training versus the incumbent curriculum at $10^7$ and at $10^5$ pairs, judged on max round reached, minimum-over-rounds retention, and data needed to match the incumbent's reported 0.8128-class performance. Second, the equity test: whether the worst-key-group floor is met at a 100% rate with no average-accuracy harm, or whether the constraint proves too expensive, in which case we report the measured price as the result. Third, the scalarization test: whether Chebyshev aggregation and preference conditioning beat tuned weighted sums on the traced frontier. Following the costly lesson of the Pilsung weak-key search, where 10,000 CPU hours were spent on a hypothesis falsifiable in minutes on reduced-round models Row, Row, Row Your Boat: How to Not Find Weak Keys in Pilsung, every mechanism is verified on round-reduced versions before any full-scale run.