How to simultaneously exchange information?

October 26, 2009 2:27 PM

How to simultaneously exchange information?

Say a friend and I want to exchange pieces of information, but it is very important that we reveal the information at the same time (equivalently: neither of us know the other's info at the time we commit to our own announcement). if we are in the same room, this is easy, we both write our information on slips of paper and then exchange slips. If we are not in the same room, there is no obvious analogue. For example, simultaneously sending emails does not work, as he could get my email, view my information, alter his announcement, and then send his email all in a few seconds.

If an example would help, say that we are both to name positive whole numbers, and if the sum of our numbers is odd, I have to do an unpleasant task, while if it is even, he has to do the task. Obviously if he can see my information before committing to his announcement, the interaction is trivialized. So we want to find a way to randomize who gets the task using this method.

So how can we do this if not in the same room (presumably over the Internet)?

One thing reducing the difficulty of the problem: we are friends, so we will not get caught lying to each other (and if we are, a suitable punishment can be arranged). However a solution that would allow him to lie without my knowing won't work.

posted by deadweightloss to science & nature (40 comments total)

Assuming this is just for a game theory experiment (as your tags suggest) and not for some serious dispute resolution with real-world consequences…

Set up a free email account somewhere. Both of you send an email to it, and then have somebody designated to check the account afterward. Or both of you check it together to maximize accountability.
posted by The Winsome Parker Lewis at 2:30 PM on October 26

Yeah, this is what escrow is for.
posted by rokusan at 2:33 PM on October 26

You use some sort of escrow service? You both give the info to a third party who then controls when it's revealed. Unless your question is how to do this without a third-party mediator.
posted by GuyZero at 2:33 PM on October 26

Can we assume that the transmission medium is both lossless and trusted? Otherwise you run into the Two Generals' Problem and Man-in-the-Middle attacks.

In practice and for small amounts of information the simplest mechanism I can think of is a real time video chat with sufficient fidelity to allow both parties to see the other party writing the information on a slip of paper then revealing the slips simultaneously. I can't tell if you want a generalizable, formally-correct method, though.
posted by jedicus at 2:34 PM on October 26 [2 favorites has favorites]

This is principally a thought experiment (though it came up because I had exactly this need). A mutually trusted third party solves the problem, certainly, so let's assume this is not available. The free email account is a good idea, though 1-absent a trusted third party to set it up, how do I know he doesn't know the password, and 2-checking the account together requires us to be in the same room, at which point we can just do slips of paper.
posted by deadweightloss at 2:34 PM on October 26

How about doing it in two steps?
1) Sending each other (by e-mail) an encrypted whole number.
2) Once you both received the first e-mail, sending each other (again, by e-mail) the password that decrypts the first e-mail.
posted by spaghettification at 2:35 PM on October 26 [2 favorites has favorites]

@spaghettification: that moves the problem to the timing of the second e-mail.
posted by devnull at 2:37 PM on October 26

Some form of encryption containing the payload text would work too. You exchange enciphered information, and once you each have it, exchange keys. Then even if the other person has the key first it doesn't matter, since you already have the payload.

Some algorithms person here on MeFi should now jump in to explain exactly what sort of cipher to use to ensure that a second key could not be sent to produce a different result, of course. Padding the payload text with some reference text (part of a famous book, for example) might help. It'd also make it more crackable. Tradeoffs.
posted by rokusan at 2:37 PM on October 26 [2 favorites has favorites]

It's not even clear that it works in person; he could write nothing on the slip, and read yours and only reveal his bad faith.
posted by gensubuser at 2:37 PM on October 26

This may be my "when you have a hammer everything looks like a nail" approach, but you can solve this problem pretty easily with cryptographic tools. Basically, what you need is a one-way hash function. Both of you basically create a message which is your piece of information, and hash it. So you each have your piece if information, I, and the hash h(I).

You then exchange hashes with each other. Once you each have the other's hash, you exchange the actual answer. You can't (easily) cheat because the hash functions as a commitment to the answer (without revealing the answer itself).
posted by axiom at 2:37 PM on October 26

