2
$\begingroup$

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)?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

For your first question, the second paper you linked (https://eprint.iacr.org/2019/599.pdf) is a multiparty protocol so the EQZ protocol in it works for three parties.

To the best of my knowledge, the second question might not have a satisfying answer. If you want to save communication rounds, then I suggest looking at multiparty garbled circuit protocols which are constant round (https://eprint.iacr.org/2017/189.pdf or https://eprint.iacr.org/2017/189.pdf). Doing secure comparison you just need to garble a comparison circuit. If you don't need dishonest majority, the best three party protocols are based on ABY 3.0 (using replicated secret sharing). I don't think it will help with reducing the communication complexity specifically, but it might help with other parts of the function that you are trying to compute. Specifically, with ABY 3.0, you can do a dot-product with constant communication in the online phase, i.e., the communication doesn't depend on the length of the vector anymore.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Replicated secret sharing is actually a good choice, especially for multiplication. BTW, is the protocol of the equality test between two secret-shared values the same as it between one secret-shared value and one public value? Because I rarely see the latter settings. $\endgroup$
    – Dylan
    Jun 17, 2022 at 2:38
  • $\begingroup$ 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]$. $\endgroup$
    – lamba
    Jun 17, 2022 at 9:01

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.