1
$\begingroup$

Lately I've been studying cryptography and in the current course I'm taking we're reviewing statistical tests and how they can be used to determine if a pseudo-random generator is secure or not. Essentially, one of the requirements for a Pseudo-random generator to be secure is that the probability of guessing the next bit in the string is less than 1/2 + a non-negligible epsilon (epsilon being any statistical advantage the computer has of guessing the next bit of the string due to insecurity in the PRG). In an example the professor uses, he states that the probability of guessing the next bit of output from the PRG is 1/2 + 1/1000 (the non negligible epsilon). How is 1/1000 non-negligible? I understand we're using computers with thousands of times faster processing power than a normal human brain, but that still means that a computer only has a 50.1% chance of guessing the correct bit. How can a computer leverage that tiny extra probability to crack a secret key?

| |
$\endgroup$