1
$\begingroup$

Specifically: Alice and Bob want to know if they like each other, but won't admit it if the other person doesn't reciprocate. (They're teenagers, or physicists.) They don't trust anyone else, so want to do it cryptographically.

So, say A->B=1 if Alice likes Bob, 0 otherwise. And let B->A=1 if Bob likes Alice, and zero otherwise. They want to compute "(A->B) AND (B->A)", without revealing their individual rankings. Is there a way that the following sequence could be applied:

  1. Alice encodes her answer (either flipping her bit, or not) and sends it to Bob

  2. Bob applies some function to Alice's preference and his own, and sends the answer back to Alice (but also possibly sends some other information or output from the calculation)

  3. Alice applies some inverse function to determine only whether both A->B and B->A were 1, and announces the outcome, without her being able to know (or determine) B->A (excluding repeated games, or Princess Bride style psychological arguments).

My gut instinct is that this can't be done (the AND operator destroys information, and providing any extra outputs would allow Alice to determine Bob's true feelings) but intuition is hard. I'm thinking of solutions along the lines of poker by phone and the Three-Pass Protocol. It's similar but different to Yao's millionaire problem, which allows two parties to secretly decide if a>=b; that's not sufficient in this case (both because it doesn't distinguish between (1,1) and (0,0), and because it could allow them to quickly deduce their opposite's opinions.

More generally, it could apply to any situation where revealing the truth would be problematic unless the other person was on board.

Appreciate any thoughts!

$\endgroup$
  • $\begingroup$ Charles Bennett has designed a nice one. Look at "Cryptographic Protocols with Everyday Objects". Also, when you search for "Cryptographic dating", don't you get an answer? $\endgroup$ – K.G. Oct 22 '17 at 21:11
  • 1
    $\begingroup$ Is this possible? If Bob likes Alice and submit 1 for B->A, and the result is 0, isn't Alice's preference revealed? $\endgroup$ – Reid Oct 23 '17 at 3:35
  • 1
    $\begingroup$ The goal of MPC in general is not to keep each parties input completely secret - the goal is to ensure no one learns more than if the function was evaluated by a trusted third party. Any information, which can be learned by the output of the function, can not be hidden without changing the function itself. $\endgroup$ – tylo Oct 23 '17 at 13:01
  • $\begingroup$ Regarding Yao's millionare problem: Yes, you could use it: If you consider the input of Alice and Bob to be single bits $a,b$ and consider all combinations, then $a \leq b$ is a function with three $1$s and one $0$. Now you just need to find the matching encoding of Alice likes Bob and vice versa (and you need to invert the result) $\endgroup$ – tylo Oct 23 '17 at 13:07
  • $\begingroup$ You could just use socialist millionaire with a fixed number choice for true and a large random choice for false. Assuming collisions for false don't happen, it'll succeed iff both choose true. $\endgroup$ – CodesInChaos Oct 23 '17 at 13:20
1
$\begingroup$

The answer to your specific scenario is no, it cannot be done. As mentioned in a comment, if Bob knows his preference (B->A) and learns that the result of the calculation is $0$, then Bob now knows Alice's preference, i.e., A->B is 0.

$\endgroup$
  • 1
    $\begingroup$ This is not completely correct. It is possible to create a garbled circuit that will only reveal information about Alice's choice when Bob chooses 1. If Bob chooses 0, then the output of the circuit will always be 0, and Bob won't be able to determine Alice's choice. And if Alice chose 0, then she also wouldn't be able to determine Bob's choice. $\endgroup$ – ndbroadbent Dec 10 '17 at 18:41
1
$\begingroup$

You were on the right track with Yao's Millionaires Problem. Yao's Millionaires Problem is just one specific example, but almost anything can be calculated securely by using by a garbled circuit.

@mikeazo is right that if Bob chooses 1, then he'll always know Alice's choice. However, if Bob chooses 0, then the output of the circuit will always be 0, so Bob won't be able to determine Alice's choice.

The following tables show the information that is revealed to both parties when you use different gates in the circuit:

AND

+-------+---------+----------+--------------+--------------+
|  Bob  |  Alice  |  Output  |  B knows A?  |  A knows B?  |
+-------+---------+----------+--------------+--------------+
|   0   |    0    |    0     |  No          |  No          |
|   0   |    1    |    0     |  No          |  Yes         |
|   1   |    0    |    0     |  Yes         |  No          |
|   1   |    1    |    1     |  Yes         |  Yes         |
+-------+---------+----------+--------------+--------------+

OR

+-------+---------+----------+--------------+--------------+
|  Bob  |  Alice  |  Output  |  B knows A?  |  A knows B?  |
+-------+---------+----------+--------------+--------------+
|   0   |    0    |    0     |  No          |  No          |
|   0   |    1    |    1     |  Yes         |  No          |
|   1   |    0    |    1     |  No          |  Yes         |
|   1   |    1    |    1     |  No          |  No          |
+-------+---------+----------+--------------+--------------+

XOR

+-------+---------+----------+--------------+--------------+
|  Bob  |  Alice  |  Output  |  B knows A?  |  A knows B?  |
+-------+---------+----------+--------------+--------------+
|   0   |    0    |    0     |  Yes         |  Yes         |
|   0   |    1    |    1     |  Yes         |  Yes         |
|   1   |    0    |    1     |  Yes         |  Yes         |
|   1   |    1    |    0     |  Yes         |  Yes         |
+-------+---------+----------+--------------+--------------+

An XOR gate is useless for privacy, since it reveals the other person's choice in all cases. An OR gate is also pretty useless in this scenario, but it could be added to an AND gate circuit to remove the information asymmetry. (All inputs revealed unless both parties choose 0.)

The AND gate example could be used to create a secure P2P dating application, where two people are only matched if they like each other. In the context of a mobile application, there would be some additional possibilities that explain negative outcomes. For example, the other person might not have viewed your profile yet, or they might have uninstalled the app.

If someone likes someone who doesn't like them back, then the other person will have no idea. The real-world benefit is that they can interact with the person they like without any embarrassment. And maybe they can try to win them over :)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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