Post-quantum cryptosystems based on error-correcting codes get their security from a simple promise: a structured public key should be indistinguishable from a random matrix. To keep keys small, designers inject algebraic structure — cyclic symmetries, sparse parity checks, rank-metric codes — and every one of these symmetries is a potential leak. The literature now contains two very different kinds of leak detectors. One is algebraic: fold the matrix, intersect subspaces, or guess a small subspace of the error, and structured keys fall out of their random camouflage (as in the distinguishability attacks motivating MDPC-McEliece: New McEliece variants from Moderate Density Parity-Check codes and the subsupport guessing of Hybrid Subsupport Guessing: A New Hybrid Technique for the Rank Decoding Problem). The other is statistical: the "DeepDistinguisher" transformer of AI for Code-based Cryptography learns non-linear invariants from generator matrices, reaching over 98% accuracy on Goppa codes. But both kinds of detector share a crippling assumption: they are offline, batch tools. They assume a large pre-generated dataset, a fixed code family, and fixed parameters — and the DeepDistinguisher's accuracy collapses toward chance as parameters scale, with no mechanism to adapt.
This proposal treats structural cryptanalysis as what it actually is in deployment: a sequential problem. Public keys and ciphertexts arrive as a stream; the code family, its parameters, and even the implementation shortcuts (like the identical-row weak keys exposed in Cryptanalysis of Pseudorandom Error-Correcting Codes) drift over time. We build an online distinguisher that maintains a weighted dictionary of cheap algebraic invariant tests, updates the weights with every key observed, provably never does much worse than the best single test in hindsight, and pays compute only for keys that reveal a genuinely new invariant direction. The efficiency-regret literature supplies the mechanism, the cold-start literature supplies the robust warm-start across code families, and algebraic structure vulnerability is the application that gives the whole thing teeth.
Core Claim
The learner receives a stream of public keys $K_1, K_2, \dots$, each either structured (from a known code family) or uniformly random, and must predict which. It has access to a dictionary of $N$ invariant tests $f_1, \dots, f_N$ — folding/rank tests, syndrome-statistic tests, learned transformer features, and so on — each individually weak in some regime. Aggregating them by Follow-the-Regularized-Leader, the online learner guarantees cumulative regret against the best fixed test
$$R_T \;=\; \sum_{t=1}^{T} \ell(\hat y_t, y_t) \;-\; \min_{i \le N} \sum_{t=1}^{T} \ell(f_i(K_t), y_t) \;\le\; O\!\left(\sqrt{T \ln N}\right),$$
where $\ell$ is the misclassification loss and $y_t$ the true label. The claim that goes beyond textbook Hedge is a compute bound. Writing each key's dictionary responses as a vector over a finite field, the learner maintains a state matrix whose rank saturates at the invariant dimension $d_{\mathrm{inv}}$ of the underlying family (a cyclic family has small $d_{\mathrm{inv}}$; random keys do not). Keys whose response vectors lie in the already-cached row space are predicted from cached linear relations, so marginal per-key cost drops from $O(N)$ test evaluations toward prediction-only. We aim to prove this costs only a gentle regret overhead, in direct analogy to how Nearly Optimal Algorithms with Sublinear Computational Complexity for Online Kernel Regression trades its optimal $O(\sqrt{L(f)})$ or $O(\mathrm{d}_{\mathrm{eff}}(\mu) \ln T)$ regret for $O(\ln^2 T)$ computation by admitting basis points only when an Approximate Linear Dependence test fails — except here the gate is exact rank over $\mathbb{F}_q$, not a Hilbert-space projection. The cold-start ingredient is robust: when the family is unknown, prior family weights enter through the decayed-FTRL scheme of On Provably Robust Meta-Bayesian Optimization, so a misleading prior can slow us down early but, by the same proof pattern, cannot make us asymptotically worse than the cold-start learner.
This is a deliberate triple intersection. Algebraic structure vulnerability is the domain; the efficiency-regret tradeoff is the mechanism that makes an online distinguisher affordable; cold-start robustness is the constraint that makes it deployable when the family is unknown or drifting. No existing work sits at this point: AI for Code-based Cryptography is offline and batch; Oracle-efficient Hybrid Learning with Constrained Adversaries proves oracle-efficient regret for constrained adversaries but assumes an ERM oracle that would itself be a cryptanalytic break; and the kernel-regression gating of Nearly Optimal Algorithms with Sublinear Computational Complexity for Online Kernel Regression never touches finite fields or code symmetries.
Research Program
Three components, one built on each direction. First, the formulation and regret theory. We formalize online distinguishing as prediction with expert advice where the experts are invariant tests and, crucially, where ground-truth labels are expensive — verifying a key means running cryptanalysis — so the learner operates in a label-efficient mode, requesting verification only for keys with high information gain about the current expert weights. This is the discrete-space transplant of the initialization logic in Informed Initialization for Bayesian Optimization and Active Learning, which selects early queries to identify active dimensions; here the "active dimensions" are the invariant statistics that separate the current family from random. We prove the full-information $O(\sqrt{T \ln N})$ bound, then a label-efficient variant quantifying the extra regret per unit of verification budget saved, following the label-inefficiency pattern already visible in the impossibility results of Agnostic Online Learning and Offline to Online Conversion, which jointly warn that naive offline-to-online conversion is exponentially expensive — precisely the barrier a gated dictionary is designed to dodge.
Second, the gating mechanism. We port the Approximate Linear Dependence dictionary idea from Hilbert space to $\mathbb{F}_q$: a key's invariant-response vector is admitted to the state only if it raises the state's rank. The empirical hypothesis, testable on the Goppa and QC-MDPC distinguishing datasets, is that structured streams saturate at small $d_{\mathrm{inv}}$ while random streams keep raising the rank — which itself becomes a cheap global distinguisher and gives the sublinear-compute claim empirical teeth. The analogue of the NONS-ALD regret bound is the target theorem: regret of order $O(d_{\mathrm{inv}} \ln T + \sqrt{T \ln N})$, matching the "pay only for genuinely novel directions" philosophy that Li and Liao established for continuous kernels.
Third, robust cold start across families. When a new code family enters the stream, we initialize expert weights from prior families via the dynamically re-weighted, decayed-FTRL construction of On Provably Robust Meta-Bayesian Optimization, whose RM-GP-UCB guarantee — asymptotic no-regret even if every prior task is adversarial — is exactly the property needed when "tasks" are code families whose metric geometry (Hamming vs. rank) is fundamentally incommensurable, the situation the DeepDistinguisher's cross-family failures expose. The deliverable is a proof that our warm-started learner is never asymptotically worse than its cold-start self, plus a measurement of how many initial keys that robustness costs, which the same paper identifies as the open latency in dissimilarity detection.
Proposed Experiments
All experiments run on stream versions of benchmarks documented in the file. The primary benchmark is the Goppa and QC-MDPC distinguishing dataset of AI for Code-based Cryptography, replayed as an interleaved sequence of structured and random keys; the reported reference point is over 98% accuracy for Goppa codes and up to 98% for QC-MDPC at row weights up to 6. The second is a weak-key stream built from the pseudorandom-code watermarking setting of Cryptanalysis of Pseudorandom Error-Correcting Codes, where implementation shortcuts produce identical-row weak keys detectable at a reported cost of $2^{22}$ operations, and where the security of practical lengths ($n \le 2^{17}$) cannot exceed 75 bits; our metric is detection latency and cumulative verification cost against that $2^{22}$ reference. The third is a drift stress test: ramps of Goppa degree $t$ and QC-MDPC row weight past the DeepDistinguisher's operating envelope, plus abrupt family switches among Goppa, Alternant, MDPC, and QC-MDPC blocks. Metrics throughout are cumulative misclassification regret against the best expert, per-key compute in field operations, dictionary size over time (the discrete analogue of the 13-example buffer NONS-ALD reports on parkinson), and warm-start overhead versus cold start.
Baselines
The do-nothing reference is to classify every key as random. It costs nothing, but its detection rate is zero and its accuracy equals the base rate of structured keys in the stream; any proposed method must clear it trivially, and it fixes the floor for the regret accounting. The strongest existing competitor is the offline DeepDistinguisher transformer from AI for Code-based Cryptography, which reports over 98% accuracy on Goppa codes and up to 98% on QC-MDPC for row weights up to 6; we run it on exactly the same streams with the same per-key inference compute and the same total data budget (retrained at fixed intervals to give it every chance to adapt), and beating it means matching its accuracy within a few points at its comfortable operating point while remaining far above chance in the parameter-shift and family-drift regimes where its accuracy collapses — at lower amortized compute. The third baseline is the single best classical algebraic test, such as a quasi-cyclic folding rank test, run standalone; no reported result found on Lacuna for its distinguishing accuracy, so we establish its number ourselves on the same streams. The remaining baselines are ablations that isolate each ingredient of the proposal: the dictionary restricted to a single expert (isolating expert aggregation), the full dictionary with every key fully evaluated and no rank gating (isolating the sublinear-compute mechanism), and warm-start via fixed-weight transfer in the style the meta-BO literature already shows to be fragile (isolating the robust FTRL re-weighting). Fairness is enforced by fixing the key generator, the stream order, the per-key compute cap, and the verification budget across all methods.
Why not just…?
Why not just train DeepDistinguisher offline on more data? This is the most serious alternative, and we will report honestly where it wins: on a stationary stream of a single family at parameters it was trained on, it should win, because supervised capacity beats online aggregation when nothing changes. The file's evidence cuts the other way as things drift: AI for Code-based Cryptography itself reports that accuracy collapses toward chance as Goppa degree $t$ grows, its training needs massive pre-generated datasets, and Offline to Online Conversion proves that converting offline estimators into sequential ones can demand exponential time. Our drift experiments settle this concretely: we measure how long the retrained baseline needs to recover after a family switch versus the online learner's adaptation latency, at matched total compute.
Why not just run the known algebraic distinguishers directly? For a known family, this can genuinely suffice — a folding rank test on QC-MDPC is cheap and targeted, and we include such tests as experts precisely because they are strong. But they are family-specific and parameter-brittle: the file shows pure combinatorial and pure algebraic solvers each fail outside their overdetermination thresholds, and only hybrids that guess subsupports to hit the threshold exactly broke RYDE, dropping it from 301 to 272 bits of security in Hybrid Subsupport Guessing. The experiment that decides this is the family-drift stream with unknown family identity, where no single test knows which regime it is in; the no-regret aggregation is the mechanism for not having to know in advance.
Why not just use random or Sobol screening and batch processing? Uniform sampling is designed for continuous domains; on discrete structured key spaces it has an exponentially small chance of landing on the informative configurations, and Informed Initialization for Bayesian Optimization and Active Learning already shows space-filling designs losing badly to model-aware selection in high dimensions with sparse active structure — its informed initialization recovered directional lengthscales nearly half an order of magnitude more accurately than competitors by the end of the first batch. We treat this as settled for our setting and do not spend an experiment on it beyond the do-nothing floor.
Why not just use fixed-weight transfer from prior code families? The meta-BO literature already quantifies the failure: On Provably Robust Meta-Bayesian Optimization shows that fixed-weight and standard transfer baselines suffer severe negative transfer when prior tasks are dissimilar, actively degrading below cold-start GP-UCB, while its decayed-FTRL re-weighting maintains no-regret even with adversarial priors. Our adversarial-warm-start ablation replicates that comparison on key streams: prior families deliberately chosen from the wrong metric geometry (rank-metric priors on a Hamming-metric stream), with the pass condition being that our robust variant never falls below its own cold-start run by more than the theoretically predicted overhead.
Decisive Checks
Three results would make or break the proposal. The gating mechanism works only if dictionary rank visibly saturates on structured streams and keeps growing on random ones; if both saturate or neither does, the sublinear-compute claim is empty. The robustness claim works only if the warm-started learner empirically tracks its cold-start twin under adversarial priors; a persistent gap falsifies the guarantee's practical bite. And the headline result is the drift curve: accuracy as Goppa degree and QC-MDPC row weight ramp past the offline baseline's envelope, where the target is a learner that bends and recovers while the batch transformer flatlines to chance.
References
- MDPC-McEliece: New McEliece variants from Moderate Density Parity-Check codes
- Hybrid Subsupport Guessing: A New Hybrid Technique for the Rank Decoding Problem
- AI for Code-based Cryptography
- Cryptanalysis of Pseudorandom Error-Correcting Codes
- Nearly Optimal Algorithms with Sublinear Computational Complexity for Online Kernel Regression
- On Provably Robust Meta-Bayesian Optimization
- Oracle-efficient Hybrid Learning with Constrained Adversaries
- Informed Initialization for Bayesian Optimization and Active Learning
- Agnostic Online Learning
- Offline to Online Conversion