An Asynchronous Coin Toss
The circumstances were such that my thoughts came across an interesting real-life problem which in it's bare-bone form can be formulated as an asynchronous coin toss.
Problem
Suppose Alice and Bob are communicating through mail/e-mail asynchronously. Alice responds when she receives Bob's message and Bob responds when he receives Alice's message. As a result, Alice and Bob cannot synchronize with each other in any way.
Now, Alice and Bob have to toss a coin amongst the two of them. Both of them would like to cheat and win the coin toss if possible. But the other person wouldn't like that. So they want the coin toss to be fair.
Why is this a problem?
Let's look at the simplest approach. Alice communicates her choice of heads or tails to Bob. Bob tosses the coin and sends the outcome to Alice. Can Alice trust whether Bob is sending the correct outcome? As per Alice, Bob could have received Alice's message before the toss and could have manipulated the results.
How can this be done? I'd like the reader to pause and think deeply about the solution. Perhaps return to this a day later? I thought about it and discussed it with my friends for roughly 24 hours before arriving on the solution suddenly after waking up the next morning.
My Solution
Alice will make her choice of heads or tails, encrypt it, and send the encrypted message to Bob. Bob has Alice's choice locked in but cannot read it. Now, Bob can toss a coin, encrypt the outcome, and send this encrypted outcome to Alice. Now, Alice has the outcome of a fair coin toss with her in encrypted form which Bob cannot change. Both will now exchange decryption keys and will come to know who won the coin toss.
An important but perfectly reasonable assumption here is that the encryption algorithm is strong such that it cannot be decrypted into another message using a fake decryption key (atleast in polynomial time): RSA encryption or AES should suffice.
Afterthoughts
I'm sure this problem occurs in real-world systems across the globe often and has a big impact on our daily lives. Perhaps it has a different name or a different formulation. And I'm sure that either my solution or perhaps a better solution is used.