Floors, not bounds: two research papers, explained
Modern encryption is trusted because, as far as anyone knows, breaking it takes an impossible amount of work. Two new papers ask a more careful question: if you fix the rules of the game — the assumptions everyone already makes — what is the least work an attack could take within those rules?
That least amount is a floor. Both papers find floors, prove them, certify the key numbers by machine, and say plainly what the floors do not mean. The papers are by Sean Ward and Maestro, iGent AI’s autonomous software-engineering agent; the papers, their code and this page came out of one five-day working session between the two.
Paper 1 — post-quantum encryption. One historical estimate behind ML-KEM, one shortcut removed. The estimate assumed the attack’s progress follows a straight line; the real line bends. Replace it by the most attacker-friendly shape the estimate’s own rules allow — we call it the floor shape — and, by the estimate’s own reckoning, the attack needs a little more effort at every security level: on its effort dial, 406 becomes 417. That is a statement about one old estimate, not about how safe ML-KEM is.
Paper 2 — factoring. How far can a factoring method with a proof attached go? The fastest such method, Harvey’s, takes about N1/5 steps. It and its closest relatives play by the same few rules — call them Harvey’s rules — and under those rules N1/5 cannot be beaten. The dream of N1/6 would need far more pattern in the numbers than anyone has found.
What is a floor?
Not a guarantee. An honest “no lower than this, given the rules.”
Think of a limbo contest. Nobody can prove how low a perfect contestant could go. But if everyone agrees on the rules — no digging up the floorboards — then the floor of the room is a hard limit, and you can say exactly where it is.
Cryptography is usually argued the other way round: here is the best attack we know, so the scheme is probably safe. Both papers instead write down the rules the existing arguments already assume, work out the exact floor under those rules, and then list every way a cleverer attacker could break the rules.
- Write down the rules. Exactly which assumptions, or which moves, are allowed. Check that the known attacks really do follow them.
- Find the floor. Prove the least possible value under those rules. A theorem, not an estimate.
- Certify what can be certified. Certified values come with machine-checkable certificates and interval arithmetic; everything else is labelled proved, conditional, heuristic, computed or measured.
- List the loopholes. Every move the rules forbid is written down, with what is known about it. A cheaper attack must use one.
What a floor is not. It is not a proof that a code is safe. If an attacker finds a way around the rules, the floor no longer applies. Both papers say so in their opening paragraph, and this page repeats it in every section.
Why does this matter?
The security of today’s encryption rests on a sentence like “nobody has found a faster attack.” That is an observation about people, not about the problem. A floor is a different kind of statement: inside a stated set of rules, the number cannot go lower. It is a theorem, it can be checked by anyone, and the rules are written next to it.
Three things follow.
Hidden assumptions become a list. Every security estimate leans on assumptions, usually in the background. Writing them down as rules and proving the floor under them puts each assumption in the open with a price attached: the papers list every rule a cheaper attack would have to break. Anyone hunting for a better attack knows exactly where to dig, and anyone relying on the estimate knows exactly what they are trusting.
Solid numbers are separated from guesses. For ML-KEM, the number careful practitioners already use turns out to be the floor of the rule they were assuming — now certified, and shown to move by only two or three notches when the rule is loosened. For factoring, the papers show how far the fastest provable methods are from the dream of N1/6, and exactly what a breakthrough would have to find.
Everything can be re-run. The key numbers come with certificates that a second program re-checks, the code is published, and every random choice is recorded. The results can be reproduced rather than taken on trust — a habit that security estimates could use more of.
What floors do not do is make anything safer or weaker, or remove the need to keep looking for attacks that break the rules. They say precisely what “as far as anyone knows” currently rests on.
Paper 1: the straight-line shortcut, and what replaces it
The puzzle
ML-KEM, the encryption standard chosen for the quantum era, rests on a geometric puzzle: in a grid with about a thousand dimensions, find an unusually short arrow hidden among long ones. The best known attack tidies the grid one chunk at a time. Its progress is summed up by a profile — a line that shows how tidy each position of the grid has become.
The shortcut
The official estimate assumed this profile is a perfectly straight ramp. Everyone knew the real one bends: it sags at the start and kicks up at the end. Estimators patch the difference by simulation.
What we did instead
We threw the ramp away and kept only the one rule the estimate already relied on: at every chunk, the tidying cannot beat the average luck of a random grid. Among all profiles that obey that rule, exactly one is the best possible for the attacker. We call it the floor shape, and we can compute it exactly, in a fraction of a second, with a certificate a second program re-checks.
What it does to the estimate
The estimate has an effort dial, called the blocksize. Turn it up and the attack works but costs more. The estimate reads off the lowest setting at which the attack succeeds. Swap the straight ramp for the floor shape, and that setting moves up at all three security levels:
| Security level | Straight ramp | Floor shape | Change |
|---|---|---|---|
| ML-KEM-512 | 406 | 417 | +11 |
| ML-KEM-768 | 624 | 642 | +18 |
| ML-KEM-1024 | 874 | 900 | +26 |
Same reasoning, one shortcut removed, a little more effort demanded of the attacker — by this estimate’s own rules.
What this does not say. It does not say ML-KEM is safer or weaker than believed. It corrects one historical estimate under that estimate’s own rules; whether real attacks obey the rule at real sizes is an open question, and the paper says so.
Specialists already know the ramp is off, and correct it with a simulator that imitates the tidying step by step. The paper proves that the simulator’s resting points are exactly the shapes obeying the rule, and computes that from the standard start it settles on the floor shape (capped where the grid itself caps it), so it gives the same 417, 642 and 900 — a computed coincidence, the paper is careful to say, not a theorem. The floor does not change the number a careful practitioner already gets. What it adds is a proof that no shape obeying the rule can do better, a certificate for that proof, and a measure of how far the number can move.
Does it hold up?
Three checks. First, loosen the rule a little everywhere: the dial still moves up, just slightly less (to 415, 639 and 897 — the first two certified, the third from an ordinary floating-point scan). Second, a reality check: at small sizes, where every step can be measured exactly, real tidying algorithms do break the rule slightly, but only at the very first position, and allowing eight times the slack we measured there moves the result by at most one notch, at one of the three levels. Third, the specification’s own script, run today, puts the straight ramp at 406, 626 and 878 — within three notches of what it printed and within four of our 406, 624 and 874; the small differences come from a cap the script applies at the head of the ramp.
For the curious: the precise statements
The class. Profiles ℓ1, …, ℓd (log Gram–Schmidt lengths) satisfying, at every projected block of size βi = min(β, d−i+1), the linear inequality that the floor side of the Gaussian heuristic imposes, with an optional uniform slack ε.
Theorems. Over the class, the head ℓ1 and every prefix volume have exact minima, attained by the unique profile at which every inequality is tight (Theorems 2.2, 3.1). The dual multipliers are strictly positive rationals computed in O(d) exact operations (Theorem 2.3); values are enclosed by 256-bit ball arithmetic and re-derived by an independent checker. No single entry beyond the head is bounded at all (Lemma 3.2).
The re-evaluation. The specification’s success test depends only on the volume of the first d−b basis vectors; bounding that volume by the extremal profile moves the crossing blocksize from 406/624/874 to 417/642/900 at (m, d) = (517, 1030), (698, 1467), (890, 1915), each certified least in its scanned interval. Uniform slack 0.01: 415/639/897 (the ML-KEM-512 and ML-KEM-768 values certified, the third a double-precision scan). Head-only slack up to 1: unchanged at the first two levels, 900 → 899 at the third. The specification’s script (commit 75c2694) returns 406/626/878 for the GSA line clipped at log q; the converged Chen–Nguyen simulator returns 417/642/900 under both readings of the detection condition, and the probabilistic Bai–Stehlé–Wen simulator the same or one blocksize less.
The audit. With unpruned block enumeration at dimensions 75–225, the outputs leave the zero-slack class at the head by certified amounts between 0.005 and 0.14 (log units); the first vector is about 12% shorter than the heuristic length of its block. A head-only deficit of 0.13 shifts the detection bound by 1.3·10−4, against the 0.06 that separates the extremal entry from the GSA line’s.
Also. f(n) = L(n)/(n−1) attains its integer maximum at n = 36, not near 46; the larger figure comes from the leading term of an asymptotic expansion alone. The extremal profile is the fixed point of the idealised recurrence animated above (Appendix C). Proposition 6.1 characterises the fixed points of a Chen–Nguyen tour as the profiles obeying the reverse block inequalities, and Lemma 6.2 the ceiling of the pipeline; that the iteration from the standard start converges to the head-clipped extremal profile (up to the simulator’s tail convention), and the coincidence of the three integer crossings, are computed findings, not theorems. A q-aware form of the rule, capping entries at log q, leaves the crossings unchanged, and at the three crossings the extremal head lies below the ceiling.
Paper 2: searching a beach with a metal detector
The puzzle
Multiplying two 300-digit primes is easy. Recovering them from the product is the hard problem behind RSA. Most factoring methods are educated guesses: they usually work, but nobody can prove how long they take. The fastest method that comes with a proof (Harvey, 2021) takes about N1/5 steps — for a 600-digit N, a 120-digit number of steps. Could a method of this kind reach N1/6? That is Harvey’s open question. The report writes down the rules his method and its closest relatives follow — call them Harvey’s rules — and asks what it would take inside those rules.
The rules
Harvey’s rules describe a search like sweeping a beach with a metal detector. The hidden prime is somewhere along a stretch of beach. Each cell the method lays down checks one short segment. The cells must cover the whole stretch, because nobody knows where the prime is. Then a clever batching trick checks all the cells at once.
The floors
Under Harvey’s rules you must check at least N1/3 candidates in total — Lehman’s method from 1974 already checks that many. Checking them with the best batching known costs N1/5, which is exactly Harvey’s method. Even a perfect, free batching could not beat N1/6 under the same rules.
What the dream would need
Perfect batching is only possible if the cells’ starting positions line up in a special repeating pattern. We studied those positions closely. They are not random: the report finds genuine clusters of repeated gaps, proves that the biggest pile-up must grow as the numbers grow, and works out where the clusters come from. But the pattern found is far weaker than perfect batching would need. At the sizes we can compute, the biggest pile-ups are a few times larger than a random set’s — but the set is no more compressible than a random one, and the pile-ups are far too sparse for the batching trick to use. How fast the pile-ups can grow at most — the report’s envelope problem — is left open, so the dream is neither ruled out nor within reach.
If part of the secret leaks
Sometimes attackers learn a few digits of the prime. The report prices this exactly. In the cell game, each leading digit you learn is worth more than each trailing digit. But once about half the digits are known, a different method (Coppersmith’s) takes over and the problem becomes easy.
Three more floors
Shared factors — a shortcut for a special family. Some RSA variants deliberately build their two primes so that p−1 and q−1 share a large factor. We show such numbers can be factored faster than Harvey’s bound, from the public number alone, as soon as the shared factor is larger than about the twentieth root of N.
Fixed curves — a certificate for a list, over stated ranges. For three specific ranges of primes below 223, a fixed list of ten to twelve elliptic curves is certified to factor every product of two primes from the corresponding range. The report also proves that a method from 1974 succeeds on a fair share of numbers faster than N1/5 — without saying which ones.
The number field sieve — no hidden win in step one. The fastest practical factoring method begins by choosing a polynomial. Within the report’s counting model, the coefficients cannot be much smaller than they already are for ordinary numbers, so the method’s famous constant has no room to move.
What this does not say. None of this is a lower bound on factoring in general. Methods that break the rules — including the number field sieve itself, and any method that guesses and checks — are outside these floors. The report lists each such loophole and what is known about it.
For the curious: the precise statements
The model. An oblivious Lehman-cell babystep–giantstep algorithm lays down cells aq + bp whose tested integers cover the real range of the smaller factor, then finds the hit by a collision search. It contains Harvey’s algorithm exactly and, up to No(1), those of Lehman and Harvey–Hittmeir; Hittmeir’s residue-thinned search and Hart’s one-line method are members for which the floors are not asserted. Floors: cN1/3 candidates; cN1/5 with materialised giants; cN1/6 with free giants. All three exponents persist for unbalanced factors p ≥ N2/5; the materialised-giant floor also holds for polynomial test forms of any fixed degree, and the candidate floor against adaptive cell queries; residue-hypothesis thinning modulo q ≤ N1/20 buys at most (log log N)3/5.
The dream. An N1/6 search needs an efficiently computable difference cover B − G of the candidate set. Every explicit cover is bounded below through one statistic of the window starts ⌊(√(aN) − √b)2⌋: the largest number of pairs sharing (approximately) the same difference. That statistic provably grows at least like r1/3 in one regime and at least like N1/12 in another (for the squarefree shell, for almost all N); unconditional upper bounds 2.1 r2/3 and 6N2/9 are proved, and the gap is the open envelope problem. Under two stated conjectures, and for the families satisfying the hypotheses the paper specifies, the in-model floors are N5/28 and N2/11.
Partial information. With p in an interval of length Nλ: cost N3λ/5 − 1/10 for λ ≥ 3/8, matching the model’s floor; below 3/8 the in-model cost of an interval depends on its position through a Diophantine depth. With p mod M = Nμ known: N1/5M−2/5 for M ≤ N1/7. In the model a leading bit is worth 23/5 and a trailing bit 22/5; in Coppersmith’s branch either is worth 2.
Three further floors. gcd(p−1, q−1) = g = Nγ: factoring from N alone below N1/5 for every γ > 1/20, by composing McKee–Pinch’s progression search, made deterministic, with Pollard–Strassen on N−1 and Harvey–Hittmeir’s order selection. Ten, eleven and twelve Suyama curves certify [218, 219), [220, 221), [222, 223); Pollard’s p−1 succeeds on a positive proportion of nearly balanced semiprimes at exponent approaching 1/(4√e) ≈ 0.152. NFS polynomial selection: a random-root floor N1/(d+1)−o(1), a rigorous resultant floor, and — under a stated counting heuristic — the GNFS constant 1.923 as the existence optimum for generic N.
How we check
The papers keep a strict vocabulary. A number is called certified only when it comes with a machine-checkable certificate: in the lattice paper, exact rational multipliers re-verified by an independent second program, and interval arithmetic that tracks its own rounding error, so that a comparison counts only when the intervals leave no room for doubt. Everything else is labelled for what it is — proved, conditional, heuristic, computed or measured — and every random choice is recorded, so anyone can regenerate the results from the code and archives that accompany the papers, at github.com/iGentAI/factorlab .
The animations on this page run the same formulas in your browser, in ordinary double precision, so they are illustrations rather than certificates. The numbers they produce — the floor shape, the crossing settings 406 → 417 and their companions, the gap statistics for the small numbers offered — agree with the values reported in the papers.
How the work was reviewed. The papers, their code and this page came out of one five-day working session between Sean Ward and Maestro. Before release the drafts went through rounds of adversarial review by several independent AI models, and the objections were worked back into the papers and this page. No external human peer review has taken place yet; the certificates and code are published so that it can.
A short glossary
Floor. The least possible value of something under a stated set of rules. Not a limit on what could happen if the rules are broken.
Floor shape. Among all profiles that obey the one rule of Paper 1, the shape that is best for the attacker. The estimate’s shortcut replaced it by a straight line.
Harvey’s rules. The few assumptions Harvey’s factoring method and its closest relatives share: lay down cells that cover the whole range, then find the hit with a batch search. The floors of Paper 2 hold under these rules and claim nothing outside them.
Lattice. A regular grid of points in many dimensions. Post-quantum encryption hides secrets in the shape of such a grid.
Profile. A line that records how tidy each position of a grid has become after an attack has worked on it. The official estimate assumed it was straight.
Blocksize (the effort dial). How big a chunk the tidying algorithm works on at once. Larger chunks give a better result at exponentially greater cost; security is quoted as the smallest setting at which an attack works.
Semiprime. A number that is the product of exactly two primes, such as an RSA key. Factoring means recovering the two primes.
Cell. One short segment of the search that a guaranteed factoring method checks. Covering the whole range is what forces the N1/3 floor on the number of candidates checked.
Read the originals
Code, certificates, censuses and archives for both papers: github.com/iGentAI/factorlab .
This page is a plain-language guide; where it and a paper differ, the paper is authoritative. Correspondence: sward@igent.ai.