Is there a cryptographic solution for this “dating protocol”?

Question

The article Cryptographic Protocols with Everyday Objects by James Heather, Steve Schneider, and Vanessa Teague describes the following dating protocol (due to Bert den Boer):

Alice and Bob wish to determine whether they both want to go on a date; but they want to avoid the embarrassing situation in which one of them does not want to go on a date, but knows that the other would have liked to do so. Essentially they need a two-player veto protocol: they want to compute whether at least one has vetoed the date, without revealing any further information.

Q: Bennett’s solution uses playing cards. Does this problem admits cryptographic solution?

Of course it can be reduced to Yao's Millionaires' Problem. But probably this problem has a simpler solution.

Answer 1

You can use a protocol solving the Socialist millionaires problem for this. Socialist millionaires compares two integers for equality. There are relatively simple implementations of this protocol, similar to Diffie-Hellman, which are used to implement PAKE (password authenticated key-exchange).

Agree a fixed integer to denote true. A party chooses that value if they want to signal true and a random other value (say 256-bits) if they want to signal false. This clearly works for the case where at least one party chooses true. If both parties choose false it will almost certainly produce a not-equal result from SM, since the chance of two random values being equal is negligible.

Thus you can securely implement the AND function using a Socialist millionaires protocol.

Answer 2

First agree on a large prime $p$, a generator $g$, and a random value module $p$ to represent $true$. Each party has their choice of date or not as $C_{a,b} \in \{0,1\}$. Then each party $i$ computes:

$ \\ false \leftarrow random() \\ k_{private} \leftarrow random() \\ choice_i \leftarrow H(true \times C_i + false \times (1 - C_i)) \\ e \leftarrow g^{choice_i \times k_{private}} \\ \text{Send } e_i \text{ to the other player, receiving } e_{\bar{i}} \\ \text{Publish } e_{\bar{i}}^{k_{private}} $

This is just a typical private set intersection specialized to a single element.