Zero knowledge proof of shared secret Alice holds a secret $a \in X$. Bob holds a secret $b \in X$. Is there a protocol that lets them compute

$f(a, b) = \begin{cases}
1 &amp; \textrm{if } a = b \\
0 &amp; \textrm{else}
\end{cases}$

If $a = b$ the protocol must always succeed.

If $a \neq b$ they should not learn anything else about each others secret.

Of course an adversary could always just pick a random value and succeed with probability $\frac{1}{|X|}$. So an error rate $\frac{1}{|X|} + \epsilon$ is accaptable.



If $|X|$ is sufficiently large, then they could just exchange hashes and compare.

Is there also also a protocol for very small $|X|$?
There are many ways of doing this. A very nice read (but with informal presentation) is this paper by Fagin, Naor and Winkler on Comparing Information without Leaking It. A very fast protocol exists which requires a single oblivious transfer for every bit. Let $n$ be a security parameter; say $n=128$, and let $\ell$ be the bit-length of the inputs.


For $i=1,\ldots,\ell$, Party 1 chooses a pair of random values of length $n$, denoted $x_i^0,x_i^1$.
For $i=1,\ldots,\ell$, the parties run an oblivious transfer where Party 1 inputs $x_i^0,x_i^1$ and party 2 inputs $b_i$ (the $i$th bit of its input)
Party 1 sends Party 2 the value $A=\sum_{i=1}^\ell x_i^{a_i}$ (where $a_i$ is the $i$th bit of its input)
Party 2 outputs 1 if and only if the sum of the values it received equals $A$.


The nice think about this protocol is that it is secure even for malicious adversaries if an oblivious transfer protocols that is secure for malicious adversaries is used.

Note that if party 1 also needs to get output then more needs to be done.