4
$\begingroup$

The usual solution of socialist millionaire problem allows to authenticate whether TWO parties have the same secret information. Are there any natural solution of the same problem for THREE parties?

$\endgroup$
2
  • $\begingroup$ can you compare MD5(a), MD5(b), and MD5(c)? I mean, i understand that's not cryptography $\endgroup$ Dec 6, 2018 at 1:34
  • 3
    $\begingroup$ @aaaaaa: that's also not zero-knowledge; if you have MD5(a), then you can off-line test various possible values of a until you stumble across the correct one... $\endgroup$
    – poncho
    Dec 6, 2018 at 14:19

1 Answer 1

4
$\begingroup$

A tripartite version of EKE would appear to work. Here's how it works:

  • We select a pairing friendly elliptic curve, with a point $G$ that generates a prime order subgroup.

  • We define an invertible keyed hash function $F_k(H)$ that maps (based on the key) a point in the subgroup to a point in the subgroup (and so that, for two different keys $k_1, k_2$, we don't know the discrete log of $F_{k_1}(H)$ to the base of $F_{k_2}(H)$

So, what Alice does is take her networth $n_A$, and selects a random value $a$; she computes $A = F_{n_A}(aG)$ and publishes it.

Similarly, Bob and Carol also publish their $B = F_{n_B}(bG)$ and $C = F_{n_C}(cG)$.

Alice computes $e( F_{n_A}^{-1}(B), F_{n_A}^{-1}(C) )^a$ and publishes that. Bob and Carol do the same computations and publish their values.

If $n_A = n_B = n_C$, this joint computation is $e( F_{n_A}^{-1}(B), F_{n_A}^{-1}(C) )^a = e(bG, cG)^a = e(G,G)^{abc}$, and hence they will publish the exact same value.

If those three values are not the same, for example, if $n_A \ne n_B$, then $F_{n_A}^{-1}(B) = F_{n_A}^{-1}(F_{n_B}(bG))$ is effectively a random point, and so Alice will generate a value that is distinct from what anyone else generates.


On review, this idea doesn't quite work, if we have $n_A \ne n_B$ and $n_B = n_C$, then B and C will compute the same value. I believe that, from the problem statement, we want to jointly compute the value $n_A = n_B \land n_B = n_C$; we end up leaking more than that...

I'll leave this answer open in case someone can fix it...

$\endgroup$
1
  • $\begingroup$ As I understand you also assumed that $n_A$, $n_B$ and $n_C$ are large numbers. Your scheme will not work for $n_A, n_B, n_C\in\{0,1\}.$ $\endgroup$ Dec 9, 2018 at 3:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.