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.
> 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
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.
I'm not saying diversity is good, I'm saying that the community's preference for a single strand of work does a lot to explain why real crypto systems are based on a very small number of problems.
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.
Not a mathematician, but wouldn't a non-constructive proof would shed some light on the problem so that a constructive proof can be found? In my understanding, computational complexity has a lot of questions we have no idea how to approach, such as P vs NP, and certainly a non-constructive proof -- even of a simpler related problem -- would be quiete handy. Moreover, you seem to have this notion that the only immediate application of computational complexity is cryptography, but this is not necessarily true. Solving problems of computational complexity can help other not-so-related fields of CS such as ML or systems. One immediate reason is that a lot of very fundamental problems are NP Complete, such as graph coloring which appears everywhere in CS such as systems or compilers (e.g. register allocation). Of course most of these problems are probabilistically "solved" with very good heuristics, but this doesn't invalidate further research.
> “wouldn't a non-constructive proof would shed some light on the problem so that a constructive proof can be found?“
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.
> I don't really feel like the pure knowledge of what world we live in by itself would have much impact.
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.
> 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!
Fascinating stuff. Wonder if one could decisively prove that the world matches one of Impagliazzo's possibilities if and when P != NP is proved. Question for another time, I guess, but important nonetheless.
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.