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.

  • 2
    $\begingroup$ Isn't public-key encryption essentially this? $\endgroup$ – bmm6o Nov 1 '18 at 0:57
  • $\begingroup$ @bmm6o, No, I don't think so. The question contains the condition that there be "no hidden information (keys)..." $\endgroup$ – Ken Goss Nov 1 '18 at 1:33
  • 1
    $\begingroup$ You said it yourself, those are called one-way permutations. It is however unclear what you mean by "no hidden information". $\endgroup$ – fkraiem Nov 1 '18 at 2:13
  • $\begingroup$ 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. $\endgroup$ – Mikero Nov 1 '18 at 4:34
  • $\begingroup$ @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. $\endgroup$ – user63110 Nov 1 '18 at 5:03

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).

  • $\begingroup$ 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. $\endgroup$ – fgrieu Nov 1 '18 at 10:10

Your Answer

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