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 & \textrm{if } a = b \\ 0 & \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|$?

  • 4
    $\begingroup$ This is exactly the socialist millionaire problem $\endgroup$ – SEJPM Jan 5 '16 at 20:11
  • 1
    $\begingroup$ @Niklas : ​ ​ ​ Even when "|X| is sufficiently large", Just exchanging hashes and comparing is not secure. ​ In that case, even a passive adversary could try hashing lots of guesses at the other party's secret. ​ ​ ​ ​ ​ ​ ​ ​ $\endgroup$ – user991 Jan 5 '16 at 21:47
  • $\begingroup$ Multiparty computation, such as linear secret sharing or garbled circuits, are quite capable of performing any computation while keeping the inputs secure. The questions usually are 1. Is it fast enough? 2. Is it overkill - is there a simpler method? Which of these aspects interest you? $\endgroup$ – Thomas M. DuBuisson Jan 6 '16 at 2:25

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.

  1. For $i=1,\ldots,\ell$, Party 1 chooses a pair of random values of length $n$, denoted $x_i^0,x_i^1$.
  2. 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)
  3. 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)
  4. 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.

|improve this answer|||||
  • $\begingroup$ Um, if the adversary can find more than one element of X then that's not secure against a malicious Party 2, even "if an oblivious transfer protocols that is secure for malicious adversaries is used." ​ (Party 2 can just output 1 even "if the sum of the values it received" doesn't equal A.) ​ ​ ​ ​ $\endgroup$ – user991 Jan 6 '16 at 10:29
  • 1
    $\begingroup$ Party 2 can output whatever it wants if it's corrupted, even in the ideal model. The problem is only if Party 1 also needs to get output (party 1 cannot trust the output it gets from party 2). That's why I said that "if party 1 also needs to get output then more needs to be done". Also, not sure what you mean by "find more than one element of X". $\endgroup$ – Yehuda Lindell Jan 6 '16 at 10:32

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.