# server aid secure equality test

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

-
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

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