The scenario is like this:

$P_1$ has $m_1$, $P_2$ has $m_2$, they want to compare whether $m_1=m_2$ via the server $S$. After the protocol, only $S$ knows the result, and there is no interaction between $P_1$ and $P_2$.

An example solution:

  1. $P_1$ encrypts $m_1$ with his public key $PK_1$; Then he sends $E(PK_1,m_1)$ and $PK_1$ to $S$; ($E$ is additively homomorphic)
  2. $S$ forwards $E(PK_1, m_1)$ and $PK_1$ to $P_2$;
  3. $P_2$ encrypts $m_2$ with $PK_1$, and calculates $E(PK_1,m_0) = E(PK_1, m_2-m_1) = E(PK_1,m_2) - E(PK_1,m_1)$; Then he sends $E(PK_1, m_0)$ to $S$;
  4. $S$ does an oblivious decryption with $P_1$ to get $m_0$, and checks whether $m_0=0$

But in step 2, a malicious $S$ can sends $E(PK_s, 0)$ and $PK_s$ to $P2$ ($S$ knows the decryption key $SK_s$). Then $S$ will get $E(PK_s, m_2)$ from $P_2$, so that he will get $m_2$.

  • $\begingroup$ Is the server semi-trusted? $\:$ (in the sense described here) $\;\;\;\;$ $\endgroup$
    – user991
    Jun 5, 2014 at 8:52
  • $\begingroup$ Do $P_1$ and $P_2$ each have a way to authenticate messages forwarded from the other one of them? $\hspace{.6 in}$ $\endgroup$
    – user991
    Jun 5, 2014 at 9:52
  • $\begingroup$ @RickyDemer The server can be malicious instead of semi-trusted. $P_1$ and $P_2$ doesn't have the identity of each other. And the server can also collue with either $P_1$ or $P_2$. $\endgroup$
    – Jan Leo
    Jun 5, 2014 at 10:01

1 Answer 1


How about hashes?

  1. $P_i$ choose random numbers $R_i$ that they exchange through $S$.
  2. They calculate $H_i = H(R_1|R_2|m_i)$ that they give $S$.
  3. If $H_1 = H_2$, then $S$ can be reasonably sure $m_1=m_2$.

Assuming $H$ is a strong cryptographic hash function and $R_i$ are long enough to avoid collisions (e.g. 256 bits), the worst the server can do is a brute force attack to find $m_i$. Giving an incorrect $R_i$ will only cause the equality check to fail.

  • $\begingroup$ I want to also avoid brute force attack. And how can $P_1$ get $R_2$? $\endgroup$
    – Jan Leo
    Jun 5, 2014 at 9:34
  • $\begingroup$ @JianLiu: $P_1$ would get $R_2$ from $S$ just like $P_2$ would get $PK_1$ in your example. $\endgroup$
    – otus
    Jun 5, 2014 at 9:36

Your Answer

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

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