3 ms·

Running different pseudo-random generators in parallel and then XORing their results should have the property that if at least one of the input algorithms is "g

Running different pseudo-random generators in parallel and then XORing their results should have the property that if at least one of the input algorithms is "good", then the output algorithm is "good". My intuition is based on the fact that this statement is correct for true random sources: If you take a bunch of random sources that generate streams of bits, then XORing those streams together will result in a stream of uniform and independent random bits if at least one of the source streams is a stream of uniform and independent random bits (this is an elementary argument in probability). I'm not certain at the moment whether this generalizes to pseudo-random generators, but it seems plausible enough to expect that the XORed bit stream is at least as "good" in terms of pseudo-randomness as the best of the input streams. Edit: Okay, I just realized that this is obviously false when the input streams themselves are correlated. For example, suppose that one of the input streams is PRNG A, and the other input stream is simply the negation of the output of PRNG A with the same seed. Then the output stream will consist of all 0s, which is not good. Perhaps some result can be salvaged when the seeds of the different PRNGs come from independent, truly random sources, but this means things get very tricky very quickly.

contingencies 13y ago
Right, I came to the same realization. You'd need to make sure the input stream(s) (ie. entropy source(s)) to the PRNGs in question were not shared. Even if that was impractical, and this is pure conjecture from someone who is not a mathematician or cryptographer, then at the very least they should be well obfuscated, eg. unpredictably delayed throughout a large enough temporal keyspace with a not insignificant degree of feedback, or with large initial random seeds. But I'm not a cryptographer, so that's all baseless assertion. IMHO the notion stands, though.
- eru 13y ago
  XORing multiple sources throws away lots of useful entropy. There are better approaches available, and they are used. Edit: nhaehnle, I can't reply to your comment (yet) because it's too deeply nested. I don't know the direct answer, but if you want to do some research yourself, you could do worse then reading this relevant Wikipedia article (https://en.wikipedia.org/wiki/Randomness_extractor https://en.wikipedia.org/wiki/Randomness_extractor) and following the links. They don't talk about provable extractors in the article itself, but you can probably identify at least the right terms you need to search for on arxive or so.
  - nhaehnle 13y ago
    Is there a provably better way, though? I think this was basically the premise of the original question: Given that there is doubt about the safety of some PRNG scheme, is there a proven way to combine multiple PRNG scheme with the property that the resulting PRNG is at least as secure as the most secure "input" PRNG? If there is such a better way, then please provide more information - links and such.

contingencies 13y ago

Right, I came to the same realization. You'd need to make sure the input stream(s) (ie. entropy source(s)) to the PRNGs in question were not shared. Even if that was impractical, and this is pure conjecture from someone who is not a mathematician or cryptographer, then at the very least they should be well obfuscated, eg. unpredictably delayed throughout a large enough temporal keyspace with a not insignificant degree of feedback, or with large initial random seeds. But I'm not a cryptographer, so that's all baseless assertion. IMHO the notion stands, though.

eru 13y ago
XORing multiple sources throws away lots of useful entropy. There are better approaches available, and they are used. Edit: nhaehnle, I can't reply to your comment (yet) because it's too deeply nested. I don't know the direct answer, but if you want to do some research yourself, you could do worse then reading this relevant Wikipedia article (https://en.wikipedia.org/wiki/Randomness_extractor https://en.wikipedia.org/wiki/Randomness_extractor) and following the links. They don't talk about provable extractors in the article itself, but you can probably identify at least the right terms you need to search for on arxive or so.
- nhaehnle 13y ago
  Is there a provably better way, though? I think this was basically the premise of the original question: Given that there is doubt about the safety of some PRNG scheme, is there a proven way to combine multiple PRNG scheme with the property that the resulting PRNG is at least as secure as the most secure "input" PRNG? If there is such a better way, then please provide more information - links and such.