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 '14 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 '14 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 '14 at 10:01

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 '14 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 '14 at 9:36

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.