7
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ What you need is a secure two party computation protocol to compute an AND. $\endgroup$ – SEJPM Feb 9 '18 at 14:13
  • $\begingroup$ You can reduce it to socialist millionaires, which is pretty simple. $\endgroup$ – CodesInChaos Feb 9 '18 at 16:19
  • $\begingroup$ @CodesInChaos Does the socialist millionaire problem account for the age of all parties? $\endgroup$ – Q-Club Feb 9 '18 at 19:01
  • 1
    $\begingroup$ @Q-Club I strongly condemn age discrimination. $\endgroup$ – CodesInChaos Feb 9 '18 at 19:16
  • 1
    $\begingroup$ 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. $\endgroup$ – Berry Schoenmakers Feb 24 at 22:58
5
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ This doesn't seem secure. Even if I vote false. I still know if you voted true or not. $\endgroup$ – Meir Maor Feb 10 '18 at 5:46
  • $\begingroup$ 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. $\endgroup$ – Thomas M. DuBuisson Feb 10 '18 at 6:09
  • $\begingroup$ I take it back, I was confusing choice for Ci $\endgroup$ – Meir Maor Feb 10 '18 at 6:46
  • $\begingroup$ What is H function here? $\endgroup$ – Rogach Feb 14 '18 at 6:22
  • $\begingroup$ Just a hash function. SHA512 if you'd like. $\endgroup$ – Thomas M. DuBuisson Feb 14 '18 at 6:45

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.