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?
-
$\begingroup$ can you compare MD5(a), MD5(b), and MD5(c)? I mean, i understand that's not cryptography $\endgroup$– aaaaa says reinstate MonicaDec 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$– ponchoDec 6, 2018 at 14:19
1 Answer
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...
-
$\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