I think we might lose public key cryptography
twitter.com/matthew_d_green
[4 comments hidden]
at least he agrees that "he can't see the future"
there is just as much evidence for the opposite stance: AI can help us improve and formally verify every security reduction we use. As long as math allows some kind of trapdoor function, AI can help us produce the best crypto we can achieve from it.
[2 comments hidden]
[hidden]
https://nitter.meowing.monster/matthew_d_green/status/210827...
[hidden]
AI can help us improve! That's true, but not a different point. The story here resounds with me, if you read the follow up threads linked elsewhere in this submission. We've relied heavily on a small handful of mathematicians around a very small number of public key cryptography algorithms. Is this the best humanity could do? Meh. Not really.
I think it's more likely AI is good for attack than creation. I do think we'll be ok! But this genuflecting on what is, it rocks.
[2 comments hidden]
Way more likely is that every existing cryptocurrency implementation contains bugs outside of the core cryptographic algorithm that would allow stealing coins without having to break that encryption. Cybersecurity is an arms race, as it always has been.
[hidden]
The only way I've been pressured to use a shorter key length is when the longer one for some reason is treated as an entirely separate algorithm that is randomly unsupported (looking at you, P-521)
[3 comments hidden]
[2 comments hidden]
[hidden]
There is a social aspect to cryptography: the study of what types of puzzles we don't publicly know how to solve (yet) can in some cases be used to construct cryptographic primitives, so that we can derive cryptographic value (access to cryptography) from parts of mathematics we don't understand yet, this obviously relies on the main body of mathematics being publicly accessible.
That window on mathematics (the puzzle needs to be employable as a cryptographic primitive AND the puzzle needs to hard enough) is expected to vary over time, as long-time puzzle types fall, and hopefully new puzzle types emerge.
One observes no guarantees on the window width, nor on how fast that window is sweeping over the frontier of mathematics (even if humans aided with LLMs are continuously capable of finding fresh cryptography, useful for a while until it expires, it takes times to manufacture hardware to replenish all end-user electronics, so if the cadence is high enough, we might continuously have novel forms of cryptography, in time as formula's, but too late to secure the boot chains across humanity, surveillance states may encounter periodic black-outs if people jailbreak their phones with the latest LLM knowledge).
Politicians will try desperate things like criminalizing mathematics...
[hidden]
After he clarified and recanted a HUGE number of implied points in the first comment, my take is it comes down to "currently used encryption may be vulnerable" - essentially an evergreen statement, either due to weakness in the implementation (eg weak iv) or weakness in the maths (eg new mathematical attacks). Neither of these are new or honestly even worth pointing out.
Other than crypto with immutable hashes, the rest of the internet would simply update their systems to mitigate any broken encryption (depending on the risk of the 'break').
TLDR: scary implications make a post popular, regardless of substance.
[3 comments hidden]
[2 comments hidden]
[hidden]
If anything, you should be stockpiling food and guns. Or, who knows, maybe GPUs and DRAM. Physical possession of goods, not paper ownership of the same.
Debt only exists by the mutual belief of debtors and debtees that the alternative would be worse.
[3 comments hidden]
[hidden]
The thread has no coherent argument or new evidence at all but this simple truth must be drilled into the heads of the mathematicians, and whoever is next on the chopping block. Stochastic parrot with high gF will emerge one way or another, and you will like it.
[7 comments hidden]
But this is a great example on why appealing to authority is a mistake and how academia is full of charlatans.
Only way I see that happening is if (big f... if) P = NP and some superintelligence devises a general algorithm to solve one on the other; but he's obviously not referring to that, as the timeline in that context is the next 1-5 years, i.e. the models we have now.
Edit: Lmao, the guy namedrops MLWE and ECDLP to save face, under the argumentation that he's worried about the public key algorithms out there when the "market share" of those algos is like 5%. RSA and ECC still rule the world and no amount of AI will "break" them.
To be generous to the guy, he had a point, but went hyperbole, and also packing that into a scant sentence didn't help make his case.
[4 comments hidden]
Can you show a formal proof of this, or is this belief based in faith?
[3 comments hidden]
1. Build factor pair so large it takes all atoms in the universe to store it.
2. Since there's no room for anything else, nothing can factor it.
:^)
[hidden]
But yeah its easy math, lets say the pair is 1,000,000. Thats 1,000,000! possible combinations. You could stack 1,000,000 PB drives across the universe and not be able to store all the unique combinations.
[2 comments hidden]
This has never been proven. The entire point of the post is that all of public key cryptography is based on a small number of "hard" problems for which we have no deep reason to think are hard. In the pre-AI world, that was a pretty safe situation to be in. Math is a very old field, so the pace of progress was a known quantity. If we started to solve those hard problems, there would be plenty of time to find new ones before they all went away. With AI, the pace of math in the medium term is a much more unknown quantity; so the possibility of loosing all of them before we have time to find a new one is much more of a possibility.
> RSA and ECC still rule the world and no amount of AI will "break" them.
RSA has been theoretically broken for decades, as it is based on integer factorization, which is known to be vulnerable to quantum computers. Even if we ignore quantom computers, we still have no solid reason to believe that there are no solutions to integer factorization that can be realized on normal computers. At best, that gets us to 3 hard problems.
ECC is based on the assumption that ECDLP is a hard problem; and was deployed because we were concerned that integer factorization was broken.
MLWE is the backup plan if ECDLP ends up being broken.
[hidden]
But there are solutions to integer factorizatiom that can be realized on normal computers ... just not in a practical way that doesn't take you a million years.
That doesn't make RSA "broken", this was known from day one. Sure, quantum "might crack those one day" with a lot of emphasis on "might" and "one day".
Your comment is otherwise good but not knowing such basic stuff undermines your position, tbh.
[9 comments hidden]
> folks, Matt Green is not predicting that public key crypto will be cracked, he's predicting it will be regulated out of existence because LE will have no means to break into systems once we fix all the bugs https://bsky.app/profile/ver.ooo/post/3mxfbhrmk2c2u
socializer has already shown up in comments to correct this, and has a good twitter link from an hour ago, clarifying the post was really about ai math attacks possibly damaging some of the rare couple of cryptoanalysis attacks out there:
> These problems (right now basically MLWE and ECDLP with LWE and syndrome decoding as backups) have been extensively analyzed by humans. We felt good that the best known attacks were the best attacks. But we’re learning that human mathematical analysis isn’t the gold standard.
----
thankfully i think it's unrelated what else has happened in the last 24hr:
> If you haven’t asked abliterated GLM 5.3 to hack the Internet’s core routers, then you’re a happier person than I am right now. https://bsky.app/profile/matthewdgreen.bsky.social/post/3mxd...
and then oh look, a couple hours latter:
Critical Cisco Nexus Flaws Let Unauthenticated Attackers Execute Code With Root Privileges https://cybersecuritynews.com/critical-cisco-nexus-flaws/
[6 comments hidden]
That's conspiracy nonsense from the usual paranoid corners of the internet.
[2 comments hidden]
what happens is anyone's guess. (those who know certainly aren't gonna talk to us plebe public about it, haha yeah never.) but generally i think governments have been very much on the warpath to grab control, adding age (and thus identity) verification to basically all websites, and otherwise doing all they can to increase their ability to dragnet the internet and monitor it.
your accusation that it's conspiracy nonsense does indeed some what check out with me. i'm a fan of not going glonzo. i'm a fan of keeping our head and being realistic. it might not go so bad. but also: these people have done nothing to earn the public's trust. their attempts to make the internet bad and un-private have dragged on for decades, and they lose and they lose and they lose. but eventually they get a shot through. they get lucky and it gets worse. there's been very little ratchet the other way, just a general ratchet of loss and woe for the public, for privacy, for electronic freedom frontiers. the governments have not played nice at all, have demonstrated no interest in listening to the public, have disregarded all advocacy, and keep passing bad no good very bad laws, trying with persistence until eventually they find a chink in the armor.
so yes this is a glonzo theory. somewhat. i somewhat agree. but looking at who we are looking against, how things have gone, well: it seems all too realistic.
as for "usual paranoid corners of the internet" i think you are completely fucking off base out of your mind. this is from someone very respected very in the know and very good and very serious and you're just some shithrower with nothing to say. this kind of vacuous uncontestable low grade bullshit can go piss right the fuck off.
[2 comments hidden]
Europol calls privacy-enhancing technologies, or PETS, the tools of criminals:
“PETs are used by criminal actors for secure communication, anonymisation, and protection of data. Criminal networks utilise various PETs, including end-to-end encrypted messaging apps, encrypted phones, and virtual private networks (VPNs), to communicate securely and anonymously. “
"For this reason, lawful access to electronic evidence has become one of the most critical issues for European law enforcement"
https://www.europol.europa.eu/cms/sites/default/files/docume...
Meanwhile Canada just banned e2e and Signal is leaving the country.
[hidden]
But we'll need some decentralised ones. Signal leaving Canada is exactly the problem with centralised networks like theirs: there's a single entity to go after for compliance. So they can be forced just like telegram was forced by Durov's arrest in France.
But there's already good options that aren't centralised. I think people will move to those. At least that's what I will do and I hope most people follow suit.
[hidden]
You're responding to speculation about a vague tweet with more baseless speculation from a third party. He actually explained what he meant, and he did mean the advances in AI math. But he was also baselessly speculating, so I guess it's the circle of life:
[hidden]
> So what does “losing public-key [encryption]” mean? It does not mean cryptography or encryption is impossible, or that we live in Minicrypt. It does mean that we imminently see new cryptanalytic results that substantially improve our ability to attack standardized schemes.
> The more modest effect of this would be that several schemes we’d previously agreed were “good enough” (128 bit security level) aren’t. Maybe they’re 96-bit or 108-bit secure.
> In any case, honest standards bodies have to step back and deprecate at least those smaller parameter sets, which are already deployed in some live systems. But in principle, we can usually just crank up parameter sizes. Right?
> But crank them up to what? Right now we’re saying we have the right numbers, because humans spent 40 years (or 25 years) studying these assumptions. If suddenly it turns out we were off by 26 bits, that’s obviously not something we can lean on.
> So then, we could lean on the fact that the machines now say they’re stuck — the assumptions at the new numbers seem pretty robust, and no lab is able to make further progress.
> How do you feel about that? I don’t feel great about it. I think nobody will feel good about it.
> And what happens if we tentatively agree to trust that progress has stalled, and then some new internal model makes another step-change jump? We could end up losing trust in these assumptions at any security level except for painfully high ones.
> So again I’m not saying that any of this will happen. What I am saying is that I would be very surprised and pleased to find out that human cryptanalysis (of the non-classified form) handled by a couple of dozen people, turned out to be the best we could ever do.
antics[2 comments hidden]
I think it's fair to say that in the last month we have learned 0 things that would specifically confirm or disconfirm this stated view, either directly or indirectly. And that is not really Matthew's concern, anyway. His actual concern is that computers are really good at math, and if we point them at something like Module LWE or ECDLP there is a real chance that it (essentially magically) breaks them. See his statement at [1].
For better and for worse I think we are in a crisis of empiricism. As a community we are worried enough about the outcomes of breaking something like encryption that we're willing to admit statements like this one, even though we have no real, actual, concrete evidence that would indicate whether they're true or not. The line of thought Matthew articulates here (i.e., we can solve millennium problems thus "optimism [related to encryption] is a very opinionated bet") may be defensible from a risk management perspective, but it is absolutely not defensible as a statement of knowledge. Internally that's fine, but the public (including the technical public) is not going to make that distinction. They will interpret it as knowledge. That does not help us.
[1]: https://x.com/matthew_d_green/status/2108281944291393983
DoctorOetker[hidden]
of course it is questionable they would just dump cryptographic breakthroughs in some random batch of breakthroughs ...