Unpredictable Randomness Definition


 
Let's consider randomness as the outcome of an experiment, two extremal cases are of interest. The first is the truly random  number generator, which is based on a non-deterministic process. In that case, without condition, you cannot guess the outcome before it actually happens.

The second extreme case is  pseudo-randomness. The process takes as input a (short) sequence of numbers (seed). It is called a pseudo-random number generator  if, by considering only its outputs, it is computationally infeasible to distinguish it from a truly random number generator. By ``computationally infeasible'', we mean non polynomial time and memory and by ``distinguish'', we mean that the probability to take the good decision is significantly greater than 1/2.

Random bits produced by peripherals events (e.g. by  Entropy Gathering Daemons), or by HAVEGE, are not, strictly speaking, truly random bits nor pseudo-random bits. They are not truly random because the process which produces them is deterministic. One could theoretically reproduce the sequence if he/she was able to reproduce all the past events on the machine.  They are not pseudo-random either since there is no (short) seed which would allow an exact reproduction of the random sequence.
The randomness results instead from an inability to control or predict with sufficient accuracy the events involved in the generation process.

For the sake of convenience, we will speak in that case of  unpredictable randomness.