Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
If a block cipher is a secure PRP, is its inverse a secure PRP as well? My intuition says yes but I'm not exactly sure.
On a related note, if a block cipher is a secure sPRP, is its inverse a secure sPRP?
I'm using the terminology "PRP = secure against chosen-plaintext attacks", "sPRP = strong PRP = secure against chosen-plaintext/ciphertext attacks", where "secure = indistinguishable from a random permutation".
In theory. No. The inverse of a secure PRP need not be a secure PRP.
Here is what we can guarantee. The inverse of a secure sPRP (strong-pseudo random permutation) is guaranteed to be a secure sPRP. Any secure sPRP is a secure PRP. Therefore, the inverse of a secure sPRP will be a secure PRP.
FYI, if you are not familiar with PRP/sPRP, the difference between PRP and sPRP is:
a PRP is secure against adaptive chosen-plaintext attacks
a sPRP is secure against adaptive chosen-plaintext/ciphertext attacks
Caution: I've just learned that apparently this terminology is not 100% standard, and some people use different terminology (e.g., weak PRP / PRP or PRP-CPA / PRP-CCA instead of PRP / sPRP). So, beware, and make sure to translate my statements accordingly if you prefer the other terminology. I realize this could affect the meaning of your question.
In practice. In practice, when we make statements like "AES is secure", we usually mean that "AES is a secure sPRP". Sometimes you might see people being sloppy about the distinction between PRP and sPRP, but any modern block cipher that is not broken can usually be assumed to be a secure sPRP. Therefore, the inverse of any modern block cipher (like AES) will also be a secure PRP.
Proof. For the crypto-purists, here is a proof of the statement that the inverse of a secure PRP need not be a secure PRP.
Define $E_k$ as follows:
$$E_k(x) = \begin{cases} 0 &\text{if $x=k$}\\ \text{AES}_k(k) &\text{if $x=\text{AES}_k^{-1}(0)$}\\ \text{AES}_k(x) &\text{otherwise.} \end{cases}$$
It is easy to check that $E_k(\cdot)$ is a permutation for each $k$.
It is also straightforward to prove that $E$ is a secure PRP (making plausible assumptions about AES, e.g., that it can be modelled as an ideal cipher). Why? Because $E_k(\cdot)$ agrees with $\text{AES}_k(\cdot)$ on all but two input values, and the adversary has no clue what those input values are. The best the adversary can do is hope to hit one of those two inputs by chance. The probability that the adversary happens to hit one of those two values by chance is miniscule: after 1 query, the probability is $2/2^{128}$, and after $q$ queries, the probability is $\le 2q/2^{128}$. If $q$ is bounded by any reasonable value (say $q \le 2^{64}$), this probability is negligible.
It is also easy to prove that $E^{-1}$, the inverse of $E$, is not a secure PRP. All you have to do is query the inverse on the plaintext $0$, and you get back the key (since our definition of $E$ has ensured that $E^{-1}_k(0)=k$). So, a single chosen-plaintext query completely breaks $E^{-1}$.
This proves that there exists a cipher that is a PRP but whose inverse is not a PRP, or in other words, that the inverse of a PRP is not necessarily guaranteed to be a PRP.
