it's very possible they only had to use the massive compute budget because they were trying to plagiarize his work before he published it though, e.g. autonomously do things in ~7 days what he had likely been thinking about for ~1 year.
428 karma · joined April 7, 2026
https://xenaproject.wordpress.com/2017/10/05/more-easy-lean-...
There are other examples though. For example, NP hardness of n^{1/400}-approx CVP. Like any NP hardness proof, this shows you can faithfully encode a hard problem (3SAT here iirc) in terms of another candidate hard problem. Not really a counterexample at all.
1. he was working on the same class of problems. He explicitly mentions they were working to extend their techniques to NS (the same techniques that OpenAI may have scooped somehow), and
2. while he was using LLMs to do it, this was part of fleshing out another mathematician's work in the area. He explicitly writes in his note that this other mathematician (Luis Martinez-Zoroa) deserves a Fields medal for this work.
this isn't to say everything will go perfect, but the people doing implementations are more experienced now, and the problem is an easier one to do (though in a certain sense, optimizing compilers are making any side-channel resistance a harder goal to achieve. an implementation that is resistant under one compiler version may not be resistant in the future).
Another way cryptography breaks is via iterative improvements. For example, in the last few months there are two big cryptanalytic stories
1. The novel scheme (though not standardized) HAWK had its security reduced by ~1/2 by AI. It is no longer compelling in any way. This was in a sense "predictable" though. There was a series of papers showing that HAWK-like schemes were vulnerable to an attack of this type. Then, AI was able to bridge the gap and apply these attacks directly to HAWK.
2. The ISO-standardized scheme McCliece (from ~45 years ago) has had some alarming security reductions, and may be effectively broken (it's still a little early to tell, many cryptanalytic papers require heuristics that must be justified, etc). Again, this was in a sense "predictable". Starting ~3 years ago it was discovered that McCliece had some yet-unexploited structure, and since then there have been more and more papers exploiting this further, until recently more dramatic attacks have occurred.
In both cases, there is a clear "story" you can (post-hoc) tell about the attacks. You can't always predict precisely where the attacks will end up (for the McCliece attack, it appears more effective than I would have predicted at least). But you can often tell when things are gradually weakening, before a full collapse.
RSA has a cousin (binary characteristic finite field DH) that had this gradual weakening into total collapse happen in the 2010s. It is possible this cousin was a problem child, and GNFS will remain the best attack against RSA until quantum computers fully break it. I can't predict the future. But I can say that ECC has had no such problematic cousins.
This is to say that we are blessed that we have extremely strong cryptography available. Why you would choose to use the weakest defensible option is beyond me, and not something anyone serious about security would ever recommend doing. There is no upside, and only downsides.
* for years people have noticed that many members of congress use privileged information to pick stocks.
* lobbying post-Citizen's United has a very decidedly "buying politicians" aspect to it
* a congressman (Menendez) was literally arrested while holding gold bars from a foreign government. he went to prison, but is the only person on this list who has iirc.
* the former mayor of new york (a long-time police offer) was embroiled in a Very Funny, very obviously true corruption scandal for turkish airline tickets. the prosecution against him was dropped for no good reason.
It's also worth mentioning the main concern for RSA is not GNFS, but something stronger. SOTA RSA attacks (such as GNFS) use "index calculus". You can also use index calculus to attack finite field diffie hellman. In the 2010's, there was remarkable progress in index calculus attacks against finite field DH in the small characteristic case. For example, the current record for binary characteristic finite field DH is ~30k bits (and this is by an academic --- a nation state could definitely do more).
It is not known that similar progress is possible in other cases (such as for RSA). But it's very much possible that factoring is much easier than expected. Simultaneously I wouldn't personally bet money on it, and if that breakthrough happened, there were sufficient warning signs that I would feel justified in saying "told you so" to people trusting RSA.
https://leodemoura.github.io/blog/2026-8-1-postmortem-for-ke...
This was initially "completed" in the 80s. You can see the timeline for cleaning up the proof in e.g. this mathoverflow answer
https://mathoverflow.net/questions/114943/where-are-the-seco...
it's something that some people have been waiting decades for, and is not yet completed.
Notably, junk theorems are true. Nobody would debate that the junk theorem is true. The main thing people would say is that junk theorems, while being true, are sensitive to precisely how you encoded mathematics, so despite being true, they are perhaps not conceptually meaningful.
As an example of a junk theorem, sasy you use the definition of the natural numbers using von neumann ordinals
https://en.wikipedia.org/wiki/Set-theoretic_definition_of_na...
Then for any natural numbers n, m, they're implicitly sets. So n \intersect m = min(n,m). This is the wrong way to think about natural numbers. You should not use this ever in proofs. But this isn't because your proofs would be false, but instead because it is a fundamentally confusing way to think about the natural numbers. It is in this sense it is a "junk theorem".
1. Some known set of architectures, with
2. Some known set of (constant time/variable time) operations
And then prove things about programs written against those architectures. See for example
https://github.com/PLSysSec/FaCT
That being said, practically the operations that are variable time are known, and are mostly* the same on all modern architectures. In particular
1. Branching on a secret-dependent variable, or
2. Indexing an array with a secret-dependent index, or
3. Some architecture specific operations (typically things like division, occasionally things like multiplications/shifting).
https://github.com/rust-stdx/stdx
https://news.ycombinator.com/item?id=48571266
Note that there are baby versions of this that are uncontentious, for example
this is missing the LTS release. but it is a curated group of libraries that are relatively uncontentious to recommend.
1. someone has a cheap disc brake bike for pleasure rides (mostly in the sun)
2. they get something like this for commuting or whatever
3. now they're on their disc brake bike most days (including when it rains), going faster than they're used to
it's not the end of the world, but it also doesn't seem great
CS = 2^8 m + e
here, S = [-s, 1] is a padded version of the initial secret. So recast everything as a linear equation (matrix) equation
CS = 2^8m + e
Without getting into too much details, one can define a "product" * such that
(CC)(SS) = (2^8m + e)(2^8m + e)
This becomes a "degree 2" equation. Mildly faking the details for simplicity, one can expand it out not in terms of A, b, but in terms of three components A, b, c, where c is the "degree 2" component. So here things have inflated. But there is also a technique to shrink this back down to a linear equation.
This shrinking process requires some auxiliary data, namely an encryption of SS under S. it is not the problematic part of HE though. Instead, data movement (say a circular rotation by k indices) also requires some "fixing up", though here involving an encryption of rot^i(S) under S.
This is more problematic, as there are many different rotations (often on the order of thousands), and you naively need a piece of auxiliary data for each of them (vs one for multiplication). There are ways to shrink the required number of keys, but in general they're the "heavyweight" part of FHE.
1. generate a 512 x 512 random (u32) matrix A, and
2. generate a 512-dimensional rounded (to the nearest integer) Gaussian, say of standard deviation 10, e.
The ciphertext is then [A, b :=As + e + 2^8 m].
To decrypt, you compute b - As to recover 2^8 m + e. You can then recover m, as e << 2^8 with high probability.
Anyway, if you have two of these ciphertexts, you can sum them together to get
[A1 + A2, (A1 + A2)s + (e1 + e2) + 2^8 (m1 + m2)]
this decrypts to m1 + m2, so you can recover homomorphic sums (or scalings by small integers).
Multiplication is more complex, so I won't get into it here. But the high level from the above example is that you could have someone compute arbitrary linear functions of your data without them knowing what your data is.
that being said, you can construct IND-CPA secure homomorphic encryption schemes from factoring-based assumptions iirc, so this isn't a fundamental obstacle.
https://eprint.iacr.org/2022/922.pdf
it's hard to precisely analyze BDGL16, but to leading order it takes ~ (3/2)^n time, which is roughly 2^{.292n} time.
When I say it takes roughly this amount of time, this is likely modulo several heuristics. With the caveat that I'm not a lattice cryptanalyst, my understanding of the heuristics is the following. BDGL16 is a "sieving" algorithm. To find a short vector v, you
1. start with many long vectors v1, ..., vn.
2. take their pairwise differences. this may produce shorter vectors (and if vi are suitably randomly distributed, this is provably true).
3. repeat
there are other tricks on top of that you do, but that's the conceptual core. As I mentioned, if the
1. initial vi were suitably randomly distributed, and
2. you could prove the pairwise differences were also suitably randomly distributed
you could likely get a provable running time bound on things. At least the 2nd likely breaks down (maybe the first as well though), so you instead only get a running time bound under the above 1+2 heuristic assumptions. In cryptanalysis this is typically viewed as good enough, as long as the heuristics are solid (for example, SOTA for factoring, the Number Field Sieve, only has heuristically understood running time iirc).
This paper is instead about provable algorithms. They can be conceptually interesting, and useful if there is not community consensus that the heuristics are solid. But in lattice cryptography everyone thought BDGL16 used reasonable heuristics, so SVP took 2^{0.292n} time practically, even if it was too difficult to formally prove this.
https://eprint.iacr.org/2022/922.pdf
for some history