In the recent Signalgate scandal, several senior Trump administration appointees used the Signal app on their phones to discuss an attack on the Houthis. People discussed the risk of the phones being compromised or human factors, such as adding a prominent journalist to the group chat by mistake. But mostly no one had concerns about the cryptography itself on this widely-available app.
It wasn't always this way--cryptography used to be a cat and mouse game, most notably the breaking of the German Enigma machine dramatized in the movie The Imitation Game. Then Diffie and Hellman in their classic 1976 paper stated
Theoretical developments in information theory and computer science show promise of providing provably secure cryptosystems, changing this ancient art into a science.
And in recent memory we've had several successful cybersecurity attacks, but never because the encryption was broken.
We've made incredible progress in solving problems once thought unsolvable, including language translation, chess, go, protein folding and traveling salesman. We have great SAT and Mixed-Integer Programming algorithms. We've blown through the Turing test. None of these algorithms work all of the time but no longer do hard problems seem so hard. Yet cryptography remains secure. Why? How did we get to this Optiland, where only the problems we want to be hard are hard? Quantum computers, if we have them can attack some cryptographic protocols, but we're a very long way from having those capabilities.
My latest theory involves compression. Machine learning works by finding a representation of a function in a neural net or other form that gives an imperfect compressed version of that function, removing the random components to reveal the structure inside. You get a smaller representation that, through Occam's Razor, is a hopefully mostly accurate version of that data. For example, we learn the representation of a Go player by training a neural net by having the computer play itself over and over again.
Cryptography is designed to look completely random. No compression. If you remove the randomness you have nothing left. And thus modern algorithms have no hook to attack it.
This is just the beginnings of a theory. I don't have a good formalization and certainly not even the right questions to ask of it.
So to me it's still a big mystery and one that deserves more thought, if we really want to understand computational complexity in the world we actually live in.
R. Ahlswede used to say that "Bad Codes are Good Ciphers", and wrote a paper about that (Problems of Control and Information Theory 11.5 (1982)). Seems somewhat related to what you say.
ReplyDeleteYou cant break “Crytptography” because that’s not how you spell Cryptography
ReplyDeleteThanks. I fixed the title.
DeleteRe: "I don't have a good formalization and certainly not even the right questions to ask of it." -- do you feel average-case hardness is not good enough? Even though we don't provable avg-case hardness for factoring or discrete log (under the distributions that matter), we do have it for some of the post-quantum crypto-systems (which aren't mainstream yet, anyway), starting with Ajtai's reduction from worst-case to avg-case hard instances of lattice problems.
ReplyDeleteI thought the difference between SAT and FACTORING is that its easy to genrated hard instances of Factoring, but its hard to generate hard instancs of SAT (except those that come from factoring). Is that relevan there?
ReplyDeleteWhat about the planted clique problem? People have looked at cryptography based on planted cliques.
DeleteMy intuition is: To make a certificate, you make a random graph, with a planted clique. The resulting graph is a "public certificate"; to log into a server, you send the vertices of the planted clique. (Obviously, there's then the problem of how you send the vertices securely.)
That's only my intuition; I haven't read the above paper...
Designing an algorithm to solve a problem can be seen as the process of compressing the range of possible solutions to that problem. The complexity of a problem is rooted in its inherent randomness, which can render it incompressible. The fundamental question, therefore, is whether it is feasible to establish that a problem is inherently incompressible.
ReplyDeleteI don't think it is surprising at all.
ReplyDeleteIt is also not just crypto. The information density of tasks that humans typically do like natural language is pretty low. Models with billions of parameters can learn them easily.
Try asking an LLM to multiply two 20 digit numbers without using tools. Even the latest models fail on such talks.
Here is how I explain my intuition to people:
Multiplication problem has a very high entropy, so the model cannot memorize them. Each digit of the result is highly dependent off previous digits, so it is not local. These models fail in predicting digits with some small probability. The chance of it failing for some output digit grows exponentially. So what happens is that we get the first and the last digits right but at some point it makes a mistake and then it gets the rest wrong.
You might be able sparsify and do error correction, that is too some extent what thinking and reasoning models do, but they still cannot multiplication.
When they cannot solve multiplication, we don't even need to talk why they cannot solve crypto problems.
Have you ever discussed this with Michael Kearns? His PhD thesis The Computational Complexity of Machine Learning (1989) still seems to be the best reading on the topic.
ReplyDeleteOn a slight tangent: would proving that P!=NP also prove that any cryptography is more secure? (I mean, presumably if it were proven that P=NP, constructively enough to give an algorithm with reasonable constants, that would break a lot of crypto.)
ReplyDeleteBreaking AES, or factoring, or even quantum-proof crypto can be coded up as SAT instances. Presumably even if it were shown that P!=NP, these SAT instances might somehow be easier.
You called??? Anyway, as I've said before...
ReplyDelete"For example, we learn the representation of a Go player by training a neural net by having the computer play itself over and over again."
Not quite. First, the history.
The Google program that first beat one of the world's strongest players was essentially a reimplementation of then-current Go programs, one of which, running on a PC (without a GPU), had just beaten a retired Japanese professional. Google's initial "intellectual contribution" to Go programming was to demonstrate that throwing a server farm at the problem resulted in stronger play.
Google's following work on Go programming, though, was significant. In addition to figuring out how to make better use of neural nets, they showed how to learn (through self play) the neural net parameters for the _Go-specific neural nets used_. And made other improvements. And published this work so others could reimplement it. Thank you, Google!
(Thanks to Google's work, nowadays a PC with a midrange GPU (e.g. 3080 or 4070) plays super-human Go. No need for a server farm.))
But note the "Go-specific" bit in there. The learning programs start with the world's strongest Go program (i.e. they know exactly what to learn) and figure out how to make those Go-specific structures either work (starting from zero) and/or then work even better.
From start to finish, the self-play learning thing is exactly and only learning parameters for Go-specific evaluators.
Thus the idea that "a neural net learns a model of a Go player" is technically, intellectually, and philosophically problematic. That ain't what's going on, at all.
What if we could break cryptography. In public key cryptography, we assume integer factorization and discrete logarithm are intractable. If we know how to solve efficiently an NP complete problem, for example, SAT, Hamilton cycle, or traveling salesman, we can easily solve integer factorization and discrete logarithm.
ReplyDeleteI found an efficient algorithm for the traveling salesman problem with distances a and b. I am working on factoring RSA numbers that haven't been factored yet (there are 31 of them). I aim at solving them all as their factorization can be done in a short time. For example, factoring RSA260 should take less than an hour.
Hopefully, by the end of this month, I'll start announcing the factorizations on my blog.