"what means does A employ to generate its random sequence?"
Close enough. I'm talking about the quality of the randomness of the "random" sequence. See Shannon.
but I had in mind something like a simple LCG
pwnd.
You could have said "use a cryptographically secure PRNG" (which reduces to "use the random oracle in my proof", but since we're practitioners here and not theorists, we don't care -- we just have to recognize that the output of the PRNG may, in fact, be deterministic despite what we think now), or perhaps "use a noisy diode or some other truly random source of entropy" though that's... expensive, in terms of entropy, and probably infeasible given the system we're talking about. But, LCGs are not suitable for this, or most use-cases that require a secure entropy source. (I'm rather swamped with some work right now, or I'd dig up the nice LCG lattice work that was done... a while ago, but not only are they deterministic, but they're also easily precomputable for many inputs, some of which do not even produce random sequences!)
But, I think my point has been made. We don't know how to design algorithms that produce truly random output from a fixed input seed -- sure, we can do things like change the input seed before the expected period of the algorithm elapses, etc., or we can go the expensive route and produce one random bit of input per one random bit of output (as is needed to make one-time-pads unconditionally secure), but even if you're talking about the "one-time-pad" equivalent of a search algorithm, you still have that problem of truly random "randomness" to contend with.
This isn't a trivial problem. The first version of SSL, in Netscape, was broken because of a (much stronger on paper than LCG, but poorly seeded) flawed PRNG, and we're still seeing these problems in systems being designed right now. Dismissing the last 63 years of research into the entropy of a presumed-random stream of data is a mistake that far too many implementors make.
![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
(no subject)
Date: 2008-01-04 06:40 pm (UTC)Close enough. I'm talking about the quality of the randomness of the "random" sequence. See Shannon.
but I had in mind something like a simple LCG
pwnd.
You could have said "use a cryptographically secure PRNG" (which reduces to "use the random oracle in my proof", but since we're practitioners here and not theorists, we don't care -- we just have to recognize that the output of the PRNG may, in fact, be deterministic despite what we think now), or perhaps "use a noisy diode or some other truly random source of entropy" though that's... expensive, in terms of entropy, and probably infeasible given the system we're talking about. But, LCGs are not suitable for this, or most use-cases that require a secure entropy source. (I'm rather swamped with some work right now, or I'd dig up the nice LCG lattice work that was done... a while ago, but not only are they deterministic, but they're also easily precomputable for many inputs, some of which do not even produce random sequences!)
But, I think my point has been made. We don't know how to design algorithms that produce truly random output from a fixed input seed -- sure, we can do things like change the input seed before the expected period of the algorithm elapses, etc., or we can go the expensive route and produce one random bit of input per one random bit of output (as is needed to make one-time-pads unconditionally secure), but even if you're talking about the "one-time-pad" equivalent of a search algorithm, you still have that problem of truly random "randomness" to contend with.
This isn't a trivial problem. The first version of SSL, in Netscape, was broken because of a (much stronger on paper than LCG, but poorly seeded) flawed PRNG, and we're still seeing these problems in systems being designed right now. Dismissing the last 63 years of research into the entropy of a presumed-random stream of data is a mistake that far too many implementors make.