Wikipedia:Reference desk/Archives/Mathematics/2013 July 13

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is a transcluded archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

July 13

is it true that you can increase the quality of a RNG by (also) including a backdoor but not decrease it?

Suppose I normally use a quick algorithm for my RNG generator in software. I think it's very good. I have a random hardware generator that's given to me by the NSA and told "trust us, there's no backdoor in here." I also have a lava lamp.

So, now I will combine these streams by xor'ing the next bit from all three to get my next random bit.

Isn't it true now true that if any ONE of the three are secure, the stream is truly random?

Meaning, the fact htat I've included all three can *only* increase the entropy, and cannot possibly decrease it? Even if it were so broken that one of the three only always returns 1? Even if one of them is explicitly included to try to break the randomness of hte stream?

The argument being that xor is commutative, so that you can arrange any of the three items in the xor stream to come "last". At that point it MUST act like a OTP (one time pad) and completely hide the 'brokenness' of the other two, with the key immediately being discarded since it is not saved anywhere. The brokenness HAS to disappear, otherwise it would in some statistical or other sense be present in the 'ciphertext' that is the output of the OTP performed by the 'good' source in the chain.

So: weak software rng -> xor -> lava lamp that actually always ends up returning 1 due to my bug -> xor -> NSA provided backdoor hardware rng

By including hte hardware RNG in this stream, I could *ONLY* make the stream stronger. But I could not make it broken if it's not already broken; it could 'only' save the day. (For example if there's some regularity in my weak software rng), but by some miracle the NSA provided box really is truly random.

what do you think? 178.48.114.143 (talk) 23:14, 13 July 2013 (UTC)

If one is good and the other two aren't, you should be fine. But in principle you could go wrong if two are good independently but are correlated with each other. If you can rule that out, I think you should be okay. Looie496 (talk) 00:46, 14 July 2013 (UTC)

Yup, you can strengthen the "should". Two conditions (a) at least one of the sources is truly random (each bit is independent of its other bits and balanced) and (b) this source is independent of the other sources, together ensure that the result is truly random. Also, if all the sources are truly independent albeit imperfect, the entropy of the output should not be less than that of any single one of the sources (sorry, but I've not got a rigorous result, hence I only put "should" here). — Quondum 03:44, 18 July 2013 (UTC)