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$

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.