RFC: A zero-knowledge protocol to determine if two people like each other.
Consider the following conundrum:
Person 1: "Do you like me?" Person 2: "I dunno, do you like me?" Person 1: "I dunno, you tell me first." Person 2: "No, you first."
The deadlock occurs because neither person wants to be the only one to answer Yes if the other person answers No. Call the answers A1 and A2. The value they really want to compute is the logical expression "A1 AND A2". That is, whether or not they simultaneously both like each other, without revealing the individual values of A1 and A2.
Zero-knowledge protocols can help with problems like this. Here's a proposal for a solution that can be done in a restaurant/bar and just requires a calculator phone app:
1. Choose 3 integers greater than 1 (2, 3 & 4 are the easiest) and compute their least-common multiple (12). 2. P1 taps an arbitrary random number of at least 7 digits into Phone 1 and then multiplies it by the LCM (12) without revealing these numbers to P2. 3. P1 copies the resulting number into Phone 2 and sets Phone 1 aside face down. 4. If the value of A1 is 'Yes', P1 multiplies the number in Phone 2 by 3. If the value is 'No', multiply by 2. 5. Pass Phone 2 to P2. P2 only knows this intermediate number and not the original random number. 6. If the value of A2 is 'Yes', P2 *divides* the number by 3. If the value is 'No', P2 divides the number by 4. P1 should not ever see the resulting number. 7. Find an impartial, trusted third-party (say a waitress or bartender), individually reveal the numbers on the two phones to him/her and ask if the two numbers are the same. The numbers on the two phones will be equal if and only if A1 and A2 are both 'Yes' (because the random number was multiplied and divided by 3). If either answer was 'No', then the numbers will be different. 8. Now that the answer has been determined, clear the numbers on the phones (only necessary if they were non-equal so that A1/A2 cannot be reverse-engineered by running the protocol backwards).
If done properly, this protocol should be mathematically secure. The main problem with it is the requirement of the trusted third-party in step 7. In many cases there may be no third-parties around, or no third-parties that can be trusted by both participants. One solution could be to run the final numbers through a non-reversible hashing function and compare the hashes with a simultaneous reveal, but that would probably require using integers with hundreds or thousands of digits in order to be completely secure, which makes it impractical for a restaurant/bar environment.
Can anyone think of a way to enhance the protocol to not require the trusted third-party? (and I would say that answers like "use an app for it, or a website" won't be sufficient since the app/website would effectively be the trusted third-party). An ideal solution will still be simple enough to do in a minute or two just using calculator apps.
Madly buying things from Amazon's product suggestions in the hours before they start charging California sales tax is a dangerous thing: Why yes, I would like a waterproof camera case, 100 AA batteries, a 6-pack of boxes of granola bars, some 'organic' compostable trash bags, etc.. Looking at the final bill: :O
I've been beta testing the new version of the Facebook iPhone app for a while now and it's a huge improvement. The app gracefully handles low-bandwidth and spotty connections much better now, which was a godsend in London when there were hordes of people overloading the cell networks everywhere. So glad it's available for everyone now!