Learning the Decoding Boundary: LLM-Evolved Noise for Estimating Rare Decryption Failures

Modern post-quantum ciphers — the ones being deployed now to survive quantum computers — encrypt by adding carefully chosen mathematical noise to a message and decrypt by removing it. Sometimes, with very small probability, the noise wins: a valid ciphertext fails to decrypt. That probability is not a quality-of-service number; it is a security parameter. An attacker who can query a decryption device and observe which ciphertexts fail learns, bit by bit, the geometry of the secret key's decoding boundary, and rare failures are exactly the oracle that reaction attacks feed on. The trouble is that nobody can measure the number. Standard parameter sets demand failure rates around $2^{-128}$, while direct simulation by repeated encryption and decryption stalls somewhere near $10^{-9}$ to $10^{-12}$. Practitioners therefore rely on analytical bounds, and those bounds rest on an assumption their own authors flag as false: that failures of individual polynomial coefficients are statistically independent, when polynomial multiplication in fact ties them together.

This proposal builds an automated pipeline that attacks the problem from the data side rather than the proof side. The plan is to treat the cryptosystem itself as a forward physical model — encryption plus decryption is a simulator that, like the PDE solvers used to label pollution-source locations in Predicting Locations of Pollution Sources using Convolutional Neural Networks or the finite-element engine labeling internal forces in Learning Force Distribution Estimation for the GelSight Mini Optical Tactile Sensor Based on Finite Element Analysis, returns exact ground-truth labels (decrypt / fail) for any configuration we feed it. An LLM then mutates executable sampling code that defines structured noise, error, and key configurations; every mutated configuration is run through the real decryption routine and kept only if it actually produces failures at a measurable rate. The surviving corpus trains a surrogate model of the decoding boundary whose architecture is constrained by the algebra of the ring — the cryptographic analogue of the biomechanical priors that keep synthetic organ deformations physically legal in Beyond respiratory models: a physics-enhanced synthetic data generation method for 2D-3D deformable registration and Generative Myocardial Motion Tracking via Latent Space Exploration with Biomechanics-informed Prior. That surrogate then extrapolates failure probabilities into regimes no simulation can reach, and, as a by-product, surfaces weak key classes automatically.

Core Claim

