<p>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.</p>

<p>That said, there are several research papers on the subject. See for example:
<a href="http://www.wisdom.weizmann.ac.il/~oded/PS/npc-crypto.ps" rel="nofollow noreferrer">On the possibility of basing Cryptography on the assumption that P != NP</a> by Goldreich and Goldwasser, and references thereof.</p>

<p>See also <a href="http://portal.acm.org/citation.cfm?doid=1132516.1132614" rel="nofollow noreferrer">On basing one-way functions on NP-hardness</a> by Adi Akavia <em>et al.</em></p>

<p>In addition, it is well known that decoding some cryptosystems is NP-hard (See, for example, the <a href="http://en.wikipedia.org/wiki/McEliece_cryptosystem" rel="nofollow noreferrer">McEliece cryptosystem</a>, or <a href="http://en.wikipedia.org/wiki/Lattice-based_cryptography" rel="nofollow noreferrer">Lattice-based cryptography</a>). <strike>I don't know why this does NOT resolve the problem, since I'm not familiar with such cryptosystems.</strike>See Peter Shor comments below.</p>

<p>I also suggest you take a quick look at the discussion at <a href="https://stackoverflow.com/questions/311064/are-there-public-key-cryptography-algorithms-that-are-provably-np-hard-to-defeat">Stackoverflow</a>. Reviewing the literature which <a href="http://scholar.google.com/scholar?cites=10491271149759669045&amp;as_sdt=2005&amp;sciodt=2000&amp;hl=en" rel="nofollow noreferrer">cites Impagliazzo's work</a> can also be instructive.</p>

<p><strong>EDIT:</strong>
<em>The following results might be of interest:</em></p>

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

<p>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.</p>

<p><a href="http://www.wisdom.weizmann.ac.il/~oded/p_aggm.html" rel="nofollow noreferrer">Akavia, Goldreich, Goldwasser, and Moshkovitz. On Basing One-Way Functions on NP-Hardness</a></p>

<p><a href="http://www.cs.tau.ac.il/~amnon/Papers/GT.ECCC06.pdf" rel="nofollow noreferrer">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.</a></p>

<p>Bogdanov and Trevisan. Average-case complexity. Found. Trends Theor. Comput. Sci. 2, 1 (Oct. 2006), 1-106. DOI= <a href="http://dx.doi.org/10.1561/0400000004" rel="nofollow noreferrer">http://dx.doi.org/10.1561/0400000004</a></p>

CC BY-SA 2.5
2011-02-08T17:03:36.870Z
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.
Peter Shor 
CC BY-SA 2.5
2011-02-08T19:16:50.930Z
@Peter: Thanks a lot! You solved a puzzle intriguing me for a long time!
Sadeq Dousti
CC BY-SA 2.5
2011-02-08T21:31:50.087Z
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.
Peter Shor 
CC BY-SA 2.5
2010-09-06T16:38:07.893Z
2011-02-08T19:17:45.127Z
2017-05-23T12:40:09.333Z
Sadeq Dousti
<p>About a year ago I co organized a workshop on <a href="http://intractability.princeton.edu/blog/2009/05/program-for-workshop-on-impagliazzos-worlds/">complexity and cryptography: status of Impagliazzo's worlds</a>, and the slides and videos on web site may be of interest.</p>

<p>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. </p>

<p>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.</p>

CC BY-SA 4.0
2019-03-05T16:01:06.360Z
This link may work better: http://archive.dimacs.rutgers.edu/Workshops/Cryptography/program.html
Timothy Chow
CC BY-SA 2.5
2010-09-19T02:06:31.553Z
2010-09-19T02:06:31.553Z
Boaz Barak
<p>In 1995, Russell Impagliazzo proposed five complexity worlds:</p>

<p>1- Algorithmica: $P=NP$ with all the amazing consequences.</p>

<p>2- Heuristica: $NP$-complete problems are hard in the worst-case ($P \ne NP$) but are efficiently solvable in the average-case.</p>

<p>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.  </p>

<p>4- Minicrypt: One-way functions exist but public-key cryptographic systems are impossible</p>

<p>5- Cryptomania: Public-key cryptographic systems exist and secure communication is possible.</p>

<blockquote>
  <p>Which world is favored by the recent advances in computational complexity? What is the best evidence for the choice?</p>
</blockquote>

<p><a href="http://www.computer.org/portal/web/csdl/doi/10.1109/SCT.1995.514853">Russell Impagliazzo, A Personal View of Average-Case Complexity</a>
<a href="http://www.computer.org/portal/web/csdl/doi/10.1109/SCT.1995.514853">, 1995</a></p>

<p><a href="http://blog.computationalcomplexity.org/2004/06/impagliazzos-five-worlds.html">Impagliazzo's Five Worlds,</a>
<a href="http://blog.computationalcomplexity.org/2004/06/impagliazzos-five-worlds.html">The Computational Complexity
     blog</a></p>

CC BY-SA 2.5
2010-09-06T15:23:08.693Z
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?"
Aaron Sterling
<cc.complexity-theory><conditional-results><average-case-complexity>
Status of Impagliazzo's Worlds?
Mohammad Al-Turkistany
# Status of Impagliazzo's Worlds?

(Asked by: username_0 on 2010-09-06)

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](http://www.computer.org/portal/web/csdl/doi/10.1109/SCT.1995.514853)
[, 1995](http://www.computer.org/portal/web/csdl/doi/10.1109/SCT.1995.514853)

[Impagliazzo's Five Worlds,](http://blog.computationalcomplexity.org/2004/06/impagliazzos-five-worlds.html)
[The Computational Complexity
blog](http://blog.computationalcomplexity.org/2004/06/impagliazzos-five-worlds.html)

**Tags:** cc.complexity-theory, conditional-results, average-case-complexity
> **Comments:**
> **username_1**: 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?"  

---

## 2 answers

### Answer by username_4 on 2010-09-19. Score: 33 | Accepted answer

About a year ago I co organized a workshop on [complexity and cryptography: status of Impagliazzo's worlds](http://intractability.princeton.edu/blog/2009/05/program-for-workshop-on-impagliazzos-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:**
> **username_5**: This link may work better: http://archive.dimacs.rutgers.edu/Workshops/Cryptography/program.html  

---

### Answer by username_2 on 2010-09-06. Score: 20

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](http://www.wisdom.weizmann.ac.il/~oded/PS/npc-crypto.ps) by Goldreich and Goldwasser, and references thereof.

See also [On basing one-way functions on NP-hardness](http://portal.acm.org/citation.cfm?doid=1132516.1132614) by Adi Akavia *et al.*

In addition, it is well known that decoding some cryptosystems is NP-hard (See, for example, the [McEliece cryptosystem](http://en.wikipedia.org/wiki/McEliece_cryptosystem), or [Lattice-based cryptography](http://en.wikipedia.org/wiki/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](https://stackoverflow.com/questions/311064/are-there-public-key-cryptography-algorithms-that-are-provably-np-hard-to-defeat). Reviewing the literature which [cites Impagliazzo's work](http://scholar.google.com/scholar?cites=10491271149759669045&as_sdt=2005&sciodt=2000&hl=en) 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](http://www.wisdom.weizmann.ac.il/~oded/p_aggm.html)

[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.](http://www.cs.tau.ac.il/~amnon/Papers/GT.ECCC06.pdf)

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>

> **Comments:**
> **username_3**: 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.  
> **username_2**: @Peter: Thanks a lot! You solved a puzzle intriguing me for a long time!  
> **username_3**: 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.  

---

