Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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$.

share|improve this question
Is the server semi-trusted? $\:$ (in the sense described here) $\;\;\;\;$ – Ricky Demer Jun 5 '14 at 8:52
Do $P_1$ and $P_2$ each have a way to authenticate messages forwarded from the other one of them? $\hspace{.6 in}$ – Ricky Demer Jun 5 '14 at 9:52
@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$. – 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.

share|improve this answer
I want to also avoid brute force attack. And how can $P_1$ get $R_2$? – Jan Leo Jun 5 '14 at 9:34
@JianLiu: $P_1$ would get $R_2$ from $S$ just like $P_2$ would get $PK_1$ in your example. – otus Jun 5 '14 at 9:36

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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