5 ms·

What if the coin's bias changes from flip to flip, perhaps influenced by its earlier results? Is there a solution for this?

LeonB 5y ago
Without knowing what sort of influence it has — it’s difficult to construct a general method, though, please check my idea and see if this achieves the purpose. First you find a gambler, any gambler and ask them to show you the lowest denomination coin they have, and get them to verify for you that it is a fair coin. Now demonstrate your weird coin to them, and when they are amazed by its properties, swap it with them for the fair coin. Done.
paxys 5y ago
This makes me think – is a coin with a truly random bias from flip to flip any different from a perfectly fair coin?
- mannerheim 5y ago
  Depends on what you mean by 'truly random'. A distribution can be skewed, in which case the bias would itself be biased and then clearly different from a perfectly fair coin. Assuming you mean a uniform distribution, we can calculate this. Been a while since I've done stats, so bear with me... We can first argue from symmetry that we should expect as many heads as tails. But this doesn't mean that this is necessarily the same distribution as a perfectly fair coin (Bernoulli with p = 0.5). Anyway, the distributions we have here are a Bernoulli distribution and a uniform distribution X ~ {0, 1}; 0 with probability 1-q, 1 with probability q q ~ [0, 1], uniformly The expected value of X is E[X] = 0 * p(0) + 1 * p(1) = p(1) I think we could prove p(1) = E[q], but I'm honestly not sure, and don't know if that holds up in general. But from the above, we know it's 0.5 anyway. Now, we need higher moments: E[X^n] = 0^n * p(0) + 1^n * p(1) = p(1) = 0.5 The moment generating function of a probability distribution is defined as M_X(t) = E[e^(tX)]. There's a theorem in probability that two distributions with the same MGF are the same. You can see from the above that this has the same moments as a Bernoulli distribution with p = 0.5. Hence, a biased coin with a random uniform bias should be identical to a Bernoulli distribution. In fact, I believe the above argument works for not just uniform bias, but any random bias that is symmetric about p = 0.5.
  - eru 5y ago
    Minor application: In Dungeons and Dragons, a challenge is typically resolved by taking some number that's a difference between difficulty of the challenge and your character's skill, and comparing it to the roll of a twenty sided die. (Higher is better for you.) Some dungeons and dragons game masters sometimes can't decide how hard to make a challenge. So they roll one die to set a random challenge, and then proceed as normal with a second die roll. With the same logic as in your comment above, I think you should be able to show that this 'randomized challenged' behaves exactly the same as a challenge of difficulty 10?
goodpoint 5y ago
There isn't. No matter how clever your cleanup/filter algorithm is, you can always more cleverly biased "coin" that defeats it. (Assuming the "coin" is a complex device) That's why proving that a hardware RNG is secure is very difficult.
- eru 5y ago
  That depends! Look at the following setup: First, you pick a cleanup/filter algorithm. Second, your adversary gets to study your algorithm and hand you a dastardly clever 'coin'. [0] Third, your algorithm runs, but has access to a second unbiased source of randomness. [1] Under those circumstances, your algorithm has a chance! Basically, you use your extra source of randomness to create a secret key; then use that key to encrypt your adversary's bit-stream from their "coin". If your encryption algorithm has 'ciphertext indistinguishability under chosen-plaintext attack' https://en.wikipedia.org/wiki/Chosen-plaintext_attack https://en.wikipedia.org/wiki/Chosen-plaintext_attack this scheme should roughly work, unless your attacker has exponentially more computing power than you do. [0] To make the challenge fair, assume that our adversary has an obligation to put at least a bit of entropy into their "coin". Eg by having an unrelated third-party pick an arbitrary bit-stream that our adversary has to transmit via their "coin". How the adversary encodes that is up to them; and they can be as wasteful as they like. They just have to be able to decode it, too. [1] You have to use that source sparingly to make it a challenge.
  - goodpoint 5y ago
    There are two problems with that: 1) If you expected the filter algorithm to detect and warn on bad/malicious randomness, this doesn't work 2) More importantly, if you have a CSPRNG and a source of randomness as part of your filter you can simply throw away the "coin" because just implemented your own RNG.
    - eru 5y ago
      I don't expect (1). For (2), yes, it's essentially that; but you add some extra mechanisms around to make use of any entropy sources you can find, even if some of them are tainted. Basically what /dev/random does in Linux: they still use the potentially tainted 'coins' despite having a CSPRNG.

