Here's the situation. Suppose I have a secure PRF $F$ and use $F$ in the following way:

for equal size message $m_i$ in $\{m_j\}^{q}_{j=1}$( $q=poly(n)$, $n$ is security parameter ), randomly select $k_i \xleftarrow{\$}K$ and compute $c_i=F(k_i, m_i)$, where $K$ is key space. All previous computation results $\{(k_j, m_j, c_j)\}^{i-1}_{j=1}$ are revealed to adversary $A$ when using ($k_i$, $m_i$) to evaluate $F$. The main point is that the key is changed and some previous keys revealed, which is different to traditional pseudo-randomness definition of $PRF$. My security goal is adversary $A$ cannot distinguish $c_i$ from a random string $r_i$ using any $PPT$ distinguisher $D$. Intuitively, I think $F$ is secure in this setting. Is there any formal security model for this situation? and under what situation is it secure or insecure?


1 Answer 1


Yes, this is secure since the keys are chosen randomly. Remember that even in the "traditional" PRF game, the adversary can generate keys at random, so the output of F on past keys does not help him (since he can generate such outputs anyway).

  • $\begingroup$ yes that makes sense, it seems i didn't fully understand the original definition. Thank you, fkraiem. $\endgroup$
    – D.V.
    May 17, 2017 at 13:29
  • $\begingroup$ @binta Indeed, the wording of your question hints that you are not very clear on the difference between a PRF and a PRG... $\endgroup$
    – fkraiem
    May 17, 2017 at 16:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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