No, devnull, because even if the second mail is delayed or out of sync, it's too late to change the content of the first message, which contained the official info. All that can change is the passphrase... but see my second para caveat/concern about mutable ciphers.
posted by rokusan at 2:38 PM on October 26

I like the encrypted information, followed by a key, but couldn't he arrange his encrypted announcement so that different keys could produce different numbers?
posted by deadweightloss at 2:38 PM on October 26

@gensubuser: if he writes nothing in person, I will at least know that he is trying to deceive me, and can then exact revenge accordingly (since we are friends, we interact repeatedly). So that seems like much less of a problem than the possibility of his deceiving me online and my not knowing about it.
posted by deadweightloss at 2:40 PM on October 26

Type the number into a text file. Compress the text file into a password-protected ZIP file. Email it. Later, send the ZIP password.
posted by The Winsome Parker Lewis at 2:41 PM on October 26 [1 favorite has favorites]

Winsome Parker Lewis: that is a good idea!

Everyone: any reason this would not work?
posted by deadweightloss at 2:44 PM on October 26

Given ciphertext and plaintext, it isn't possible to find a key that will produce that plaintext. Don't worry about it.

A bigger problem is that your friend could conceivably encrypt all the values (say) from 0 to 100, and check each one against the encrypted text you sent him. For this reason, it is very important to include some extra random information in the text you encrypt (called salt).
posted by miyabo at 2:46 PM on October 26 [1 favorite has favorites]

Both people upload their numbers as a text document in a password protected .rar on a file sharing service or via e-mail. Once both people have downloaded their file with the number you exchange passwords over instant message or a phone call.

This is essentially analogous to exchanging slips of paper only here the flip is receiving the password. This requires the same amount of faith that both parties have written something on their slip of paper, and the flip can be nearly simultaneous with reactions and responses in real time.
posted by CheshireCat at 2:48 PM on October 26

How does that differ from the earlier recommendations to encrypt? Aside from implying the use of really really weak zip encryption?
posted by floam at 2:49 PM on October 26

Really curious as to what the real-world problem was that made you think of this.
posted by meadowlark lime at 2:50 PM on October 26 [1 favorite has favorites]

floam: I see two differences. One, it's simpler, and two, we need a method where only one key could conceivably work on the encrypted data.

I'm not particularly knowledgeable on encryption, but it seems if my friend is devious enough, he could send me encrypted information that could be decoded as an odd number (say) if he sends key 1, and as an even number if he sends key 2. With password-protected files, presumably there is only one key (the password) that will do anything with the encrypted data. I certainly could be wrong about this, though.
posted by deadweightloss at 2:54 PM on October 26

floam: Simply encrypting a string, particularly one containing only a single integer, does leave open the possibility deadweightloss suggested of creating a pair of keys that will return different results as needed. But there's no way to do this with a password-protected ZIP file. There may be other weaknesses inherent in the format though, if someone really knows his way around a password cracker...
posted by The Winsome Parker Lewis at 2:54 PM on October 26

(Then again, there's no such thing as 100% secure security, you just have to do the best you possibly can and stay a step ahead of those whom you're securing against!)
posted by The Winsome Parker Lewis at 2:56 PM on October 26

meadowlark lime: it's pretty trivial. We've done a couple of friendly pools on who among many will meet some future criterion (say, who will win the 2010 NCAA championship, as an example). Our pools involve anteing a fixed amount of money and then bidding on those eligible one at a time, with the higher bidder paying the average of the two bids out of his anted money. Our bids obviously need to be exchanged simultaneously, or the person going second will always either bid one cent more or one cent less than the person whose bid is revealed first.

The need to do this online came up when my friend had to work from home for a couple of weeks.
posted by deadweightloss at 3:01 PM on October 26

