Cheap and Secure Web Hosting Provider : See Now

# Is there a zero-knowledge protocol for bit vector agreement?

, ,
Problem Detail:

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.

###### Asked By : Mark Dominus

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.

Question Source : http://cs.stackexchange.com/questions/51509

3200 people like this