Extending the Socialist millionaire problem to three parties

Question

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?

Answer 1

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...