Hacker News Reader

Comment by slashtrends | Hacker News Reader

Part of the problem with the current centralization of the world's math capability within AI labs is that if they do find that P=NP via an efficient algorithm, it could have implications on all modern public key based cryptography. So it's not completely clear that they will (be allowed to) release these results.

View on HN

> if AI frontier labs do find that P=NP via an efficient algorithm, it could have implications on all modern public key based cryptography.

The fact that other math problems are bulk solved yet nothing from cryptography was released/published as solved could be a strong indicator that "all modern public key based cryptography" could have been at risk.

Or it could indicate that more resources have been put into cryptography than most other math fields, so AI hasn't yet caught up to our progress.

Also most of the results come from "spray attacks". In addition to the results that are found there are also tons of failed attempts on other problems. So merely through how large the whole space is one should not necessarily expect groundbreaking results in cryptography specifically (even though it can also be true that some results be withheld, at the same time).

It seems rather unlikely that solving the Navier-Stokes problem is harder than e.g. a better attack on a reduced-round AES. Perhaps they think an epsilon improvement in the exponent isn't worth publishing, but it seems more likely that they're intentionally withholding any results they have.

Maybe I'm misunderstanding you, but a better attack on a reduced-round AES has been achieved by LLMs. Anthropic did it and published it already, a chosen plaintext attack that improves on state of the art against reduced-round by "200-800x". https://anthropic.com/document/aes_mobius_bridge.pdf

It's a reasonable assumption that the cases where the NSA, etc, had a role in designing cryptographic systems, and reportedly made specific suggestions that could be forms of a backdoor, would all be revealed by AI being tasked to find it. Maybe even indirectly as part of the broader defensive security research by models unreleased to the public. If algorithmic complexity or a really obscure backdoor has existed in cryptographic systems and put there by the Gov't, it seems that current frontier models would have the best chance of revealing it.

Either that or they've not put the model(s) on those problems. Remember that even the Navier-Stokes solution did use a large amount of compute. I'm not sure they'd even want to waste it on problems that they can't get PR from.

> The fact that other math problems are bulk solved yet nothing from cryptography was released/published as solved could be a strong indicator that "all modern public key based cryptography" could have been at risk.

“Could be”, but I think the correct way to describe it is “the general public doesn’t know”. It could be any of

- they tried very hard without finding weak spots

- they tried for a while, and gave up because the LLMs didn’t even produce leads

- they tried, found something and kept it for themselves

I think the first is not unlikely. Before LLMs, the likes of the NSA must have looked really hard into these problems, and IMO it’s not likely they found something substantial (if they did, their counterpoints in other large countries likely would find it, too, and some of them would have used that knowledge)

"They've specifically avoided trying" is also a possibility. Because what do they do if they actually find a critical flaw? Publishing leads to mass chaos. If they don't publish but it leaks, also mass chaos. (Probably just leaking the existence is enough without the actual proof). If they're "responsible" and report it to NSA, there's a good chance that model development gets forcibly halted and some chance that the entire company gets seized on national security grounds.

The issue is that if a country's agencies find an efficient attack to modern public key based cryptography with LLMs, there is no reason to think that other countries will not find the same in a few months with their LLMs. So, finding a vulnerability could offer a short term advantage, but one would want eventually to protect their own, too.

> it could have implications on all modern public key based cryptography

Here's a nice low-budget scifi movie about this:

https://en.wikipedia.org/wiki/Travelling_Salesman_(2012_film...

https://www.youtube.com/watch?v=OgeyHkP6i3g (full movie)

This is also the premise of Sneakers. I don’t think they prove P=NP, but it’s inferred they find fast factoring (although never explicitly).

Also "Silicon Valley"

This is a book about this:

https://www.goodreads.com/book/show/37986693-factor-man

That premise is great.

I think a proof of P=NP via a galactic algorithm is far more likely than a proof of P=NP via an efficient algorithm.

I mean if someone develops an O(n^100) algorithm for solving an NP-complete problem, that would prove P=NP, but pose no immediate threat to cryptography.

It increases risk, in that a galactic algorithm increases the odds that an efficient algorithm exists waiting to be found, but it is entirely (epistemically) possible that the galactic algorithm exists but the efficient algorithm doesn't.

And vise versa, a proof that P!=NP do not exclude an algorithm that is fast enough for practical n.

Maybe, but that feels significantly more exotic and unlikely to me. You have to basically negate the natural cost scaling of brute force in the thousand to million n range but lose that speed benefit later.

Well, if someone found a quasipolynomial time algorithm – O(n^log(n)) – for an NP-complete problem, that would technically be compatible with P!=NP, but might have quite significant practical implications.

To have a really big impact you'd have to have that be the dominating factor at lower n and keep that "log(n)" part of the equation below 10 or so for all practical n. The latter one in particular seems unlikely to me.

if someone finds a O(n^100) algo for NP complete problems, the obvious next step is to start lowering that 100 exponent.

Given the current developments, I would not be confident that it would not lower dramatically pretty soon.

The 2012 movie "Travelling Salesman" is a thought provoking film that explores this scenario.

Reply on news.ycombinator.com