2
$\begingroup$

Suppose we use a pseudorandom function $PRF$ and a random key $k$ to generate a set of pseudorandom values:

$\forall i, 1\leq i \leq n: w_i=PRF(k,i)$

Now, consider instead of picking a fresh key, we increment the key by one:$k'=k+1$. Then, we compute a set of pseudorandom values:

$\forall i, 1\leq i \leq n: q_i=PRF(k',i)$


Question: Are the set of $w_i$ values are computationally indistinguishable from the set of $q_i$ values?

$\endgroup$
2
  • $\begingroup$ That would be dependent of the PRF. $\endgroup$
    – Azarinak
    Mar 1, 2016 at 19:31
  • 1
    $\begingroup$ For any cryptographic PRF, I would hope that's true, but you'd have to analyze each PRF algorithm to be sure. $\endgroup$ Mar 1, 2016 at 19:48

1 Answer 1

2
$\begingroup$

Question: Are the set of $w_i$ values are computationally indistinguishable from the set of $q_i$ values?

No, that is not guaranteed by standard security notions.

AES for example is considered a secure PRP (and thus PRF up to a bound), but has related-key attacks. Granted, the known attacks have more complex key-dependence between a large number of keys, but still, in theory an otherwise secure PRF may be insecure if you see outputs for such related keys. They are only required to be secure with a randomly chosen key.

$\endgroup$
2
  • $\begingroup$ Thank you for the answer. What if we set $k'=k+PRF(k'',i)$ where $k''$ is a random key. $\endgroup$
    – user153465
    Mar 6, 2016 at 12:55
  • $\begingroup$ @user153465, that should be ok (assuming addition is modulo key size). However, the standard primitive for this is a key derivation function. For example, HKDF. $\endgroup$
    – otus
    Mar 6, 2016 at 13:05

Your Answer

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

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