# Is there three-party protocol for Secure Equality Test (a.k.a Socialist Millionaire problem)?

Secure Equality Test is an important building block in Secure Multi-Party Computation (MPC) with respect to Secure Comparison, also known as Socialist millionaire problem.

A similar question was posted several years ago (Extending the Socialist millionaire problem to three parties), but it seems to be considered from Zero-Knowledge. In this post, I want to discuss this problem from the perspective of Two/Three-Party (2/3PC) Computation.

Definition with respect to 2PC: Given two secret-shared (e.g., additive secret sharing) values $$x$$ and $$y$$, held by Alice (i.e., $$[x]_1$$ and $$[y]_1$$) and Bob (i.e., $$[x]_2$$ and $$[y]_2$$), respectively. After running the secure computation between Alice and Bob, Alice and Bob learn $$[z]_1$$ and $$[z]_2$$, respectively, where $$z=1$$ if $$x=y$$, otherwise $$z=0$$. Note that $$x$$ and $$y$$ are secret-shared under arithmetic secret sharing while the result bit $$z$$ is a single bit under boolean sharing.

Recent protocols such as CryptFlow2 and New Primitives for Actively-Secure MPC over Rings with Applications to Private Machine Learning provide secure equality protocols based on 2PC.

So, my questions are:

1. Is there a protocol for Three Party?

2. CryptFlow2 is probably the most efficient protocol proposed recently. But there are still too many communications (e.g., the communication round is $$logl$$ where $$l$$ is the bit length of the integer, shown in Table 1 in the CryptFlow2 paper).

For me, I'm more concerned with communication overhead. That is, I can accept a bit more computational overhead, but as little communication as possible. So is there any communication-efficient protocol (no matter 2PC or 3PC)?

• I think so, because the EQZ protocol in my answer basically checks if a secret shared value is 0. If you want to compare the equality between a secret shared value $[a]$ and a plaintext value $b$, then you basically do EQZ($[a] - b$) and then you'll get either a $[0]$ or $[1]$. Jun 17, 2022 at 9:01