9
$\begingroup$

Suppose Alice and Bob each have bits a and b, respectively. How can Alice and Bob compute the function a and b, without revealing their bits to each other?

EDIT: A paper called Solving the Dating Problem with the SENPAI Protocol came out recently.

$\endgroup$
5
$\begingroup$

They could use 1 out of 2 oblivious transfer. Alice offers the messages $0$ and $a$ and Bob uses $b$ as his choice bit (I.e., choosing the first message if $b = 0$ and the second if $b = 1$.). It should be easy to see that Bob now receives $a \land b$ (if in doubt write down the truth-table). Now Bob can send the result to Alice (or they can do the protocol in reverse).

Of course this assumes passive (semi-honest) adversaries. Also, note that if one party has input 1, then $a \land b$ always reveals the other party's input (this is regardless of the protocol).

Btw, this is known as the "Dating Problem", because it can phrased as follows: Alice and Bob does not want to openly tell each other whether or not they want to go on a date with the other. They fear embarrassment if the other party rejects them. Using the above protocol they can learn if both want to go on a date but will not learn if only the other party wants to go on the date. Essentially what Tinder solves for thousands of people every day! (Although they do it in a totally non-cryptographic way AFAIK)

$\endgroup$
  • 2
    $\begingroup$ Is there a way to ensure both parties learn the output, without letting one party prematurely terminate the protocol to prevent the other party from doing so? $\endgroup$ – user76284 Mar 25 '15 at 18:21
  • $\begingroup$ @Carlos that property is called fairness. It is notoriously hard to achieve in the two party setting. I am not sure but I believe it is impossible for this function (although could be possible for other functions than conjunction) $\endgroup$ – Guut Boy Aug 26 '16 at 18:10
  • $\begingroup$ This only assumes passive Bob; it will handle malicious Alice if the OT protocol does. ​ ​ ​ Also, conjunction is one of the functions for which fairness is achievable: ​ If the adversary aborts then the honest party outputs its own input. If the original simulator would send 0 to the functionality, then the modified simulator simulates a 0 response from the functionality, and if the adversary aborts then the modified simulator sends 1 to the functionality else it sends 0 to the functionality. ​ ​ ​ ​ ​ ​ ​ $\endgroup$ – user991 Aug 28 '16 at 4:20

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.