Example of a PRP that is not a strong PRP

Question

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?

Answer 1

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.

Answer 2

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.