3
$\begingroup$

Bob and Alice each have a bit string they want to keep private. They each want to know what the bitwise AND of their two strings would be without telling the other or anyone else listening to their exchange their actual bit strings... how can they do this? Keep in mind that even once they both hold the AND of their two bit strings, they should still not be able to calculate the other person's string exactly (unless of course one of their strings was all 1s).

I know that I have seen something similar before in some sort of mutual key system/voting system but I couldn't remember where. It has to be something like make a private random key, xor it and use that somehow... but I couldn't work out the details. Any clever encryption design people out there?

Improve this question
$\endgroup$
5
  • $\begingroup$ I've been wondering about similar questions for a long time. We can ignore the question of the eavesdropper, since any solution that allows $A$ and $B$ to exchange the right amount of information can be encrypted more or less unbreakably with the usual methods so that an eavesdropper gets no information at all. The tricky part is making sure that $A$ doesn't find out any of the bits of $B$'s string where the corresponding bit of $A$'s string is 0. $\endgroup$
    – Mark Dominus
    Commented May 16, 2012 at 0:23
  • $\begingroup$ right because of course A will know exactly the values of B's string at any locations where A has a 1 $\endgroup$
    – hackartist
    Commented May 16, 2012 at 0:24
  • $\begingroup$ My own favorite question of this type is whether $A$ and $B$ can learn how many 1 bits there are in the XOR of their strings without learning anything else about the other person's string. (I don't know.) $\endgroup$
    – Mark Dominus
    Commented May 16, 2012 at 0:29
  • 1
    $\begingroup$ I'm going to migrate this question to the cryptography.SE site, where it will be merged with the version of the question you asked there. Please note that posting a question on multiple sites at once is very discouraged. If your question doesn't have much success at cryptography.SE, then you can have a cryptography.SE moderator move it here. $\endgroup$
    – Zev Chonoles
    Commented May 16, 2012 at 2:25
  • $\begingroup$ ok thank you. I wasn't aware about the multiple site policy and I will be more careful in the future. $\endgroup$
    – hackartist
    Commented May 16, 2012 at 2:28

2 Answers 2

Reset to default
4
$\begingroup$

Aaron Roth on theoretical CS was kind enough to answer with the following answer for anyone out there who is interested.

What you want to do is called "Private Set Intersection". You can think of Alice and Bob as each holding sets (the indices for which their strings are "1"), and they want to compute the intersection (the bitwise AND) so that neither of them learns anything about the other's set except what is implied by the intersection itself.

This problem is well studied. See, for example, Freedman, Nissim, and Pinkas: http://www.pinkas.net/PAPERS/FNP04.pdf

Improve this answer
$\endgroup$
1
$\begingroup$

Garbled circuits might be a good way to do this. There are plenty of libraries that will allow you to do garbled circuits easy enough. The two that come to mind are Fairplay/FairplayMP, or a more updated system done by the University of Virginia.

The advantages of these systems over the paper you referenced is that they don't use Public-Key crypto, so they should be faster. If you go with the UVa system, I would expect your performance to be similar to their results on the hamming distance.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.