The Philosophy of Computational Complexity
ristret.com
ristret.com
If we somehow got a constructive proof that was useful, in anything less than Polynomia, it would probably have the effects being discussed.
But if the proof is not constructive, and doesn't really shed any light on how to concretely attack real cryptosystems, then it basically doesn't matter because it's still basically dependent on whether anyone can come up with a groundbreaking advance and keep it secret.
I think it also over-estimates the value of unbreakable crypto over unbreakable by your average criminal organization crypto. While we have good crypto, our computing systems are woefully insecure, and you can't have meaningful secrecy if your client is hacked, and yet we're largely doing fine. We have breaches and outbreaks, but they're nowhere near so bad that we're rethinking this whole tech thing. So if we can keep crypto to the level of breakage we have now with security, well, we're no worse off than we are today.
And practically, I think we'd be far better off than compared to today's security where we have tonnes of monthly patches by every vendor.
I think the difficulty of creating cryptosystems is a bit exaggerated in this piece; I think we haven't seen much diversity in the past, because diversity was bad for public cryptanalysis, but there are six different approaches listed on the wiki for post-quantum crypto: https://en.wikipedia.org/wiki/Post-quantum_cryptography#Algo...
One of which is pure-symmetric crypto infrastructure.
It was certainly interesting reading about the different worlds we could be in, and knowing this would be worthwhile, but I don't really feel like the pure knowledge of what world we live in by itself would have much impact.
The difficulty is not really exaggerated, and diversity is still bad for public cryptanalysis. The main approaches of post-quantum cryptography utilize very advanced mathematics and very different algebraic structure. We can use basic probability theory and game theory for basic modeling, but it's very hard for us to compare and contrast relative security for algorithms variously built over polynomial rings, modules, Galois groups, lattices, supersingular elliptic curves and error correcting codes. There is some linear algebra featured in all of this, but very few people are sufficiently well trained in all of these mathematics to consider them on equal footing.
Researchers don't like this diversity. It's hard to competently analyze the advantages and disadvantages of systems with wildly different mathematical underpinnings, and you have to keep up with a lot of new material just to stay competitive. In contrast the literature for hashes, block ciphers and stream ciphers is relatively sane and unified; and at least for classical public-key cryptography you only really have to wade into number theory. The result is that the research landscape of post-quantum cryptography is pretty fractured into tribes of mathematical lineage.
But, if these problems were found to have solutions that resulted in practical attacks, I don't think we would have as much difficulty finding a new problem to hang crypto on. Or at least not as hard as this article makes out by suggesting there are only 2 mathematical problems underpinning all of public key crypto.
This is not necessarily true. Common examples where it doesn’t work that way usually involve proof by contradiction, like in the Brouwer Fixed Point Theorem. The steps of the proof only refute the non-existence of the fixed point, and don’t really offer any constructive insight into how the fixed point can be algorithmically located in general.
Other examples include many elementary calculus theorems, like the intermediate value theorem and Cantor’s diagonalizatiom theorem that the real numbers are uncountable. By extension you can think of the standard proof that the Halting Problem is undecideable as non-constructive.
In complexity theory there are also tricky non-constructive “almost proofs” that are used for intuition a lot.
One example is that it is believed that NP != co-NP. By “contradiction” you can show that if a problem was both NP-complete and also in co-NP, then NP == co-NP. Because of this, when theorists encounter a problem that is in both NP and co-NP, they treat this as “evidence” that the problem is not NP complete.
Overall, sometimes a non-constructive proof offers insight to think of a constructive proof. But often it does not provide any such information.
There is even the branch of logic called intuitionism, which uses the Principle of Explosion to effectively disallow proof by contradiction, which is related to the subset of mathematicians who will only treat fully constructive proofs as acceptable.
If we live in a world where P=NP, I think there would be a fury of changes in crypto, because a constructive proof wouldn't be far behind. Once people know something is possible, they quickly find a way to do it.
[1] Aaronson, Scott. Why Philosophers Should Care About Computer Science. https://www.scottaaronson.com/papers/philos.pdf
> First, computational complexity is not well-understood outside of computer science, and this is a pity. Philosophers in particular should pay more attention to computational complexity!
It doesn't count if it's your own fork...
Great post. I never saw much point in the question, before. I'm still skeptical, but at least it gives a plausible scenario.
I’m not sure quite how to parse that. Especially coming from what appears to be an armchair physicist.