Security of OFB mode if PRP is used instead of PRF

Question

In the cryptography lecture at my university, we had the theorem that (randomized) OFB mode is IND-CPA secure if the used pseudorandom function (PRF) is IND-PRF secure.

Afterwards, we investigated the security of rOFB if a pseudorandom permutation (PRP) is used instead of an PRF. As we can only distinguish a PRP from a PRF if the PRF produces a collision, we can use them interchangeably as long as the block length is large enough. This is the case as for large block lengths the probability of a collision is negligible.

From this result we deduced that we can also use PRPs in rOFB mode which results in a IND-CPA secure encryption scheme.

I totally understand that we can distinguish a PRP from a random function oracle (RFO) if the RFO produces a collision. Therefore, the PRP 'does not look random' if we can query many outputs. However, the security of rOFB mode requires that we do not have a collision in the ciphertexts. Therefore, I do not understand why the security of rOFB mode is lower when we use a PRP instead of a PRF (negligibly lower, but lower) as a PRP does rule out exactly this attack on OFB.

It is clear for me that the PRP-OFB mode does not look like an OTP for many queries, but I cannot imagine why the attack surface should be negligibly higher if there is NO collision possible.

Answer 1

I think the final negligible term depends on the way you prove the rOFB security. If you construct OTP in the ideal word based on random functions, then use PRF; if based on random permutations, then use PRP. Note that in the latter case, replacing block ciphers with random permutations cannot guarantee that no collisions happen among the block cipher outputs. In other words, such collisions are not the same as those considered in PRF/PRP.

The attack surface for PRP is not negligibly higher. It seems higher just because you first prove the security with PRF and wants an easy reduction based on the advantage difference between PRP and PRF. Btw, any negligible difference should not matter in the security proofs.