We can construct various symmetric key primitives like PRGs, PRFs, SPRPs etc., assuming the existence of either one-way permutations or one-way functions with the former assumption allowing simpler constructions.

However, what is the relationship between one-way permutations and one-way functions? Clearly, the existence of one-way permutations implies the existence of one-way functions. Is the converse true? If it isn't then assuming one-way permutations is strictly stronger than assuming one-way functions.


It was shown by Rudich in his PhD thesis [R] that it is not possible to construct one-way permutations (OWPs) from one-way functions (OWFs) in the framework of black-box reductions.$^1$ This was later strengthened by Matsuda and Matsura [MM], who ruled out black-box construction of OWPs from injective OWFs (which are much more structured than OWFs) that expand by even a single bit. So, yes assuming OWPs is strictly stronger than assuming OWFs (or iOWFs).

The technique employed in both the results is called oracle separations. The idea is to construct an oracle relative to which OWFs (or iOWFs) exist, but any black-box construction of one-way permutations is broken. An overview of Rudich's argument can be found on this thread.

But as Maeher points there could still exists non-black-box constructions of OWPs from OWFs. For example, we know that given indistinguishability obfuscation (IO), it is possible to construct (even trapdoor) OWPs from OWFs [BPW].$^2$ I believe a construction without IO is still open.

You can read more about the different notion of reductions here and on black-box separations here and the references therein.

$^1$ This was under a conjecture which was later proved by Kahn et al. [KSS].

$^2$ There have been attempts at at ruling out even non-black construction of cryptographic objects from one-way functions (e.g, [DS]), but I am not sure if any of them extend to OWPs.

[BPW] Bitanksy, Paneth and Wichs, Perfect Structure on the Edge of Chaos, TCC 2016

[DS] Dachmann-Soled, Towards Non-Black-Box Separations ofPublic Key Encryption and One Way Function

[KSS] Kahn, Saks and Smyth, A dual version of Reimer's inequality and a [enter link description here]5proof of Rudich's conjecture, CoCo 2000

[MM] Matsuda and Matsuura, On Black-Box Separations among Injective One-Way Functions, TCC 2011

[R] Rudich, Limits on the Provable Consequences of One-way Functions, PhD Thesis

  • 1
    $\begingroup$ You could mention that theoretically non-black box techniques could potentially allow circumventing this impossibility result. $\endgroup$ – Maeher Apr 11 '20 at 9:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.