> mathematical impossibility of reversing some integer/mod calculation
No, there's no proof that most crypto "calculations" are impossible to reverse. That's why algorithms got weakened by researchers regularly. As of now, it's totally possible someone finds an algorithm to break a next one tomorrow. They just haven't found it yet.
Talking about proofs, there is no proof that just because AI found counter example for a conjecture, it can break math behind cryptography The belief that "if it did A and B it can do C,D,E ,,,Z" is what is driving the current AI hype.
> there is no proof that just because AI found counter example for a conjecture, it can break math behind cryptography
Of course there isn't, nothing like that could be formally proven. But that is neither here nor there.
The important issues remain:
1. Whether some as yet unknown technique exists for efficiently breaking a code.
2. If the answer to (1) is yes, whether LLMs can find it at a reasonable cost.
TTBOMK we still don't know anything about (1). I think the answer to (2) is "probably yes".
When we're talking about things like AES and SHA2, a common answer among experts to (1) is "probably no".
(That's not a common answer to the same question about, say, ECDLP, even leaving quantum aside).
Also AI seem pretty good at constructive proofs.
Most of the breakthroughs so far have been finding counter examples. They can just search tirelessly to find one. Finding a good algorithm (maybe even one faster than people assume is possible) seems the obvious next step for them (as opposed to more conceptual proofs e.g. existance or non-existence where they still aren't quite terrifyingly good).
The phrase "for all we know some undergrad might find a counter example" is the new "it works for n<100 so I don't see why it won't continue indefinitely".
> That's why algorithms got weakened by researchers regularly.
That's the 3rd point. correctness of the algorithms.
There is no such thing. There is just more thorough and less thorough bit-blending. Have a look at any symmetric encryption algorithm or secure hash - there's no magic there, they just do a bunch of stuff to thoroughly mix up all the bits. In the case of symmetric encryption, they constrain it to reversible mixing primitives. And cryptographic experience has shown how much mixing is enough mixing.
A few basic things are known - for example, you can't make a symmetric cipher with just bitshifts and XOR, because then linear algebra techniques can trivially reverse it.
If there is no such thing, how have people found weaknesses in various cryptographic algorithms over the years? The weaknesses are incorrect algorithms.
They haven't. Excepting RC4, which is wildly different from every other mainstream cipher, the track record of practical block cipher cryptanalysis (of core algorithms) is meager. If you redesigned DES so that it had 16-byte blocks and keys and the round structure to match, but retained the rest of its core design decisions, it'd presumably be viable (if slow).
You have a maze (a really, really complicated maze).
Two cases: 1) you have to find a route to the middle 2) someone gives you a route to the middle and you have to validate it
It’s not proven that case 2 is necessarily easier than case 1. But logic and every case in the history of computing suggest that it is.
I don’t see how LLMs could possibly change that fact