Inverse single element permutations

Question

Let's say we have a set of ordered elements $D=[x_1,x_2,x_3,x_4,x_5]$. We apply a random permutation on them with a $PRP=P_k: P_k(D)=D'=[x_3,x_2,x_5,x_1,x_4]$

My question is: can the owner of the key $k$ recover a single position of the original element without having to recompute all the permutations? Is there an inverse $PRP, PRP'_K$ such that:

$PRP'_K(3)=x_3, PRP'_K(2)=x_2$ and so on and so forth or given the result of the permutation and the key to recover the original element of this positions:$PRP'_K(x_3)=x_1, PRP'_K(x_2)=x_2$ ? without keeping either $D$ or $D'$

Answer 1

No, in general, knowing the key $k$ allowing efficient computation of a keyed permutation $P_k$ does not allow to efficiently compute the inverse permutation.

Here is a concrete example where the inversion is (conjecturally) computationally infeasible:

• Let $D$ be the set of 4096-bit bitstrings, assimilated to integers per big-endian conventions.
• Let $p=2^{4097}+3^{2579}+863880\;$. This is such that $p$ and $(p-1)/2$ are prime, and $2^{(p-1)/2}\equiv-1\pmod p$. The function $x\to(2^x\bmod p)$ is an efficiently computable public permutation of the set $\{1,2,3\dots p-3,p-2,p-1\}$, but the reverse permutation is hard to compute for arbitrary input (that's a Discrete Logarithm problem).
• For $k\in D$, let $P_k$ be the permutation over $D$ defined for input $x$ by
  • $x\gets (x\oplus k)+8192$
    note: here $8192\le x<2^{4096}+8192<(p−1)/2$
  • repeat
    • $x\gets(2^x\bmod p)$
  • until $8192\le x<2^{4096}+8192$
  • output $(x-8192)\oplus k$

The repeat/until loop (known as the cycling trick) creates a public (conjecturaly) hard to invert (that is, trapdoor) permutation of the set $\{8192,8193,\dots,2^{4096}+8190,2^{4096}+8191\}\;$. Combined to XOR with $k$, that forms $P_k$, which is keyed, and (conjecturaly) hard to invert and computationally indistinguishable from a random permutation without knowledge of $k$.

---

The above $P_k$ is an example of a PRP which members are trapdoors even to one choosing the key $k$. That's not the case of all PRPs: we also have block ciphers, which are PRPs invertible by anyone able to compute the function; and textbook RSA encryption, which is computable by anyone knowing the public key, but invertible only by one knowing the private key (textbook RSA encryption alone is not quite a PRP on a fixed set, but it is possible to build such PRP from textbook RSA encryption, e.g. using a cycling trick as above).