Permutation for which an inverse is a hard problem

Is it possible to construct (even if we don't know how) a permutation for which an inverse must exist but is difficult to find (brute force required)? The one way permutation contains no hidden information (keys) or state - it's public.

Or can it be proven that such a construct is not possible?

In case I'm not specific enough in what I'm asking, such a construct would allow for a sponge construction with no hidden state because no inverse permutation for it can be found.

• Isn't public-key encryption essentially this? Nov 1, 2018 at 0:57
• @bmm6o, No, I don't think so. The question contains the condition that there be "no hidden information (keys)..." Nov 1, 2018 at 1:33
• You said it yourself, those are called one-way permutations. It is however unclear what you mean by "no hidden information". Nov 1, 2018 at 2:13
• In a sponge construction, it is not the permutation that is secret. The permutation is assumed to be public. And sponge constructions are proven secure even when the permutation's inverse is public. Disabling the permutation's inverse (by using a OWP) won't eliminate the need for hidden state. Nov 1, 2018 at 4:34
• @Mikero I was under the impression that the purpose of the hidden state was to prevent you from inverting the permutation and overwriting the end of a known message. Or even recovering a MAC key if the whole message is known.
– user63110
Nov 1, 2018 at 5:03

2 Answers

It is obviously possible; one simple example is the function $$f(x) = g^x - 1 \bmod p$$, where $$p$$ is a large prime, and $$g$$ generates the entire group $$\mathbb{Z}_p^*$$; this is permutation over the range $$[0, p-1)$$, and is difficult to invert if the discrete log problem is hard.

What may be more difficult is to design an efficient hard-to-invert permutation; most efficient permutations are designed as a composition of trivially invertible permutations (and hence the result can be easily inverted).

• Even leaving efficiency aside, I don't know a recognized method to generate a hard-to-invert permutation of a moderate set, $2^b$ elements with $b$ in the low hundred(s). I asked here, and while I accepted the answer because it was useful, it is a far cry from a good solution. Also I have this other question where inefficiency is desired.
– fgrieu
Nov 1, 2018 at 10:10

Or can it be proven that such a construct is not possible?

Kinda. Sort of. As usual in complexity theoretical cryptography. The TL;DR is though that the provable, unconditional existance of such a permutation would imply $$P\neq NP$$.

So in complexity theoretical cryptography one of the main objects studied is the so-called One-Way-Function. That is a polynomial-time computable function $$f:\{0,1\}^*\to\{0,1\}^*$$ where we assume that $$\Pr[x\stackrel{\}{\gets}U_n;\mathcal A(1^n,f(x))\in f^{-1}(f(x))]\leq \operatorname{negl}(n)$$ for some negligible function $$\operatorname{negl}$$ and all probabilistic polynomial-time adversaries $$\mathcal A$$. Obviously this is very little structure imposed on such a function $$f$$ but this definition has been proven to be theoretically sufficient to construct any symmetric-key crypto (and a few other things), the key term here is Minicrypt.

Now we note that the existence of such an $$f$$ clearly implies $$P\neq NP$$. The argument for that is simple: First we built a PRG $$G_f$$ from our OWF $$f$$ (via this Result, PDF), then we define the language $$x\in L\iff \exists k: (G_f(k)\oplus m)\|m=x$$. Clearly this language is in NP given that with $$k$$ one can clearly decide whether $$x$$ has the desired form. However this language is not in BPP (and as P is in BPP it is neither in P) given that deciding whether the word is in the language would break the PRG (as such an algorithm would have to work for all possible strings of appropriate length and only have bounded, non-negligible error probability) which would violate the OWF property of $$f$$. Thus we have a language in $$NP\setminus P$$ and therefore $$P\neq NP$$.

Now the final question is: How does this all relate to One-Way-Permutations? Well they are defined as OWFs with the additional constraint that for each input length $$n$$ the output also has length $$n$$ and that the mapping is bijective (i.e. $$\forall n\in\mathbb N: f(\{0,1\}^n)=\{0,1\}^n$$). As each OWP is also an OWF that means that the unconditional existence of an OWP implies $$P\neq NP$$.