# Tag Info

0

your title asks "How to prove that a function F isn't a pseudo random function", in your question case (b) is not PRF which is easy to prove. function $F'$ is PRF if for all PPT distingushers $D$, success probability of $D$ distinguishing $F'$ from random function be negligible. So for proving that function $F'$ is not PRF it suffices to construct one ...

4

The function $f$ is biased towards the complement of the input $c_{i,j}$, assuming the other two inputs are approximately randomly distributed. As all the values $c_{i,j}$ are public, this means that the output of the function $R_i$, and hence the function $F$ is strongly distinguishable from random (being biased towards a known bit pattern). This isn't an ...

2

Is that backtracking-resistant? No, as mentioned in the comments, if the PRF itself can be inverted when you know the key, the PRG is not 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 ...

Top 50 recent answers are included