# Example of a PRP that is not a strong PRP

The exact definition of security for a pseudorandom permutation is straightforward - for some encryption scheme $E\,\colon\,\mathcal{K}\times\mathcal{D}\rightarrow\mathcal{D}$, it must be the case that no efficient adversary can distinguish $E_k(\cdot)$ from $\Pi(\cdot)$ (a random permutation on $\mathcal{D}$) except with negligible probability. A "strong" PRP is defined the same way, except $E_k(\cdot)$ and decryption $D_k(\cdot)$ must be jointly indistinguishable from $\Pi(\cdot)$ and $\Pi^{-1}(\cdot)$.

I've thought about this but I can't quite come up with an example of an $E$ whose encryption is indistinguishable from a random permutation but its decryption doesn't have the same property. Does anyone have a nice example?

EDIT: I saw DW's example in the answer of this question. It is a very clever construction but quite 'unnatural' as well. Are there more straightforward examples?

• This is the first time I encounter this definition, it's probably equivalent to the usual one but it's very weird. – fkraiem Feb 21 '16 at 0:32
• I saw DW's example but it is a little bit unsatisfying, in a sense - I was hoping for a more 'natural' example that says something about the difference between the two definitions. – pg1989 Feb 21 '16 at 0:33
• @fkraiem I tried to write it out formally but the LaTex was being weird. – pg1989 Feb 21 '16 at 0:36
• It seems like your definition of (strong) PRP is not equivalent to the usual one, since for that, they need to be jointly indistinguishable from [a random permutation and its inverse], rather than just each indistinguishable from a random permutation. ​ ​ – user991 Feb 21 '16 at 1:05
• Yeah, I'll edit it to make that clear. – pg1989 Feb 21 '16 at 1:07

A three-round Feistel network is a good example of a realistic construction that is a secure "weak" PRP, but not a "strong" PRP.

A Feistel network uses the permutation $P_f(L, R) = R, (L\oplus f(R))$, where $f$ is an element of a pseudorandom function family. This PRP will be keyed with three keys $k_1, k_2, k_3$, which will be used to key a PRF $F$ differently each round.

We define $E_{k_1,k_2,k_3}$ to be a three-round Feistel network:

$E_{k_1,k_2,k_3}(L \| R) = \operatorname{Concat}(P_{F_{k_3}}(P_{F_{k_2}}(P_{F_{k_1}}(L, R))))$

Assuming $F$ is a PRF, $E$ will meet the definition of a weak PRP. I believe this proof is originally attributed to Luby, Rackoff (for details of the proof, see here, starting on page 11). Similarly, the inverse $D_{k_1,k_2,k_3} = E^{-1}_{k_1,k_2,k_3}$ is also a weak PRP.

Interestingly, though, $E$ is not a strong PRP. When given simultaneous access to both a "forward" oracle and a "backward" oracle, an adversary can distinguish between $(E_{k_1,k_2,k_3}(\cdot), D_{k_1,k_2,k_3}(\cdot))$ and $(\Pi(\cdot), \Pi^{-1}(\cdot))$, where $\Pi$ is a randomly selective permutation on the same domain.

Here is an adversary that distinguishes the two with high probability:

• Query the decryption oracle with two strings of zero bits: $(a\|b) \leftarrow D(0\|0)$
• Query the encryption oracle: $(c\|d) \leftarrow E(0\|a)$
• Query the decryption oracle again: $(e\|f) \leftarrow D((b\oplus d)\|c)$
• If $e=c\oplus a$, then return $1$, else return $0$.

Here's why this works:

• By expansion, we see that $D_{k_1,k_2,k_3}(L\|R) = (x\|y)$, where:

$x=R \oplus F_{k_2}(L \oplus F_{k_3}(R))$

$y=L \oplus F_{k_3}(R) \oplus F_{k_1}(R \oplus F_{k_2}(L\oplus F_{k_3}(R)))$

• It follows that the first oracle query will result in:

$a=F_{k_2}(F_{k_3}(0))$

$b=F_{k_3}(0) \oplus F_{k_1}(a)$

• By expansion, we see that $E_{k_1,k_2,k_3}(L\|R) = (x\|y)$, where:

$x=R \oplus F_{k_2}(L \oplus F_{k_1}(R))$

$y=L \oplus F_{k_1}(R) \oplus F_{k_3}(R \oplus F_{k_2}(L\oplus F_{k_1}(R)))$

• It follows that the second oracle query will result in:

$c=a \oplus F_{k_2}(F_{k_1}(a))$ and

$d=F_{k_1}(a) \oplus F_{k_3}(c)$.

• Note that $b$ and $d$ both contain the term $F_{k_1}(a)$. When we compute $b\oplus d$, the terms cancel:

$b\oplus d=F_{k_3}(0) \oplus F_{k_3}(c)$

• Finally, in the third oracle query, the specifically crafted $L$ and $R$ cause the following simplification:

$e=c \oplus F_{k_2}((b\oplus d) \oplus F_{k_3}(c))\\=c \oplus F_{k_2}(F_{k_3}(0))\\=c \oplus a$

• The adversary finds that $e=c\oplus a$ as required, which would only be expected with low probability for a truly random permutation.

The basic idea is to set things up so that $F_{k_2}$ receives the same input in two different queries. This causes the left oracle output to be masked with the same value, which can be detected by the adversary.

Crucially, this attack would not work without the ability to query the permutation in both directions.

• Very nice (and natural) example. Thanks for writing this up. – pg1989 Feb 21 '16 at 23:03

For convenience, let's assume that $\mathcal{K} = \mathcal{D}$ so that the key $k \in \mathcal{D}$. Define $E$ to be some strong PRP, and let $D$ be its inverse.

Now, define a PRP $E' : \mathcal{D} \times \mathcal{D} \to \mathcal{D}$ such that $E'_k(x) = E_k(x)$ for all values of $k$ and $x$, but with the following adjustments:

• Define $E'_k(k) = 0$ for all values of $k$. The choice of $0$ is arbitrary; any fixed value known to the adversary will do.
• Define $E'_k(D_k(0)) = E_k(k)$ so that $E'_k$ remains a permutation.

An adversary will have great difficulty distinguishing $E'(\cdot)$ from a random permutation $\Pi(\cdot)$, since it does not know the key $k$. However, when given access to a decryption oracle $D'_k(\cdot)$, the adversary can query $D'_k(0)$, discover the key $k$, and perform an additional query to determine whether or not the permutation is random.