I think we might lose public key cryptography
twitter.comJust to be absolutely clear, the giant OpenAI math dump replaces two (2) already efficient probabilistic algorithms with deterministic ones. Neither affects encryption as it is deployed today (one is a quantum algorithm, and the other is factorization over prime fields).
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
i hope we first lose people who post dumb essays on twitter.
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.
I hope we first lose people who post on twitter, as I can't read the replies
I agree, but this link worked for me:
https://nitter.meowing.monster/matthew_d_green/status/210827...
This is essentially a guess that P probably = NP.
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.
a specific hardness assumption is much less general than P=NP, in case you are interested in hardness assumptions and not only P vs NP
Counter theory: No we won't.
Seems pretty un loseable to me as well
This is just clickbait. Nothing to see here. Move along.
Markets are down today over nonsense stargazing like this. If we lose cryptography, we lose everything in a sort of blackout level event like on Blade Runner 2049. It won’t matter what you buy or sell to. I see no signs we are even close to that.
What a deeply ignorant statement. There are no shortcuts to factoring a (sufficiently large) number, and that's not even touching on other kinds of PKC.
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.
> betting against models and in favor of human intelligence being the limit has not worked well for any of us.
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.
some already refuted speculation online about what this was, that i found informative & interesting & real to our times [edited, originally intro text read: "to clarify"]
> 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/
> 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
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:
Later in the linked Twitter thread: https://twitter.com/matthew_d_green/status/21082828173438241...
> 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.
>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
That's conspiracy nonsense from the usual paranoid corners of the internet.
Europol, a tax funded law enforcement body, is publicly lobbying exactly this.
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.
They can stick their chatcontrol where the sun don't shine, I don't expect people to play along with it. People will just move to apps that don't play ball with these backdoors.
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.
it's speculation about behavior. and it's grounded in a very real truth, that law enforcement in many nations has not been impeded by security / cryptography: they've had the means to break it, route around it. the assertion that this is changing feels imminently clear.
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.
It's conspiracy nonsense, because it wasn't what Green said.