Last week, a friend and I had to arrange an in-person meeting after work, by email. He’s based on the Upper East Side, and I’m in Chelsea. Neither one of us wanted to make the trek to the other’s office, and there was no logical place “in between” where we’d have a quiet space.
The obvious solution would be to flip a coin, which he suggested. But how do we know that the other is telling the truth?
The procedure for having Alice and Bob flip a coin over the phone is actually fairly simple. (Conveniently, my friend’s name begins with a ‘B’, so I’ll make him Bob, and I’ll be Alice).
First, Alice flips a coin, but keeps the result of the coin flip secret. Let’s say that ‘H’ is 1, and ’T’ is 0.
Then, Alice finds a book – (almost) any book will do, as long as Bob has a copy of the book as well. She picks an arbitrary page in the book. If the coin flip was H (1) she should pick an odd page; otherwise, she should pick an even page. She notes both the page number and the first two words on that page.
Then, Alice emails Bob the first two words, and asks him to guess whether the page is even or odd. After Bob reveals his guess, Alice reveals the page number. Since Bob has a copy of the same book, he can verify that Alice is telling the truth about the parity of the page number (ie, whether the number is odd or even).
This protocol works because it is easy to find the first two words on a page, but it is hard to find a page that begins with a given pair of words. This serves the purpose of a one-way-function (a function that is hard to invert). By telling Bob the first two words, Alice is telling Bob a signature, and promising that she knows a value that produces that signature. Because Bob has a copy of the book, he is able to verify this signature.
A few interesting things to note about this technique, which is known as a commitment scheme:
-
If Alice only chooses a single, common word (like ‘the’), it would be easy for her to find both an odd page and an even page that start with that word. This would let Alice change the outcome of the coin flip after Bob makes his guess.
-
If Alice chooses too many words (such as an entire sentence), she runs the risk of providing enough context for Bob to figure out where to find the sentence (particuarly if he has read the book and knows the plot).
-
The ideal book is one that both Alice and Bob possess, but which neither one has read, for the above reason.
-
The book should be a work of fiction, as nonfictional books tend to have an index that provides a mapping of words -> page numbers.
-
This technique assumes that Bob does not have access to a digital version of the book that is easily searchable.
There are certainly a few ways in which this procedure could be cheated – either to guarantee a certain outcome, or to tip the results in one’s own favor. But in cryptography, we sometimes make certain concessions (such as assuming an “honest but curious” adversary, as opposed to a truly malicious one). In this case we assume that both Alice and Bob are “honest, but temptable” – ie, Alice or Bob might be tempted to lie about a coin flip, but neither will go to the trouble of manually finding phrases that appear on both even and odd pages in the same book).