# Distinguishing two sets of pseudorandom values when their keys differ by one

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?

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

## 1 Answer

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.

• Thank you for the answer. What if we set $k'=k+PRF(k'',i)$ where $k''$ is a random key. – user153465 Mar 6 '16 at 12:55
• @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. – otus Mar 6 '16 at 13:05