The claim has two parts. First, that an LLM mutating code — not prose — can discover worst-case error and key structures in post-quantum schemes far more efficiently than random search, because the interesting structures (like BIKE's clustered "gathering" keys) are combinatorial objects that a code-mutating LLM can express and a decryption oracle can verify. Second, that a surrogate trained on this structured corpus, with the ring's algebra built into its architecture, can extrapolate decryption failure rates below $2^{-128}$ without assuming coefficient independence, and that its estimates will be calibrated where we can check them and informative where we cannot. The importance-weighted estimator that makes tail extrapolation sound is the standard one:

$$\widehat{\mathrm{DFR}} = \frac{1}{N}\sum_{i=1}^{N} \mathbf{1}\!\left[\mathcal{D}_{sk}(c(e_i)) \neq m\right]\frac{p_0(e_i)}{q_\theta(e_i)}, \qquad e_i \sim q_\theta,$$

where $p_0$ is the scheme's honest noise distribution, $q_\theta$ is a proposal distribution learned by the surrogate, $\mathcal{D}_{sk}$ is the decryption routine, and $\mathbf{1}[\cdot]$ is 1 when decryption fails. The whole game is finding a $q_\theta$ that concentrates mass on the true failure region instead of an independence-flavored approximation of it.

What the Literature Leaves Open

Three lines of work bracket this proposal. The analytical line models lattice encryption as a noisy channel: Information- and Coding-Theoretic Analysis of the RLWE/MLWE Channel derives capacity bounds and shows BCH error-correcting codes can suppress failure rates dramatically, and Higher Rates and Information-Theoretic Analysis for the RLWE Channel extends the analysis — but both lean on stochastic independence across coefficients, an assumption the first paper's authors themselves identify as a central limitation. The weak-key line shows independence-style averages can be badly wrong in practice: Exploring Decryption Failures of BIKE: New Class of Weak Keys and Key Recovery Attacks discovers keys whose clustered nonzero coordinates push the average failure rate to at least $2^{-116.61}$, violating the $2^{-128}$ correctness assumption BIKE's security argument needs — and it found this by manual combinatorial derivation, not by any automated search. The security-proof line, notably Fujisaki-Okamoto Transformation under Average-Case Decryption Error: Tighter and More General Proofs with Applications to PQC, shows FO transforms can be proven secure under average-case decryption error — but says nothing about how to estimate the concrete error distribution, and On the Applicability of the Fujisaki-Okamoto Transformation to the BIKE KEM shows message-dependent failures break the proof's assumptions outright.

On the methods side, two papers supply the machinery this proposal reuses. Towards Foundation Models for Mixed Integer Linear Programming shows an LLM evolving executable Python problem code, with an exact solver filtering out trivial and infeasible instances, produces training data that lets a model generalize to unseen problem classes where standard augmentation fails. Adaptive Problem Generation via Symbolic Representations shows that generating problems in symbolic code space yields structurally distinct instances (pairwise embedding cosine distance 0.37 versus 0.07 for natural-language generation) and doubles downstream gains. Neither touches cryptography; the open move is to point this machinery at the space of structured noise and key configurations, where the "solver" is the decryption oracle itself and the "failure region" is the object of study rather than a nuisance to filter away.

Research Program

The pipeline has three components. The generator is an LLM operating on SageMath/Python code that samples keys and error vectors for a target scheme (BIKE's QC-MDPC codes, Kyber's module lattices). Starting from the scheme's honest sampling code as a seed, the LLM applies evolutionary mutations — clustering nonzero coordinates into windows, tilting weight distributions, changing decoder iteration counts, injecting structured correlations across ring coefficients — in the spirit of the mutation and constraint-injection operators of MILP-Evolve. The verifier runs each mutated configuration through the actual decryption routine under a fixed oracle-call budget and discards configurations that never fail (trivial) or always fail (degenerate), exactly the execution-verification loop that Towards Foundation Models for Mixed Integer Linear Programming found indispensable for weeding out hallucinated, infeasible instances. The surrogate is a network whose layers respect the ring/module structure of the scheme — convolution matched to polynomial multiplication, so the model can only represent failure correlations that are algebraically possible — trained on the verified corpus to predict decryption success or failure, in the way neural surrogates approximate expensive wave-equation solvers roughly 100× faster in Fast acoustic scattering using convolutional neural networks and Seismic wave propagation and inversion with Neural Operators. The surrogate defines $q_\theta$ for the estimator above, and a closed loop in the style of Adaptive Problem Generation via Symbolic Representations feeds surrogate disagreement back into the LLM's prompt, directing mutation toward the boundary regions the surrogate is least sure about.

A natural extension, held as a second phase rather than the core, models physical fault channels continuously. Existing fault attacks treat instruction glitches as binary skips — Preparing for Kyber in Securing Intelligent Transportation Systems Communications and Key-Recovery Fault Injection Attack on the Classic McEliece KEM both bypass the re-encryption check outright — whereas real glitch dynamics are analog, like the continuous RAM decay modeled in Recovering AES Keys with a Deep Cold Boot Attack. A forward degradation model of voltage transients, analogous to the optical point-spread-function blur that made synthetic microscopy images realistic in Nuclei Segmentation of Fluorescence Microscopy Images Using Three Dimensional Convolutional Neural Networks and the screen-recapture optics of Face Anti-Spoofing: Model Matters, so Does Data, would let the same pipeline estimate how physical faults expand the effective failure boundary.

Proposed Experiments

Experiment one is a blind rediscovery test on BIKE at the 128-bit parameter set. The pipeline is seeded only with the scheme's standard sampling code; the LLM has no hint about the gathering property. Success means the pipeline, within a fixed oracle-query budget, isolates a clustered weak-key class whose per-key failure rate is consistent with the published lower bound $\text{DFR}_{\text{avg}} \ge 2^{-116.61}$ from Exploring Decryption Failures of BIKE, and whose implied key-recovery complexity brackets the reported $2^{116.61}$ (without ciphertext reuse) or $2^{98.77}$ (with reuse). The headline metric is oracle queries per discovered weak class, compared against the manual analysis effort of the published work.

Experiment two is tail extrapolation on NewHope and Kyber. The surrogate is trained on configurations producing failures in the Monte-Carlo-reachable band (roughly $10^{-6}$ to $10^{-12}$), calibrated on held-out rates in that band — predicted versus observed failure probability must land inside binomial confidence intervals — and then extrapolated toward $2^{-128}$ and beyond. The comparison point is the independence-based analysis of Information- and Coding-Theoretic Analysis of the RLWE/MLWE Channel, which reports reducing NewHope's decryption failure rate from $2^{-216}$ to $2^{-12769}$ at fixed bitrate via BCH coding (with bitrate gains of roughly 7× for NewHope and 1.84× for Kyber). The decisive quantity is the gap: by how many bits of security does the dependence-aware estimate differ from the independence-based one, and does the gap grow for the BCH-enhanced channel where coefficient coupling is strongest?

Experiment three is the ablation and diversity study. It measures the embedding diversity of generated configurations under symbolic mutation versus natural-language prompting (expecting a contrast like the 0.37-versus-0.07 cosine distance reported in Adaptive Problem Generation via Symbolic Representations), and it runs the pipeline with the verification filter removed, with the LLM replaced by hand-written random mutation operators, and with the algebra-informed surrogate replaced by a generic multilayer perceptron over coefficient vectors. No reported result found on Lacuna for any prior weak-key search or dependence-aware failure estimate on Kyber, so experiment two's extrapolation is genuinely uncharted.

Baselines

The naive reference point is direct Monte Carlo: run $N$ honest encryptions and decryptions per parameter set and report the empirical failure count. At BIKE's and Kyber's target parameters this yields "zero failures in $N$ samples," i.e., only an upper bound around $1/N$, and the file's sources agree that simulation becomes infeasible exactly in the regimes that matter — Exploring Decryption Failures of BIKE states directly that for larger parameters the failure rate becomes too small for direct simulation. Every method, including ours, receives the same oracle-call budget, so this baseline also defines the budget in queries.

The strongest existing method is the analytical machinery of Information- and Coding-Theoretic Analysis of the RLWE/MLWE Channel, which reports, for NewHope at fixed bitrate, a decryption failure rate reduced from $2^{-216}$ to $2^{-12769}$ using BCH codes over a $Q$-ary channel model. It is the strongest competitor because it is the only method in the file that produces concrete numbers in the ultra-rare regime at all. It will be run by applying its published independence-based bound formulas to the identical parameter sets (plain and BCH-enhanced NewHope and Kyber), with no tuning advantage. Beating it means producing a calibrated estimate in the reachable band and a bound-free extrapolation whose confidence interval either contains the analytical number (confirming independence is benign there) or excludes it (quantifying the hidden vulnerability), with the divergence explained by inspected dependence structure in the surrogate.

The third baseline is cross-entropy importance sampling with a hand-designed parametric tilt of the honest noise distribution — no LLM, no surrogate. It is the strongest "simple statistical" competitor and gets the same query budget. The key ablation isolates the proposal's central ingredient: the same pipeline with the LLM's symbolic mutation replaced by random perturbation of the sampling code, keeping the verifier and surrogate identical. If random mutation finds weak classes as cheaply as LLM mutation, the LLM is decorative and the proposal collapses to a surrogate-plus-importance-sampling paper; that outcome would itself be informative, and the experiment is designed so it can be detected.

Why not just…?

Why not just run Monte Carlo with importance sampling? This is the most serious objection, and cross-entropy methods are the real threat. The honest answer is that a fixed parametric tilt family — tilting error weights or variances — searches within a family that cannot express combinatorial clustering: the gathering property that sinks BIKE's average failure rate to $2^{-116.61}$ is a structural property of where nonzeros sit, not a parameter of an independent-coordinate distribution, and Exploring Decryption Failures of BIKE found it only through manual structural analysis. Still, the head-to-head against cross-entropy sampling in experiment three is the decisive test, and if a cleverly chosen tilt family matches the pipeline on BIKE and Kyber, the proposal should be revised to drop the LLM component rather than defended.

Why not just tighten the analytical bounds? Because the independence assumption is not a loose end but the load-bearing simplification: the authors of Information- and Coding-Theoretic Analysis of the RLWE/MLWE Channel acknowledge it themselves, and the BIKE weak-key result is a demonstrated case where independence-flavored reasoning overestimated security by more than eleven bits ($2^{-116.61}$ actual versus $2^{-128}$ assumed). Analytical tightening is also complementary rather than competing: a calibrated surrogate gives analysts an empirical target their closed forms must hit, the same role exact solvers play in filtering LLM-generated MILP instances.

Why not just have experts hand-derive weak keys for each scheme? That is literally how the BIKE result was obtained, so the objection has force. The counter is scaling: manual combinatorial analysis was affordable for one scheme's one parameter set, and no reported result found on Lacuna for any equivalent weak-key enumeration on Kyber, NewHope, or the rank-metric schemes of On a Rank-Metric Code-Based Cryptosystem with Small Key Size and Interleaving Loidreau's Rank-Metric Cryptosystem. The pipeline's value proposition is measured by experiment one: if it cannot rediscover the gathering property blind, cheaper than experts did, it should not be trusted on new schemes.

Why not just prompt the LLM in natural language? Because the evidence says natural-language generation changes phrasing, not structure: Adaptive Problem Generation via Symbolic Representations measured embedding diversity of 0.37 for symbolic mutation against 0.07 for natural-language modification, and Towards Foundation Models for Mixed Integer Linear Programming found prompt-only frontier models could not reliably interpret raw mathematical files. Relatedly, out-of-the-box generative models fail basic physical invariants outright — video generators render falling objects with sub-Earth gravity in Objects in Generated Videos Are Slower Than They Appear — so an unverified LLM proposal for "hard noise" would be worthless; the verification loop against the real decryption oracle is what makes hallucinated configurations impossible to keep.

Decisive Checks

Three results would settle the proposal. First, blind rediscovery of BIKE's weak-key class within the query budget, validating the generator on the one ground truth the field has. Second, calibration of the surrogate's failure-rate predictions inside binomial confidence intervals across the reachable band, on configurations the surrogate was not trained on. Third, a quantified divergence — with uncertainty — between the dependence-aware extrapolation and the independence-based bound of Information- and Coding-Theoretic Analysis of the RLWE/MLWE Channel at NewHope and Kyber parameters, or a demonstrated agreement that lets the community finally trust the independence assumption with evidence instead of necessity. Any of the three outcomes is publishable; only the middle path — calibrated but untested extrapolation with no structural discovery — would count as failure.

References

  1. Predicting Locations of Pollution Sources using Convolutional Neural Networks
  2. Learning Force Distribution Estimation for the GelSight Mini Optical Tactile Sensor Based on Finite Element Analysis
  3. Beyond respiratory models: a physics-enhanced synthetic data generation method for 2D-3D deformable registration
  4. Generative myocardial motion tracking via latent space exploration with biomechanics-informed prior
  5. Information- and Coding-Theoretic Analysis of the RLWE/MLWE Channel
  6. Higher Rates and Information-Theoretic Analysis for the RLWE Channel
  7. Exploring Decryption Failures of BIKE: New Class of Weak Keys and Key Recovery Attacks
  8. Fujisaki-Okamoto Transformation under Average-Case Decryption Error: Tighter and More General Proofs with Applications to PQC
  9. On the applicability of the Fujisaki-Okamoto transformation to the BIKE KEM
  10. Towards Foundation Models for Mixed Integer Linear Programming
  11. Adaptive Problem Generation via Symbolic Representations
  12. Fast Acoustic Scattering Using Convolutional Neural Networks
  13. Seismic Wave Propagation and Inversion with Neural Operators
  14. Preparing for Kyber in Securing Intelligent Transportation Systems Communications: A Case Study on Fault-Enabled Chosen-Ciphertext Attack
  15. Key-Recovery Fault Injection Attack on the Classic McEliece KEM
  16. Recovering AES Keys with a Deep Cold Boot Attack
  17. Nuclei Segmentation of Fluorescence Microscopy Images Using Three Dimensional Convolutional Neural Networks
  18. Face Anti-Spoofing: Model Matters, so Does Data
  19. On a Rank-Metric Code-Based Cryptosystem with Small Key Size
  20. Interleaving Loidreau's Rank-Metric Cryptosystem
  21. Objects in Generated Videos Are Slower Than They Appear: Models Suffer Sub-Earth Gravity and Don’t Know Galileo’s Principle...for now