Impagliazzo’s Five Worlds

Russell Impagliazzo in 1995 published a paper called A personal view of average-case complexity in which he describes possible worlds which we could live in depending on some (still) unproven conjectures in complexity theory. Reviewing it almost 30 years later, understanding the relationships between certain assumptions and the outcomes of the truth or falsity of them is still fascinating.

I think especially considering the worlds from a cryptographer’s perspective is important. It’s useful to know the cascade of assumptions certain primitives rely on and the potential limits of cryptography in certain worlds.

Impagliazzo’s five worlds

Somewhat recently, I was reminded of Impagliazzo’s Five Worlds. The worlds are related to the unresolved problem of P vs NP, which revolves around the language classes P and NP. However, it also distinguishes worlds via the existence of One-way functions (OWF) and Trapdoor permutations (TDP).

In his paper, Impagliazzo illustrates the differences between “worst-case” and “average-case” hardness of problems through his 5 worlds:

• Algorithmica: $\mathbf{P}=\mathbf{NP}$ (or something “morally equivalent”), where we can solve NP-complete problems efficiently
• Heuristica: $\mathbf{P}\ne \mathbf{NP}$ but $\mathbf{NP}$ problems are still easy on average
• Pessiland: $\mathbf{NP}$ is hard on average but OWFs do not exist — Imp95
• Minicrypt: OWFs exist but TDPs do not exist
• Cryptomania: TDPs exist

These worlds follow from the following chain of implications:

• TDP ⇒ OWF
• OWFs exist → NP is hard on average
• NP is hard on average → $\mathbf{P}\ne \mathbf{NP}$

All the propositions in that chain are conjectures at this point, but the implications are true. So, there are 5 possible settings for these propositions, each which corresponds to one of Impagliazzo’s worlds.

A note on hardness

A subtle but crucial point in Impagliazzo’s framework is the distinction between worst-case and average-case hardness.

$\mathbf{P}\ne \mathbf{NP}$ is a worst-case statement: it says there exist some NP problems for which no efficient algorithm works on every input. A single hard instance suffices. This is why Heuristica (where $\mathbf{P}\ne \mathbf{NP}$) can still be a pleasant world for algorithms: hard instances might be rare or contrived.

One-way functions, by contrast, require average-case hardness: the function must be hard to invert on a random input drawn from some natural distribution. An adversary that inverts on even a polynomial fraction of inputs breaks the OWF. This is a much stronger statement than worst-case hardness, and it is not known whether $\mathbf{P}\ne \mathbf{NP}$ implies it.

This gap explains why Heuristica exists: a world where NP is hard in the worst case (so $\mathbf{P}\ne \mathbf{NP}$) but NP is easy on average — meaning random instances of NP problems are tractable — so OWFs cannot exist — Imp95.

There is also work trying to understand if $\mathbf{P}\ne \mathbf{NP}$ actually could imply OWFs exist (or the barriers to trying to prove this):

• GG98
• AGGM06

Beyond the Five Worlds

The worlds laid out by Impagliazzo were useful to illuminate the differences between average-case and worst-case hardness. It also makes it clear how different types of cryptography rely on average-case and not worst-case assumptions.

However, there is a large body of both complexity and cryptography which prove a long list of implications from one conjecture to another. And, I personally think it would be an interesting project (if infeasible) to enumerate and map all of these implications throughout the literature.

Instead of enumerating all of them though, I’ll just discuss a handful of them to illustrate the plethora of possible worlds we (for all we know) could be in.

Breaking up Cryptomania

In his original paper, Impagliazzo actually suggested that Cryptomania includes the existence of OT and HE. However, I’ve simplified the definition to just be the existence of a TDP.

Early work of GKM+00 lays out how these different primitives relate to each other. Importantly, there is a large gap between OWF and TDP in Cryptomania: OWFs imply PRGs, PRFs, SKE, MACs, and digital signatures, but no relativizing construction of key agreement, hence of public-key encryption, from them exists — IR89. TDPs imply PKE — GM84, Yao82a — and enhanced TDPs imply OT — EGL85, Gol04; under black-box reductions neither PKE nor OT implies TDPs, and PKE and OT are incomparable — GKM+00. OT is complete for secure computation — Kil88 — so general secure computation follows from enhanced TDPs — EGL85, GMW87 — and holds in Impagliazzo’s original Cryptomania, which includes OT.

Fully homomorphic encryption (FHE) is an interesting case: it is not known to follow from TDPs alone. Leveled FHE follows from LWE alone — BV11, BGV12; unbounded-depth FHE via bootstrapping additionally assumes circular security — Gen09 — and FHE without circular security follows from sub-exponentially secure iO and slightly super-polynomially secure re-randomizable encryption — CLTV15. Whether FHE follows from Cryptomania (TDPs) is a major open problem.

Obfustopia

Indistinguishability obfuscation (iO) together with OWFs defines an even richer world beyond Cryptomania, sometimes called Obfustopia. iO is an extremely powerful primitive: combined with OWFs, it implies PKE, digital signatures, NIZK in the CRS model, functional encryption for all circuits, deniable encryption, and much more — SW14; FE via GGHRSW13.

iO by itself implies no hardness: if $\mathbf{P}=\mathbf{NP}$, iO exists (output the lexicographically first circuit of the same size equivalent to the input) — folklore. Together with $\mathbf{NP}⊈\text{io-}\mathbf{BPP}$, iO implies OWFs — KMNPRY14. Obfustopia (iO + OWF) implies PKE — SW14 — and, with sub-exponential security, TDPs — BPW16 — so it lies inside Cryptomania; iO alone is orthogonal to the hierarchy.

The first candidate iO construction was proposed in GGHRSW13 based on multilinear maps. A construction from well-founded assumptions — the sub-exponential hardness of SXDH on asymmetric bilinear groups, LWE, LPN over ${\mathbb{Z}}_p$, and a Boolean PRG in NC${}^0$ with stretch $n^{1+\tau }$ — was given in JLS21.

Microcrypt

A surprising recent development is the discovery that cryptographic tasks may be possible without any one-way functions, using quantum information. This hypothetical world — sometimes called Microcrypt — has some quantum cryptography but no OWFs; relative to a classical oracle it is consistent even with Algorithmica — KQST23.

The key insight is that quantum unclonability (the no-cloning theorem) can serve as a cryptographic resource even without one-way functions. For example:

• Private-key quantum money is constructed from pseudorandom quantum states — JLS18; in turn, private-key quantum money with pure banknotes implies OWSGs (QM ⇒ OWSG).
• Pseudorandom quantum states (PRS) exist relative to a quantum oracle under which $\mathbf{BQP}=\mathbf{QMA}$ — Kre21 — and single-copy-secure PRS exist relative to a classical oracle under which $\mathbf{P}=\mathbf{NP}$ — KQST23.

PRS do not exist if $\mathbf{BQP}=\mathbf{PP}$ — Kre21.

The landscape of quantum cryptography without OWFs is mapped out in GMMY24, which identifies a rich hierarchy of quantum cryptographic primitives that may separate Pessiland from Minicrypt in the quantum setting.