1
$\begingroup$

Suppose Alice knows a secret vector of $N$ bits, say $A=\langle a_1, a_2, \ldots, a_N\rangle$ and Bob similarly knows $B=\langle b_1, b_2, \ldots, b_N\rangle$. Is there a protocol that allows them to determine the number of bits that their vectors have in common, without revealing any additional information about what the vectors are or what positions agree?

That is, we would like Alice and Bob to be able to determine the size of the set $$X(A,B) = \{i\mid a_i=b_i\}$$ without learning anything else about $A$ and $B$, and without revealing any information to an eavesdropper.

Obviously if $X(A,B) = N$ or $X(A,B)=0$, then Alice now knows Bob's vector and vice versa, and in other cases each gets some incomplete information about the other vector, but that is unavoidable. Perhaps that means that a true zero-knowledge protocol is by definition impossible. But I would like the information leakage to be no greater than this necessary amount.

$\endgroup$
2
$\begingroup$

I think you actually want secure multi-party computation, not zero-knowledge proofs. In secure multi-party computation, Alice has a secret input $a$, Bob has a secret input $b$, and we want to compute $f(a,b)$ so that both Alice and Bob learn $f(a,b)$ but neither one learns anything more about the other's secret. That maps directly to your situation. In your situation, $f$ is the Hamming distance function that counts the number of positions where Alice and Bob's bitvectors agree.

It's a standard theorem that for every poly-time computable $f$, there is a poly-time protocol to compute $f(a,b)$ in a secure multi-party computation sense. There are also toolkits to automatically derive such protocols, given a circuit/description of $f$. For instance, you could look at VIFF or UVA's toolkit.

You'll want to be aware of the differences in threat model between the honest-but-curious threat model (aka semi-honest threat model) vs malicious threat model. The honest-but-curious threat model is a bit of an academic curiousity; for most real applications, I suspect the malicious threat model will be more appropriate, but the protocols do tend to be more expensive.


The following paper might be of interest as well, not for your particular problem, but as an interesting tool for computing monotonic functions, where the inputs are sets:

Lea Kissner and Dawn Song. Privacy-Preserving Set Operations, CMU-CS-05-113.

(I previously thought your problem could be reduced to Cardinality Set Intersection, from Section 5.2 of the following paper, by making Alice's set is $S_1 = \{i : a_i=1\}$, Bob's set is $S_2 = \{i : b_i=1\}$, and computing $|S_1 \cap S_2|$ -- but as you accurately point out, that doesn't work, because you actually want to compute $|S_1 \Delta S_2|$.)


There are a bunch of cryptographers who hang out on Cryptography.SE and who are knowledgeable about this area.

$\endgroup$
  • $\begingroup$ Thanks for this very useful reply. Note that we want them to learn $|S_1\,\triangle\, S_2|$, not $|S_1\cap S_2|$, and the Kissner-Song paper only handles monotonic functions, so does not apply to this case. $\endgroup$ – Mark Dominus Jan 6 '16 at 16:50
  • $\begingroup$ Oh, right! Thanks for correcting my error, @MarkDominus. (Random side note: I remember a Mark Dominus who taught at CTY long ago. If that's you, I remember you as one of the folks who help inspire my love of mathematics back when I was young -- so neat to run across you again!) $\endgroup$ – D.W. Jan 6 '16 at 18:04
  • $\begingroup$ I'm glad you have good memories of me. Thanks! $\endgroup$ – Mark Dominus Jan 6 '16 at 19: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.