= 27d567bc2d48d9f40e9ccc20ea370b15)
asr comments on Can noise have power? - Less Wrong
You are viewing a comment permalink. View the original post to see all comments and the full post content.
= 783df68a0f980790206b9ea87794c5b6)
Loading…= b715d02e85f7b3b4ae65ca3d3e450868)
Subscribe to RSS Feed
Powered by Reddit
= f037147d6e6c911a85753b9abdedda8d)
You are viewing a comment permalink. View the original post to see all comments and the full post content.
Comments (42)
I'm an expert in a neighboring field: numerical optimization. I've seen lots of evidence for Jaynes's impression that for any algorithm that uses randomness, one can find a deterministic technique (which takes thought) that accomplishes that goal better. (For example, comparing genetic algorithms, simulated annealing, and tabu search, the last has an deterministic memory mechanism that gives it the ability to do both diversification and intensification, with much more control than either of the other two.) Random methods are employed frequently because to do otherwise would require thought.
As for the debate, to me it looks like it was over terminology. To illustrate, let me label three different cases: the 'benign' case, where the environment is assumed to be dumb (i.e. maxent priors are reasonable), the 'adversary' case, where the environment is assumed to be an agent that knows your algorithm but not your private source of randomness, and the 'omega' case, where the environment is assumed to be an agent that knows your algorithm and your private source of randomness.*
Eliezer thinks the phrase 'worst case analysis' should refer to the 'omega' case. Scott thinks that the 'adversary' case is worth doing theoretical analysis on. The first is a preference that I agree with,** the second seems reasonable. I think Silas did a good job of summarizing the power that randomness does have:
*There's also a subtlety about solving the problem 'with high probability.' For a deterministic algorithm to have a chance at doing that, it needs to be the benign case- otherwise, the adversary decides that you fail if you left them any opening. For a randomized algorithm, the benign and adversary cases are equivalent.
**One of the things that Scott linked--when Monte Carlo goes wrong--is something that shows up a lot, and there's a whole industry built around generating random numbers. For any randomized algorithm, the real worst case is that you've got a PRNG that hates you, unless you've paid to get your bits from a source that's genuinely random, and if omega was the case that came to mind when people said 'worst case,' rather than adversary, this would have been more obvious. (vN got it, unsurprisingly, but it's not clear that the median CS researcher did until they noticed the explosions.)
"Worst case analysis" is a standard term of art in computer science, that shows up as early as second-semester programming, and Eliezer will be better understood if he uses the standard term in the standard way.
A computer scientist would not describe the "omega" case as random -- if the input is correlated with the random number source in a way that is detectable by the algorithm, they're by definition not random.
Actually, in the context of randomized algorithms, I've always seen the term "worst case running time" refer to Oscar's case 6, and "worst-case expected running time" -- often somewhat misleadingly simplified to "expected running time" -- refer to Oscar's case 2.
A system that reliably behaves like the omega case is clearly not random. However, a random system such as case 2 may still occasionally behave like omega, with probability epsilon, and it is not at all unreasonable or uncommon to require your algorithm to work efficiently even in those rare cases. Thus, one might optimize a random system by modelling it as an omega system, and demanding that it works well enough even in that context.
I did not propose that worst case be interpreted as Omega or that it be given any nonstandard referent. I did suggest that "worst case" to describe the Adversary scenario is deceptive to readers, and we should ReplaceTheSymbolWithTheSubstance via a more descriptive phrase like "adversarial superintelligence that knows everything except the bits designated random". This is what the phrase standardly means in computer science, but calling this "worst case analysis" seems to me deceptive, especially if we're trying to conduct a meta-ish debate about the benefits of randomization, rather than talking about some particular algorithm.
Agreed.
Right. But I want to repeat the objection here that we often use pseudorandomness instead of actual randomness, and then the real worst case is that we've gotten a cursed seed. Somewhat less practically, in situations where a real adversary may have access to our hardware, we may have to assume that they can read (or write to!) our RNG.
I think this is a practical scenario in cryptography where your threat model is state-level actors.
If your adversary can read or write bits in your hardware, then what is the purpose of using cryptography?
They may only be able to access your hardware in limited ways. For example, if a hardware "RNG" actually outputs 1,2,3,... encrypted with some key known only to the NSA, that's essentially totally undetectable. But if instead they have the hardware send out extra information over the internet, sooner or later someone will notice and the game will be up.
How does the NSA synchs with your "RNG" is no information is exchanged?
But anyway, if you reasonably believe that your RNG may have been compromised, then you just don't use it.
They don't need to sync for it to be a serious weakness in a cryptosystem. If a system using Khoth's PRNG sends out a billion encrypted messages in its lifetime, then an attacker with the PRNG key needs less than 2^30 tries to decrypt a message sent at an unknown point in that sequence -- a large number, but more than manageable when you consider that a PRNG with a period of 2^80 would be considered weak in the crypto world.
Agreed.
Side channel attacks on hardware are not rare. For example, an adversary might have a way of measuring the power consumption of your CPU as it does RNG calculations. This is not quite the ability to "read or write bits in... hardware", but it is a viable attack to gain information about your, ahem, random numbers.
Sure, but at this point they can also gain information on your keys or the data you wish to encrypt.
Not necessarily. Think wider, not only PCs use encrypted communications. Consider a router, for example, or a remote sensor.
Still, if they can compromise the RNG state in the router/sensor/whatever, they could probably compromise its CPU and/or RAM.
That's not self-evident to me. Passively observing power consumption is much easier than, say, getting inside a SOC in tamper-resistant packaging.