# If a PRG is constructed by iterating a PRF, is it backtracking-resistant?

Say we construct a pseudo-random generator from a pseudo-random function $f$ (using some constant key $k$ and some initial value $v_0$). We do this by feeding the output block of the PRF back into the PRF to produce a new block of pseudo-random bits. That is, $B_{i+1} = f_k(B_i)$. Is that backtracking-resistant?

I thought it would be backtracking resistant because if we compromise the internal state of the PRG at time $t+1$ (meaning the adversary gets $k$ and $B_{i+1}$), then we can't find any of the previous blocks $B_i$ (for $i < t+1$), since the PRF is hard to invert. That is, $B_{i+1} = f_k(B_i)$, so we want to find $B_i$ by doing $B_i = f^{-1}_k(B_{i+1})$, but we can't invert it.

Am I missing something? Apparently it's not backtracking-resistant because the key isn't being changed, whereas other PRGs such as HMAC-DRBG are, because they update the key.

• Yes. ​ Who is a PRF hard to invert for? ​ ​ ​ ​ – user991 Nov 14 '15 at 4:36
• I might have mixed up PRF with one-way function (I don't quite understand the relationship between them). – user29077 Nov 14 '15 at 4:40
• A PRF with large domain is hard to invert for parties/people who don't know the key. ​ ​ – user991 Nov 14 '15 at 4:41
• A PRF may also be hard to invert for someone who knows the key, as there is no requirement for an efficient inverting algorithm. However, since a PRF is normally constructed from a PRG, I don't see the point of doing it the other way... – fkraiem Nov 14 '15 at 4:47
• Could you give an example of a PRF that is hard to invert for someone who doesn't know the key, but easy to invert for someone who knows the key? – user29077 Nov 14 '15 at 4:58

I thought it would be backtracking resistant because if we compromise the internal state of the PRG at time $t+1$ (meaning the adversary gets $k$ and $B_{i+1}$), then we can't find any of the previous blocks $B_i$ (for $i < t+1$), since the PRF is hard to invert.