1
$\begingroup$

When we take the coin flip in Blum's algorithm in "Coin flipping by telephone a protocol for solving impossible problems", where Alice and Bob both want ownership over the same car, then one party (the adversary / Alice) can abort the protocol. Provided there does exist a powerful third party (e.g. the law), the protocol can be extended, to give the car to Bob in case Alice aborts. This makes the algorithm game-theoretical fair, because Alice no longer has any desire to abort.

But let's say we–the general public–and Bob do not desire a specific outcome, but a random outcome, yet Alice still desires the car. The set of desired results is thus not longer disjunct. Now Alice can can calculate the result and if she decides it is not in her favor, she can abort. Bob will have to flip the coin again, providing Alice a second chance for her desired outcome. Bob could also use the first flip, but this would still give Alice two options to chose from. Since Alice can chose from two random numbers, it's not longer true random to Bob. Yet we can't punish Alice by giving the car to Bob, because the result would not be true random either.

If we instead take the Commit-Reveal scheme, the party acting last would also get the choice. My question is thus, does there exist a protocol which can guarantee a random selection if Bob has honest intentions and Alice may wants to abort?

To me, the issue of game-theoretical fairness lies in the punishment being contained in the coin flip itself. In a real-world we would probably resort to independent measures like fines or prison sentences, but it's hard to prove their impact on game-theoretical fairness, so it would be much better to have a formal protocol which can guarantee a random number while punishing Alice.

Edit 1: I already see there are some issues with my approach. Even if we maintain the rule to give the car to Bob in case Alice aborts, Alice would always take the random choice to maximize profit and never aborts, so we never end up with the non-random scenario of giving the car to Bob. I need to extend the problem a bit further to get to the core issue i originally wanted to discuss: Alice does not want the car for herself, but she has a hidden preference for either Alice or Bob which we don't know. But we and Bob want a random selection So we can't punish her by giving the car to Bob, because this could have been her intention and she would abort the protocol, resulting in the aforementioned issue of giving her an advantage.

$\endgroup$
2
  • 1
    $\begingroup$ If I understand correctly, why not set the rule to be that Bob independently flips a coin if Alice aborts? That satisfies Bob's preference and is the best Alice can hope for with the honest protocol. You'd need to show that Alice cannot abort after learning the outcome of the honest protocol, I suppose (e.g., if she aborts after that point, the outcome is already decided for Bob and third parties). $\endgroup$
    – Sam Jaques
    May 8, 2023 at 12:27
  • 1
    $\begingroup$ @SamJaques If Bob flips a random coin after Alice aborts, Alice has a chance larger than 50% to achieve her preference. She can either stay with the protocol if she knows her desired outcome will become true after revealing her secret, or if the outcome will be bad, she can abort and force Bob to flip again increasing her overall chances to 75%. Thus it's no longer true random. $\endgroup$
    – Mangudai
    May 8, 2023 at 13:14

1 Answer 1

0
$\begingroup$

If the goal is to design a 2-party protocol such that outputs a fair coin even when one party could leave early, then that is impossible due to Cleve 1986, STOC. Roughly, the paper says that for any protocol of $R$ rounds, a malicious party that may abort early can deviate the outcome of the coin by $\Omega(1/R)$. This impossibility holds no matter what cryptographic assumption is used in the protocol. Recent results strengthened the bounds on the deviation.

The proof idea of Cleve is similar to what you mentioned: the malicious party knows the protocol, and it will use the protocol to choose a round to abort. That is, using the current state of the malicious party, it estimates the outcome had it chosen to abort in the current round, where the estimation is given by the protocol.

$\endgroup$
1
  • $\begingroup$ To put this in context of game-theoretical fairness, because Bob does want randomness and Alice' preference is hidden from the public, there is no way to make her not abort. $\endgroup$
    – Mangudai
    Aug 3, 2023 at 9:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.