With a password protected file it seems like it becomes a social problem rather than a technical one. Assuming the two people are coordinating to send the files at roughly the same time, the weak security isn't an issue as long as the file can't be opened immediately upon receiving it (so as to alter the reply) and as long as the results can't be altered by the password that is given. The idea is to conduct the exchange in such a way as to minimize any chances or appearances of impropriety on either side rather than having to rely on total security and uncoordinated actions. If they then hack the file after the exchange has been made it's still the same end result as having to delay for the password.
posted by CheshireCat at 3:03 PM on October 26

This is a well-studied problem. See the wikipedia article on Commitment scheme or Mental poker
posted by 0xFCAF at 3:11 PM on October 26 [3 favorites has favorites]

I cannot see a way of doing this without a trusted 3rd party, who is
able to judge the validity and truthfulness of the statements being made.

Encrypting files and then exchanging keys, does nothing to prevent
a person to learn all the "secrets" of the first person without divulging
anything but an ascii lol kitty.

A system of multiple encryptions could possible be used to divulge only
a small part of the content at a time.

So each person would have a continue/stop decision at each step.

Under this mechanism a word, a letter, or a sentence could be decoded at a time.

This however does assume some symmetry in the length of the messages.
It also assumes that either party will have the ability to validate the truthfulness
of the message.
posted by digividal at 3:19 PM on October 26

0xFCAF: very interesting, thanks. I like this line: "A commitment scheme can either be perfectly binding (it is impossible for Alice to alter her commitment after she has made it, even if she has unbounded computational resources) or perfectly concealing (it is impossible for Bob to find out the commitment without Alice revealing it, even if he has unbounded computational resources) but not both." This may mean the problem is theoretically impossible (my particular problem is made easier by the fact that neither of us wishes to b caught lying, even if it does give us a temporary advantage).

digividal:gradually revealing bits of the information certainly does make cheating less likely, but there would have to be some point at which exactly one of us has the others complete information, at which point the problem returns.
posted by deadweightloss at 3:30 PM on October 26

Okay, let's say that Google Docs had the functionality to tell you not only the precise times that a document was revised but also the precise times that it was viewed by each user who had access to it.

You could each create a Google document with your information in it. Then, via IM, you simultaneously share the URLs to access the documents. You can check the revision history of your friend's document to make sure he/she didn't change it after accessing your document, and you can check the time at which your friend accessed YOUR document to make sure it was before he/she IMed you the URL to his/her document (so as to preclude the possibility that your friend had a bunch of different documents set up and chose which one to send you after seeing your document). This, of course, assumes that all clocks are perfectly synchronized. And that Google docs has this functionality, which it doesn't.

But if we're assuming no automated involvement (i.e. the computer checking the document instantaneously and IMing faster than a human being could), just exchanging the URLs of the Google docs simultaneously via IM would be trustworthy enough. You can even do the IM exchange some designated amount of time after creating the Google docs, so there's no ambiguity about what happened first when you're looking at time tags.

