# The worlds in which cryptography may or may not exist

# Introduction

If you're a programmer of any sort, chances are you have heard of the $\mathsf{P}$ vs $\mathsf{NP}$ problem many times before. However, have you ever heard of Impagliazzo's Five Worlds or average-case complexity before?

$\mathsf{P}$ vs $\mathsf{NP}$ asks whether the set of problems that can be verified quickly can also be solved quickly. You may also use the mental shortcut of asking whether "difficult" problems can be solved easily, although it is not quite correct since there are complexity classes that are harder than $\mathsf{NP}$. We will be using the words "easy" instead of "P" and "hard" or "difficult" instead of $\mathsf{NP}$ a lot in this post.

What are Impagliazzo's Five Worlds? Impagliazzo's Five Worlds, published (opens new window) in 1995 by Russell Impagliazzo, defines five different scenarios in which cryptography may or may not exist. But wait a second, shouldn't there only be two worlds? $\mathsf{P}=\mathsf{NP}$ and cryptography doesn't exist, or $\mathsf{P} \neq \mathsf{NP}$ and cryptography does exist?

It might be intuitive to think that if $\mathsf{P} \neq \mathsf{NP}$, then cryptography would exist. Intuitively, encryption should be a P-problem and decryption should be a NP-problem, right? Well... that is actually correct, but the problem comes with generating those encryptions that are $\mathsf{NP}$-difficult to decrypt.

You see, even if $\mathsf{NP}$-problems exists, we might not be able to generate new instances of those problems easily. In fact, this is true for problems like Sudoku or crosswords. In order to create a new puzzle of this sort, we need to do a lot of checks and balances to ensure that it will be solvable. Believe me, I tried to create my own Sudoku puzzles as a bored kid in class and I was not able to create one that actually worked.

However, for the prime factorisation problem - which is used in many cryptographic protocols today - it is easy to generate a new instance. We simply multiply any two random (large) primes.

# The five worlds

# Algorithmica

In, Algorithmica, we have the scenario where $\mathsf{P}=\mathsf{NP}$. Most researchers believe this world is very unlikely to be true since we have many examples of $\mathsf{NP}$ problems for which no one has been able to find an efficient algorithm. In fact, it seems quite absurd that anyone might be able to solve a Sudoku puzzle, for example, in just a few steps. In Algorithmica, we obviously won't have cryptography. Anyone will be able to decrypt any information they find.

# Heuristica

Heuristica is the world in which $\mathsf{P} \neq \mathsf{NP}$ and $\mathsf{NP}$ problems are hard to solve in the worst case, but easy on average. Wait, what? Recall that complexity classes like $\mathsf{P}$ and $\mathsf{NP}$ consider the asymptotic complexity for all instances of the problem. In other words, a problem might be easy to solve in most cases, but every there are any instances for which it is hard, then the problem is in $\mathsf{NP}$.

In Heuristica, cryptography still isn't possible. Even though hard $\mathsf{NP}$-problems would exist, we wouldn't be able to find them easily and thus we wouldn't be able confidently create encryptions which we know will be difficult to decrypt.

# Pessiland

In the next world, called Pessiland, cryptography still does not exist 😔. As you can infer from its name, this is Impagliazzo's least favourite world. In Pessiland, there are hard average-case $\mathsf{NP}$ problems, but one-way functions do not exist.

"What are one-way functions?", you ask. One-way functions (OWFs) are functions that are functions that are easy to compute, but hard to invert. One-way functions are the bedrock of modern cryptography. Every time we encrypt anything, a one-way function is used to compute the ciphertext (the encrypted text). Since the ciphertext is the output of a one-way function, it is hard for an adversary to invert (i.e. to decrypt and to read what we encrypted!).

If one-way functions do not exist, there would be no way for us to generate these solved (in this case, encrypted) instances of $\mathsf{NP}$-problems.

# Minicrypt

In the fourth world, Minicrypt, cryptography finally does exist - albeit only private-key cryptography (hence the "mini"). If you haven't heard of private-key and public-key cryptography before, don't worry too much about it for now. Just know while that some cryptography would be possible in Minicrypt, many of the protocols we rely on today for communicating on the internet, won't exist.

# Cryptomania

In the last world, Cryptomania, cryptography in all its forms exists. As you can see, Impagliazzo was very excited about this world. It this world in which we currently think, or at least pretend, we live in. All of modern cryptography in practice is based on the hope that we do actually live in Cryptomania.

What is the difference in the technical assumptions necessary for Cryptomania that does not exist in Minicrypt? Well, I'm glad you asked (or even if you didn't), because I'd like to tell you about my favourite type of function: trapdoor one-way functions. Honestly, what a cool name for a mathematical construct? And it does what it says in the name. Trapdoor OWFs are the same as one-way functions in that they are easy to compute and hard to invert, but they are also easy to invert if and only if you have some secret "trapdoor" information.

Trapdoor OWFs makes public-key cryptography possible. I still remember the uncomfortable feeling of sending my SSH public key to my boss at one of my first internships and wondering how it could be that my public key won't reveal anything about my private key. Your private keys are your trapdoor secrets. When you decrypt something encrypted with your public key, you "open" the trapdoor!

# The new contender: Microcrypt

Impagliazzo theorised that his Five Worlds were the only five possibilities. However, in the last few years, more research in quantum computing has opened up the possibility of a sixth world, Microcrypt. I won't go into much details here, but this Quanta Magazine (opens new window) article explains the lead-up to this discovery.

Essentially, researchers have been working on basing cryptography on quantum computers on mathematical constructs that are "weaker" than one-way functions. Dakshita Khurana and Kabir Tomer succesfully proved (opens new window) in 2024 that if certain assumptions about the relative advantage of quantum computers versus classical computers are true, quantum cryptography can exist if a new construct called one-way puzzles exist (even if one-way functions do not).

# Further reading

Impagliazzo's original 1995 paper (opens new window) is a surprisingly accessible read and the slightly janky, old-school formatting is endearing.

If you prefer something more modern, this article by Quanta Magazine is what originally got me interested in the topic. (Also, please observe (opens new window) the schmodel photos of Impagliazzo on Quanta. I love that Quanta Magazine makes mathematicians look glamorous).