2
$\begingroup$

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'$

$\endgroup$
  • $\begingroup$ By definition, a pseudorandom permutation is efficiently invertible given the key. $\endgroup$ – fkraiem Aug 3 '16 at 1:09
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ A bit confused. But a PRP isn't a trapdoor permutation by definition? Meaning the owner of they can easily invert? $\endgroup$ – curious Aug 3 '16 at 3:37

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.