38
$\begingroup$

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

Improve this question
$\endgroup$
1
  • 2
    $\begingroup$ I'm not enough of an expert to answer, but I thought you might like to know that at the first Barriers in Complexity Workshop, Impagliazzo called for a research program very much in line with your question. Call "Earth-like oracles" oracles in which the same complexity theorems hold that hold in the "real" unrelativized world we live in. Then study the properties of these oracles that are kinda like the real Earth. So, in that framework, your question becomes, "What does an oracle have to satisfy to be Earth-like?" $\endgroup$
    – Aaron Sterling
    Commented Sep 6, 2010 at 15:23

2 Answers 2

Reset to default
33
$\begingroup$

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.

Improve this answer
$\endgroup$
1
20
$\begingroup$

Good question, but scientist have not been able to even separate "Algorithmica" from the remaining cases, let alone decide the exact world we live in.

That said, there are several research papers on the subject. See for example: On the possibility of basing Cryptography on the assumption that P != NP by Goldreich and Goldwasser, and references thereof.

See also On basing one-way functions on NP-hardness by Adi Akavia et al.

In addition, it is well known that decoding some cryptosystems is NP-hard (See, for example, the McEliece cryptosystem, or Lattice-based cryptography). I don't know why this does NOT resolve the problem, since I'm not familiar with such cryptosystems.See Peter Shor comments below.

I also suggest you take a quick look at the discussion at Stackoverflow. Reviewing the literature which cites Impagliazzo's work can also be instructive.

EDIT: The following results might be of interest:

Feigenbaum and Fortnow. Random-Self-Reducibility of Complete Sets. SIAM Journal on Computing, 22:994–1005, 1993.

Bogdanov and Trevisan. On Worst-Case to Average-Case Reductions for NP Problems. In Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, pages 308–317, 2003.

Akavia, Goldreich, Goldwasser, and Moshkovitz. On Basing One-Way Functions on NP-Hardness

Gutfreund and Ta-Shma. New connections between derandomization, worst-case complexity and average-case complexity. Tech. Rep. TR06-108, Electronic Colloquium on Computational Complexity, 2006.

Bogdanov and Trevisan. Average-case complexity. Found. Trends Theor. Comput. Sci. 2, 1 (Oct. 2006), 1-106. DOI= http://dx.doi.org/10.1561/0400000004

Improve this answer
$\endgroup$
3
  • 7
    $\begingroup$ The McEliece cryptosystem is not a cryptosystem; it is a whole family of cryptosystems, depending on which class of error-correcting codes you use in it. If you use arbitrary error-correcting codes, then it is NP-hard to break, but it is also NP-hard to decode a message. If you use a class of error-correcting codes that has a polynomial-time decoding algorithm, then it is indeed polynomial-time to decode the message, but we no longer have a proof that breaking the cryptosystem is NP hard. The situation with lattice-based cryptography is better, but it's still not NP-hard to crack. $\endgroup$
    – Peter Shor
    Commented Feb 8, 2011 at 17:03
  • 1
    $\begingroup$ @Peter: Thanks a lot! You solved a puzzle intriguing me for a long time! $\endgroup$
    – Sadeq Dousti
    Commented Feb 8, 2011 at 19:16
  • 1
    $\begingroup$ In fact, it appears that for some families of error-correcting codes, the McEliece cryptosystem has been broken, although not for Goppa codes, which were in McEliece's original proposal. $\endgroup$
    – Peter Shor
    Commented Feb 8, 2011 at 21:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.