(You could also each add your number to a random Wikipedia page and then IM each other the URLs simultaneously, since Wikipedia revisions are tracked. But that would be vandalism so you shouldn't do that.)
posted by pluckemin at 3:48 PM on October 26

Applied Cryptographyhas protocols for this kind of thing and is a classic in the field (plus it's actually a fun read insofar as crypto textbooks go). If you like these kinds of questions, you'll like the book.
posted by zachlipton at 3:54 PM on October 26

Well, pluckemin's last answer isn't too bad. Set up a private wiki hosted on a neutral server, with two pages: "Alice's Numbers" and "Bob's numbers". Make an agreement to post numbers at exactly X time by the server clock. Any deviation from posting at or before X time is a fault and a re-do. Any editing to the numbers before or after X time is cheating.

I say "at or before" because clearly posting before time X cannot benefit a person and only hurts them.

Alternately, use a service like multiplayer Rock Paper Scissors which essentially would act as an automated escrow.
posted by muddgirl at 4:02 PM on October 26

There are delay-email services such as timecave, where you send a message and it will get sent on to the receiver at a certain time in the future. Assuming that such a service gives accurate time stamps for when the message was first sent, you could both agree to send your messages within a certain timeslot, delayed by a certain time, and then you would both get the messages after the delay without any chance of going back and changing the figure.
posted by Jabberwocky at 4:58 PM on October 26 [2 favorites has favorites]

Does it have to be over the internet? Can't you each agree to mail it the old fashioned way on the same day, and confirm later that the other person's letter has the proper postmark-date on it? Since letters always take at least one day to get there, ensuring that the letters have the same postmark-date on them means neither envelope's contents was based on the other's.
posted by losvedir at 7:26 PM on October 26

Encrypting files and then exchanging keys, does nothing to prevent a person to learn all the "secrets" of the first person without divulging anything but an ascii lol kitty.

That's taken care of by the second part of the OP's protocol, where both secrets are summed, and the decision is made depending on the sum's evenness or oddness. Until the secrets have been successfully decrypted at both ends, no decision is possible; once they have been, both ends will get the same result.

Wikipedia has a neat coin toss replacement that doesn't involve simultaneous exchanges.
posted by flabdablet at 12:31 AM on October 27

Along the same lines as that coin toss replacement, here's a similar one that's easy to find the tools for:

1. Alice generates a random string of 20 lowercase letters at random.org (for example, rzcmnppzdljacllmmzzs)
2. Alice pastes the random string into a SHA-256 hash generator and sends Bob the resulting hash code (the example result is 09b56caac10cd77bbea33668fdb2ddbc52ee9b7f8ce95fbe476b42d682fe131c)
3. Bob calls the toss by guessing whether the first character of Alice's random string (which he has not yet seen) is a-m (heads) or n-z (tails) and sends that decision to Alice.
4. Alice sends Bob the random string. Bob can paste it into the same SHA-256 generator to verify that Alice has not switched strings, and both parties know whether Bob called the the toss correctly.

The point of both of these is that simultaneous two-way exchange is overkill for a simulated coin toss.
posted by flabdablet at 1:18 AM on October 27 [1 favorite has favorites]

Hmmm. That's not really quite stupidly excessively obsessively secure enough. Better would be for Alice to use a 20-character string of mixed upper and lower case letters in step 2, and for Bob to call the toss on whether the first character is upper case. This would be rather less practical over a voice link between Alice and Bob, though.
posted by flabdablet at 1:28 AM on October 27

Most of the answers here rely on moving the problem elsewhere: exchanging urls or passwords or passphrases or some other secret. This doesn't solve the problem because if the secret reveals the information you want to exchange, then it is the same as revealing that information. Hashes won't help because you can't verify the hashes or the hashed information is legitimate.

You need an escrow service (which you said you don't want) who can verify the information and then reveal it to both of you.

If you don't want that I would ask a real cryptographer. This kind of question is probably covered in the first class.
posted by devnull at 1:47 AM on October 27

This doesn't solve the problem because if the secret reveals the information you want to exchange, then it is the same as revealing that information.

Not necessarily. If I send somebody a cryptographically secure hash of a piece of information that only I hold, I have not revealed any part of that information that's computationally feasible to recover, as long as my information is a member of a sufficiently large set of possibilities. What I have given them is a way to test whether what I subsequently send them is or is not the same as what was used to generate the hash.
posted by flabdablet at 2:05 AM on October 27

Not necessarily.

How do they know the cryptographically secure hash of information you give them is a hash of the same information that they want?
posted by devnull at 3:28 AM on October 27

How do they know the cryptographically secure hash of information you give them is a hash of the same information that they want?

As the OP stated, the goal is to prevent one person from modifying their answer based on the response of the other. He doesn't care if the person sends a garbage hash, because he will know that the other person cheated when it comes time to share the actual data. If the hash of the data doesn't match the hash sent earlier, then the sender will be considered a cheater (and will be punished accordingly).
posted by helios at 4:16 AM on October 27

Way late, but I think a Google Docs spreadsheet would work. They feature real-time editing. Basically, you'd each pick a cell to paste your info into. Then you'd just need voice chat or telephone to countdown to paste. You could even practice a few times to get the feel of it.
posted by donnagirl at 3:08 PM on October 30