Skip to main content
3 of 4
Rearrange equation for clarity
Tim McLean
  • 2.9k
  • 1
  • 15
  • 26

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.

where $D'_k$ is the inverse of $E'_k$ for all $k$.

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.

Tim McLean
  • 2.9k
  • 1
  • 15
  • 26