Nugatory said:
@Aufbauwerk 2045 's original question may be more relevant to the cryptographers than the physicists; it is a very big deal if the bad guys can figure out the PRNG you're using for key generation.
I'd like to chime in on this...
Aufbauwerk 2045 said:
I am only allowed to examine the output. I am not allowed to examine the boxes themselves in any way. Looking only at the output, and using only mathematical tests for randomness, how can I distinguish between the so-called "truly random" and the so-called "pseudo-random" processes?
I like this question!
Without venturing into quantum mechanics, I think this can be distinguished if the mathematical/statistical capabilities of the machine analyzing the data from the two processes is good enough.
How the analyzing could be done? By using
Information Theory.
Let's say we have a sufficiently long message, preferably very long, for statistical reasons.
And let's say we encode this message two times, using two different random generators.
The first encoding is made by modifying the message using a "true" random quantum process.
The second encoding is made by modifying the message using a pseudorandom
1 process.
Then we can perform analysis of the so-called
information entropy2 of the two encodings with respect to the original message.
If our hypothesis that the quantum mechanics process is truly random, and the pseudorandom generator "less random", this should be able to be seen in the values of the information entropies of the two encoded messages. The QM message entropy should be at maximum, and the pseudorandom message entropy should be less than the QM value.
(see e.g.
Entropy as information content)
Edit:
On a second thought I may have been a little too quick here, it was a long time ago since I used information theory. Maybe we could use
mutual information as well... I have to think about it...
Edit 2:
Aufbauwerk 2045 said:
how can I distinguish between the so-called "truly random" and the so-called "pseudo-random" processes?
I just remembered a thing from my time studying cryptography... a pseudo-random process can be identified by analyzing sufficiently long output sequences of the process. A pseudo-random process will at one point or another, repeat itself, that is, start over.
So, the quality of the pseudo-random process, the "randomness", if you like, can be judged by how long it takes for the process to start repeating itself.
Edit 3: Footnotes:
1 With
pseudorandom I mean a sequence generated by a digital machine only, like a computer.
2 This is not physical entropy, it is a purely information theoretical concept.