LeonB 5y ago

Without knowing what sort of influence it has — it’s difficult to construct a general method, though, please check my idea and see if this achieves the purpose. First you find a gambler, any gambler and ask them to show you the lowest denomination coin they have, and get them to verify for you that it is a fair coin. Now demonstrate your weird coin to them, and when they are amazed by its properties, swap it with them for the fair coin. Done.

paxys 5y ago

This makes me think – is a coin with a truly random bias from flip to flip any different from a perfectly fair coin?

mannerheim 5y ago
Depends on what you mean by 'truly random'. A distribution can be skewed, in which case the bias would itself be biased and then clearly different from a perfectly fair coin. Assuming you mean a uniform distribution, we can calculate this. Been a while since I've done stats, so bear with me... We can first argue from symmetry that we should expect as many heads as tails. But this doesn't mean that this is necessarily the same distribution as a perfectly fair coin (Bernoulli with p = 0.5). Anyway, the distributions we have here are a Bernoulli distribution and a uniform distribution X ~ {0, 1}; 0 with probability 1-q, 1 with probability q q ~ [0, 1], uniformly The expected value of X is E[X] = 0 * p(0) + 1 * p(1) = p(1) I think we could prove p(1) = E[q], but I'm honestly not sure, and don't know if that holds up in general. But from the above, we know it's 0.5 anyway. Now, we need higher moments: E[X^n] = 0^n * p(0) + 1^n * p(1) = p(1) = 0.5 The moment generating function of a probability distribution is defined as M_X(t) = E[e^(tX)]. There's a theorem in probability that two distributions with the same MGF are the same. You can see from the above that this has the same moments as a Bernoulli distribution with p = 0.5. Hence, a biased coin with a random uniform bias should be identical to a Bernoulli distribution. In fact, I believe the above argument works for not just uniform bias, but any random bias that is symmetric about p = 0.5.
- eru 5y ago
  Minor application: In Dungeons and Dragons, a challenge is typically resolved by taking some number that's a difference between difficulty of the challenge and your character's skill, and comparing it to the roll of a twenty sided die. (Higher is better for you.) Some dungeons and dragons game masters sometimes can't decide how hard to make a challenge. So they roll one die to set a random challenge, and then proceed as normal with a second die roll. With the same logic as in your comment above, I think you should be able to show that this 'randomized challenged' behaves exactly the same as a challenge of difficulty 10?

goodpoint 5y ago

There isn't. No matter how clever your cleanup/filter algorithm is, you can always more cleverly biased "coin" that defeats it. (Assuming the "coin" is a complex device) That's why proving that a hardware RNG is secure is very difficult.

eru 5y ago
That depends! Look at the following setup: First, you pick a cleanup/filter algorithm. Second, your adversary gets to study your algorithm and hand you a dastardly clever 'coin'. [0] Third, your algorithm runs, but has access to a second unbiased source of randomness. [1] Under those circumstances, your algorithm has a chance! Basically, you use your extra source of randomness to create a secret key; then use that key to encrypt your adversary's bit-stream from their "coin". If your encryption algorithm has 'ciphertext indistinguishability under chosen-plaintext attack' https://en.wikipedia.org/wiki/Chosen-plaintext_attack https://en.wikipedia.org/wiki/Chosen-plaintext_attack this scheme should roughly work, unless your attacker has exponentially more computing power than you do. [0] To make the challenge fair, assume that our adversary has an obligation to put at least a bit of entropy into their "coin". Eg by having an unrelated third-party pick an arbitrary bit-stream that our adversary has to transmit via their "coin". How the adversary encodes that is up to them; and they can be as wasteful as they like. They just have to be able to decode it, too. [1] You have to use that source sparingly to make it a challenge.
- goodpoint 5y ago
  There are two problems with that: 1) If you expected the filter algorithm to detect and warn on bad/malicious randomness, this doesn't work 2) More importantly, if you have a CSPRNG and a source of randomness as part of your filter you can simply throw away the "coin" because just implemented your own RNG.
  - eru 5y ago
    I don't expect (1). For (2), yes, it's essentially that; but you add some extra mechanisms around to make use of any entropy sources you can find, even if some of them are tainted. Basically what /dev/random does in Linux: they still use the potentially tainted 'coins' despite having a CSPRNG.