19
$\begingroup$

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

$\endgroup$
8
  • $\begingroup$ The stronger concept of sPRP (e.g., 4-round Feistel with PRF) implies that the inverse is secure as well --- an sPRP allows the attacker to query both the permutation and its inverse. $\endgroup$ Sep 19, 2013 at 17:12
  • 1
    $\begingroup$ possible duplicate of Can AES decryption be used as encryption? $\endgroup$
    – Reid
    Sep 19, 2013 at 17:49
  • 3
    $\begingroup$ @Reid, This is not a duplicate. The other question is related but not identical. The other question asks whether AES's inverse is a PRP, so the other question is only asking about AES (one specific example of a PRP). This question asks whether it is true that for every PRP, its inverse is also a PRP. That's a more general question. As a quick way to see that they are two different questions, they happen to have different answers: the inverse of AES is a PRP, but the inverse of a PRP is not necessarily a PRP. (See my answer below.) $\endgroup$
    – D.W.
    Sep 19, 2013 at 22:07
  • $\begingroup$ nightcracker, when you say PRP, do you mean "secure against chosen-plaintext attacks" (as in my answer), do you mean "secure against chosen-plaintext/ciphertext attacks" (what I call sPRP in my answer)? This affects the meaning of your question. I've edited your question to introduce one possible interpretation, but please edit the question if that isn't what you had in mind. $\endgroup$
    – D.W.
    Sep 19, 2013 at 22:52
  • $\begingroup$ @D.W.: it's not an exact duplicate, but I think reading my answer on that question is enough to answer this question as well, at least implicitly. $\endgroup$
    – Reid
    Sep 19, 2013 at 23:12

1 Answer 1

23
$\begingroup$

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.

$\endgroup$
9
  • $\begingroup$ I was under the impression that, by default, $\;\;$ weak PRP $\:$<$\:$ PRP $\:$=$\:$ strong PRP $\:\:\:$. $\hspace{1.6 in}$ $\endgroup$
    – user991
    Sep 19, 2013 at 22:27
  • $\begingroup$ @RickyDemer, huh! I didn't know that. Maybe the terminology isn't completely standard, or maybe I've been reading the wrong references. My recollection was that in the references I've seen, PRP = secure against chosen-plaintext attacks, strong PRP = secure against chosen-plaintext/ciphertext attacks (example: Boneh's class), but it's possible that different authors use different definitions, or that the definitions have evolved over time. Bellare and Rogaway's notes now refer to prp-cpa and prp-cca, to avoid ambiguity. $\endgroup$
    – D.W.
    Sep 19, 2013 at 22:40
  • $\begingroup$ After looking online, most of the sources I found seem to agree with your use of the term. $\hspace{1.01 in}$ $\endgroup$
    – user991
    Sep 20, 2013 at 0:07
  • $\begingroup$ Thanks. Do you have a real-world example of a PRP that is not a sPRP? Or is the weakness mostly a theoretical issue with constructions as you described? $\endgroup$
    – orlp
    Sep 20, 2013 at 6:38
  • 1
    $\begingroup$ @nightcracker, I don't know of any real-world examples of a PRP that's not a sPRP. (The closest is 3-round Luby-Rackoff -- i.e., 3 rounds of a Feistel network with an absolutely perfect F function -- is a PRP but not a sPRP. However, no one uses something like that in practice.) So, yeah, I think it's just a theoretical issue. $\endgroup$
    – D.W.
    Sep 20, 2013 at 16:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.