Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
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.
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).
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$.
