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.
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.