I am seeking a mathematical construct to use as a logical coin for the purpose of making hypothetical decision theory problems slightly more aesthetically pleasing. The required features are:
Unbiased. It gives (or can be truncated or otherwise resolved to give) a 50⁄50 split on a boolean outcome.
Indexable. The coin can be used multiple times through a sequence number. eg. “The n-th digit of pi is even”.
Intractable. The problem is too hard to solve. Either because there is no polynomial time algorithm to solve it or just because it is somewhat difficult and the ‘n’ supplied is ridiculous. eg. “The 3^^^3 digit of pi is even”.
Provable or otherwise verifiable. When the result of the logical coin is revealed it should be possible to also supply a proof of the result that would convince a mathematician that the revealed outcome is correct.
Simple to refer to. Either there is a common name for the problem or a link to a description is available. The more well known or straightforward the better.
NP-complete problems have many of the desired features but I don’t know off the top of my head any that can be used as indexable fair coin.
It looks to me like you want a cryptographically secure pseudo-random number generator restricted to the output space {0, 1} and with a known seed. That’s unbiased and intractable pretty much by definition, indexable up to some usually very large periodicity, and typically verifiable and simple to refer to because that’s standard practice in the security world.
There’s plenty of PRNGs out there, and you can simply truncate or mod their outputs to give you the binary output you want; Fortuna) looks like a strong candidate to me.
(I was going to suggest the Mersenne twister, which I’ve actually implemented before, but on further examination it doesn’t look cryptographically strong.)
That works with caveats:
You can’t just publish the seed in advance, because that would allow the player to generate the coin in advance. You can’t just publish the seed in retrospect, because the seed is an ordinary random number, and if it’s unknown then you’re just dealing with an ordinary coin, not a logical one. So publish in advance the first k bits of the pseudorandom stream, where k > seed length, thus making it information-theoretically possible but computationally intractable to derive the seed; use the k+1st bit as the coin; and then publish the seed itself in retrospect to allow verification.
Possible desiderata that are still missing: If you take multiple coins from the same pseudorandom stream, then you can’t allow verification until the end of the whole experiment. You could allow intermediate verification by committing to N different seeds and taking one coin from each, but that fails wedrifid’s desideratum of a single indexable problem (which I assume is there to prevent Omega from biasing the result via nonrandom choice of seed?).
I can get both of those desiderata at once using a different protocol:
Pick a public key cryptosystem, a key, and a hash function with a 1-bit output. You need a cryptosystem where there’s only one possible signature of any given input+key, i.e. one that doesn’t randomize encryption. To generate the Nth coin: sign N, publish the signature, then hash the signature.
My first idea is to use something based on cryptography. For example, using the parity of the pre-image of a particular output from a hash function.
That is, the parity of x in this equation:
f(x) = n, where n is your index variable and f is some hash function assumed to be hard to invert.
This does require assuming that the hash function is actually hard, but that both seems reasonable and is at least something that actual humans can’t provide a counter example for. It’s also relatively very fast to go from x to n, so this scheme is easy to verify.
No candidates, but I’d like to point out that your unbiased requirement may perhaps be omitted, conditional on the implementation.
If you have a biased logical coin, you poll the coin twice until the results differ, and then you pick the last result when they do differ. That results in an unbiased logical coin.
My first instinct is to bet on properties of random graphs, but that’s not my field.
If you have a biased logical coin, you poll the coin twice until the results differ, and then you pick the last result when they do differ. That results in an unbiased logical coin.
I am seeking a mathematical construct to use as a logical coin for the purpose of making hypothetical decision theory problems slightly more aesthetically pleasing. The required features are:
Unbiased. It gives (or can be truncated or otherwise resolved to give) a 50⁄50 split on a boolean outcome.
Indexable. The coin can be used multiple times through a sequence number. eg. “The n-th digit of pi is even”.
Intractable. The problem is too hard to solve. Either because there is no polynomial time algorithm to solve it or just because it is somewhat difficult and the ‘n’ supplied is ridiculous. eg. “The 3^^^3 digit of pi is even”.
Provable or otherwise verifiable. When the result of the logical coin is revealed it should be possible to also supply a proof of the result that would convince a mathematician that the revealed outcome is correct.
Simple to refer to. Either there is a common name for the problem or a link to a description is available. The more well known or straightforward the better.
NP-complete problems have many of the desired features but I don’t know off the top of my head any that can be used as indexable fair coin.
Can anyone suggest some candidates?
It looks to me like you want a cryptographically secure pseudo-random number generator restricted to the output space {0, 1} and with a known seed. That’s unbiased and intractable pretty much by definition, indexable up to some usually very large periodicity, and typically verifiable and simple to refer to because that’s standard practice in the security world.
There’s plenty of PRNGs out there, and you can simply truncate or mod their outputs to give you the binary output you want; Fortuna) looks like a strong candidate to me.
(I was going to suggest the Mersenne twister, which I’ve actually implemented before, but on further examination it doesn’t look cryptographically strong.)
That works with caveats: You can’t just publish the seed in advance, because that would allow the player to generate the coin in advance. You can’t just publish the seed in retrospect, because the seed is an ordinary random number, and if it’s unknown then you’re just dealing with an ordinary coin, not a logical one. So publish in advance the first k bits of the pseudorandom stream, where k > seed length, thus making it information-theoretically possible but computationally intractable to derive the seed; use the k+1st bit as the coin; and then publish the seed itself in retrospect to allow verification.
Possible desiderata that are still missing: If you take multiple coins from the same pseudorandom stream, then you can’t allow verification until the end of the whole experiment. You could allow intermediate verification by committing to N different seeds and taking one coin from each, but that fails wedrifid’s desideratum of a single indexable problem (which I assume is there to prevent Omega from biasing the result via nonrandom choice of seed?).
I can get both of those desiderata at once using a different protocol: Pick a public key cryptosystem, a key, and a hash function with a 1-bit output. You need a cryptosystem where there’s only one possible signature of any given input+key, i.e. one that doesn’t randomize encryption. To generate the Nth coin: sign N, publish the signature, then hash the signature.
My first idea is to use something based on cryptography. For example, using the parity of the pre-image of a particular output from a hash function.
That is, the parity of x in this equation:
f(x) = n, where n is your index variable and f is some hash function assumed to be hard to invert.
This does require assuming that the hash function is actually hard, but that both seems reasonable and is at least something that actual humans can’t provide a counter example for. It’s also relatively very fast to go from x to n, so this scheme is easy to verify.
Hash functions map multiple inputs to the same hash, so you would need to limit the input in some other way, and that makes it harder to verify.
No candidates, but I’d like to point out that your unbiased requirement may perhaps be omitted, conditional on the implementation.
If you have a biased logical coin, you poll the coin twice until the results differ, and then you pick the last result when they do differ. That results in an unbiased logical coin.
My first instinct is to bet on properties of random graphs, but that’s not my field.
That’d work. I like it!