Impagliazzo's Five Worlds
To motivate the structural study of average case complexity, Russell Impagliazzo, introduced five worlds.[1] The five worlds are meant to illustrate the consequences of different possible answers to some of the central questions in average case complexity. In each world, Impagliazzo analyses the effect on cryptography and algorithm design. To make the repercussions more vivid, he discusses the fate of Professor Grouse—the teacher who famously assigned young Gauss the task of summing numbers from 1 to 100 which Gauss immediately solves. Of Impagliazzo's five worlds, two—Minicrypt and Cryptomania—are widely quoted and studied in the cryptography literature. In 2021, their quantum generalisations were shown to behave qualitatively differently from their classical counterparts.
The Five Worlds[edit]
| World | Characteristic | What would it take to prove? | Grouse and Gauss |
|---|---|---|---|
| Algorithmica | P=NP, or any "moral equivalent" e.g. NP ⊆ BPP. | ||
| Heuristica | NP problems are hard in the worst case but are easy on average for any samplable distribution. | ||
| Pessiland | Hard average case problems exist but one-way functions don't exist. | ||
| Minicrypt | One way functions exist but public key cryptography is impossible. | ||
| Cryptomania | Public key cryptography is possible. |
Effect of Quantum Communication and Computation[edit]
It is widely believed that one-way functions are by themselves insufficient to construct public key cryptography (i.e. Minicrypt). In particular, this means that Minicrypt does not contain secure multi-party computations. However, with quantum communication, it has been shown that one way functions suffice to perform secure multi-party computations---quantum Minicrypt is very powerful.[2] In fact, assumptions potentially weaker than one-way functions (e.g. pseudorandom states) can also be used to perform secure multi-party computations.[3]
References[edit]
- ↑ Impagliazzo, R. (June 1995). "A personal view of average-case complexity". Proceedings of Structure in Complexity Theory. Tenth Annual IEEE Conference: 134–147. doi:10.1109/SCT.1995.514853.
- ↑ Grilo, Alex B.; Lin, Huijia; Song, Fang; Vaikuntanathan, Vinod (2021). Canteaut, Anne; Standaert, François-Xavier, eds. "Oblivious Transfer Is in MiniQCrypt". Advances in Cryptology – EUROCRYPT 2021. Cham: Springer International Publishing: 531–561. doi:10.1007/978-3-030-77886-6_18. ISBN 978-3-030-77886-6.
- ↑ Ji, Zhengfeng; Liu, Yi-Kai; Song, Fang (2018). Shacham, Hovav; Boldyreva, Alexandra, eds. "Pseudorandom Quantum States". Advances in Cryptology – CRYPTO 2018. Cham: Springer International Publishing: 126–152. doi:10.1007/978-3-319-96878-0_5. ISBN 978-3-319-96878-0.
This article "Impagliazzo's Five Worlds" is from Wikipedia. The list of its authors can be seen in its historical and/or the page Edithistory:Impagliazzo's Five Worlds. Articles copied from Draft Namespace on Wikipedia could be seen on the Draft Namespace of Wikipedia and not main one.
