Theoretical Computer Science
- cc.complexity-theory conditional-results average-case-complexity
- Updated Sat, 21 May 2022 18:20:31 GMT
-
Status of Impagliazzo's Worlds?
In 1995, Russell Impagliazzo proposed five complexity worlds:
1- Algorithmica: $P=NP$ with all the amazing consequences.
2- Heuristica: $NP$-complete problems are hard in the worst-case ($P \ne NP$) but are efficiently solvable in the average-case.
3- Pessiland: There exist average-case $NP$-complete problems but one-way functions do not exist. This implies that we can not generate hard instances of $NP$-complete problem with known solution.
4- Minicrypt: One-way functions exist but public-key cryptographic systems are impossible
5- Cryptomania: Public-key cryptographic systems exist and secure communication is possible.
Which world is favored by the recent advances in computational complexity? What is the best evidence for the choice?
Russell Impagliazzo, A Personal View of Average-Case Complexity , 1995
Impagliazzo's Five Worlds, The Computational Complexity blog
Solution
About a year ago I co organized a workshop on complexity and cryptography: status of Impagliazzo's worlds, and the slides and videos on web site may be of interest.
The short answer is that not much has changed in the sense that most researchers still believe we live in "Cryptomania" and we still have more or less the same evidence for this, and not much progress on collapsing any of the worlds for one another.
Perhaps the most significant piece of new information is Shor's algorithm that shows that at least if you replace P with BQP, the most commonly used public key cryptosystems are insecure. But, because of Lattice based cryptosystems, the default assumption is that we live in cryptomania even in this case, though perhaps the consensus here is a bit weaker than the classical case. Even in the classical case, there seems to be much more evidence for the existence of one-way functions ("Minicrypt") than the existence of public key encryption ("Cryptomania"). Still, given the effort people have spent in trying to break various public key cryptosystem, there's significant evidence for the latter as well.
Comments (1)
- +1 – This link may work better: archive.dimacs.rutgers.edu/Workshops/Cryptography/program.html — Mar 05, 2019 at 16:01
External Links
External links referenced by this document: