Assume that a DRBG passes all statistical tests. We use that DRBG to shuffle(Fisher-Yates) an array that contains $\{0,1,\ldots,2^n-1\}$. Now get a pseudorandom permutation $\{0,1\}^n\rightarrow \{0,1\}^n$.

My question is, If I change $i$-th bit at the input then the probability of $j$-th bit being flipped is $\frac{1}{2}$. Can anyone provide any formal proof or any reference for the previous statement?

  • 1
    $\begingroup$ You might want to have a look at the PRP-PRF switching lemma. $\endgroup$ – SEJPM Mar 14 at 14:46

Your Answer

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

Browse other questions tagged or ask your own question.