Impagliazzo, Rudich: “Limits on the Provable Consequences of One-way Permutations”

07.08.2019, 10:00 – 11:00

07.08.2019 10:00-11:00

Speaker: Maximilian Ortl, CAC Group, TU Darmstadt | Location: Mornewegstraße 32 (S4|14), Room 5.3.01, Darmstadt

Organizer: Christian Janson, Cryptoplexity Group, TU Darmstadt


This talk is the fifth one in the seminar series „Reading the Crypto Classics“ for the summer term 2019. The idea of this seminar is to jointly read classical milestone papers in the area of cryptography, to discuss their impact and understand their relevance for current research areas. The seminar is running as an Oberseminar, but at the same time meant to be a joint reading group seminar of the CROSSING Special Interest Group on Advanced Cryptography with all interested CROSSING members being invited to participate.

This issue will cover the paper

Impagliazzo, Rudich: “Limits on the Provable Consequences of One-way Permutations” (CRYPTO 1988, STOC 1989), DOI: 10.1007/0-387-34799-2_2

with the following abstract:

„We present strong evidence that the implication, “if one-way permutations exist, then secure secret key agreement is possible”, is not provable by standard techniques. Since both sides of this implication are widely believed true in real life, to show that the implication is false requires a new model. We consider a world where all parties have access to a black box for a randomly selected permutation. Being totally random, this permutation will be strongly one-way in a provable, information-theoretic way. We show that, if P = NP, no protocol for secret key agreement is secure in such a setting. Thus, to prove that a secret key agreement protocol which uses a one-way permutation as a black box is secure is as hard as proving P ≠ NP. We also obtain, as a corollary, that there is an oracle relative to which the implication is false, i.e., there is a one-way permutation, yet secret-exchange is impossible. Thus, no technique which relativizes can prove that secret exchange can be based on any one-way permutation. Our results present a general framework for proving statements of the form, “Cryptographic application X is not likely possible based solely on complexity assumption Y.“

Further information