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

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.

• What you need is a secure two party computation protocol to compute an AND. Feb 9, 2018 at 14:13
• You can reduce it to socialist millionaires, which is pretty simple. Feb 9, 2018 at 16:19
• I'm surprised to see the dating protocol attributed to Charles Bennett, because it is known as Bert den Boer's five card trick. Den Boer used it as a very nice and playful introduction to his Eurocrypt '89 about MPC protocols for match-making. However, Bennett is acknowledged by Claude Crépeau and Joe Kilian in their Crypto '93 paper "Discreet Solitary Games," which is about card-based MPC protocols for the Secret Santa problem. So Bennett was a bit into these protocols as well, and probably liked Den Boer's five-card trick a lot. Feb 24, 2019 at 22:58
• @BerrySchoenmakers Thank you for the information about Bert den Boer's article. Indeed, I took the information from "Discreet Solitary Games". Mar 2, 2019 at 1:23

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.

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.

• This doesn't seem secure. Even if I vote false. I still know if you voted true or not. Feb 10, 2018 at 5:46
• Claiming you know and showing the math are two different things. Care to show how? This is a typical protocol. I sent $g^{ck_a}$ and you don't have $k$. You can get me to compute $g^{ck_ak_b}$ but then your $c$ must be 'true' and revealing the result of an and operation is the whole point. Feb 10, 2018 at 6:09
• I take it back, I was confusing choice for Ci Feb 10, 2018 at 6:46
• What is H function here? Feb 14, 2018 at 6:22
• Just a hash function. SHA512 if you'd like. Feb 14, 2018 at 6:45