Can you refer me to somewhere to read more about the “usual definitions” that would make this true? If I know the Turing machine, I can compare the output to that Turing machine and be pretty sure it’s not random after running the generator for a while. Or if the definition is just lack of expected correlation with bits playing a functional role, then that’s easy to get. What’s intermediate such that ‘indistinguishable’ randomness means P!=NP?
You don’t sound like you’re now much less confident you’re right about this, and I’m a bit surprised by that!
I got the ladder down so I could get down my copy of Goldreich’s “Foundations of Cryptography”, but I don’t quite feel like typing chunks out from it. Briefly, a pseudorandom generator is an algorithm that turns a small secret into a larger number of pseudorandom bits. It’s secure if every distinguisher’s advantage shrinks faster than the reciprocal of any polynomial function. Pseudorandom generators exist iff one-way functions exist, and if one-way functions exist then P != NP.
If you’re not familiar with PRGs, distinguishers, advantage, negligible functions etc I’d be happy to Skype you and give you a brief intro to these things.
If you’re not familiar with PRGs, distinguishers, advantage, negligible functions etc I’d be happy to Skype you and give you a brief intro to these things.
There are also intros available for free on Oded Goldreich’s FoC website.
Here’s my simplified intuitive explanation for people not interested in learning about these technical concepts. (Although of course they should!) Suppose you’re playing rock-paper-scissors with someone and you’re using a pseudorandom number generator, and P=NP, then your opponent could do the equivalent of trying all possible seeds to see which one would reproduce your pattern of play, and then use that to beat you every time.
In non-adversarial situations (which may be what Eliezer had in mind) you’d have to be pretty unlucky if your cognitive algorithm or environment happens to serve as a distinguisher for your pseudorandom generator, even if it’s technically distinguishable.
Okay, makes sense if you define “distinguishable from random” as “decodable with an amount of computation polynomial in the randseed size”.
EDIT: Confidence is about standard cryptographically strong randomness plus thermal noise being sufficient to prevent expected correlation with bits playing a functional role, which is all that could possibly be relevant to cognition.
Can you refer me to somewhere to read more about the “usual definitions” that would make this true? If I know the Turing machine, I can compare the output to that Turing machine and be pretty sure it’s not random after running the generator for a while. Or if the definition is just lack of expected correlation with bits playing a functional role, then that’s easy to get. What’s intermediate such that ‘indistinguishable’ randomness means P!=NP?
You don’t sound like you’re now much less confident you’re right about this, and I’m a bit surprised by that!
I got the ladder down so I could get down my copy of Goldreich’s “Foundations of Cryptography”, but I don’t quite feel like typing chunks out from it. Briefly, a pseudorandom generator is an algorithm that turns a small secret into a larger number of pseudorandom bits. It’s secure if every distinguisher’s advantage shrinks faster than the reciprocal of any polynomial function. Pseudorandom generators exist iff one-way functions exist, and if one-way functions exist then P != NP.
If you’re not familiar with PRGs, distinguishers, advantage, negligible functions etc I’d be happy to Skype you and give you a brief intro to these things.
There are also intros available for free on Oded Goldreich’s FoC website.
Here’s my simplified intuitive explanation for people not interested in learning about these technical concepts. (Although of course they should!) Suppose you’re playing rock-paper-scissors with someone and you’re using a pseudorandom number generator, and P=NP, then your opponent could do the equivalent of trying all possible seeds to see which one would reproduce your pattern of play, and then use that to beat you every time.
In non-adversarial situations (which may be what Eliezer had in mind) you’d have to be pretty unlucky if your cognitive algorithm or environment happens to serve as a distinguisher for your pseudorandom generator, even if it’s technically distinguishable.
Okay, makes sense if you define “distinguishable from random” as “decodable with an amount of computation polynomial in the randseed size”.
EDIT: Confidence is about standard cryptographically strong randomness plus thermal noise being sufficient to prevent expected correlation with bits playing a functional role, which is all that could possibly be relevant to cognition.
Decoding isn’t the challenge; the challenge is to make a guess whether you’re seeing the output of the PRG or random output. Your “advantage” is
Adv_PRG[Distinguisher] = P(Distinguisher[PRG[seed]] = “PRG”) - P(Distinguisher[True randomness] = “PRG”)
Note that this is standard notation when one discusses pseudorandom generators. Hence Ciphergoth’s comment about “the usual definitions.”
(Nods.)