# Algorithm Design for only Mutual Information Sharing

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 asked this on Stack Overflow and got yelled at to move it here. Not really sure how to tag it either if anyone knows what it would fit under better please feel free to edit. 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?

An OT1/2 protocol can be used here. For example, let Alice's first bit be $a_0$. She can prepare a table $T = \{a_0\text{ AND }0, a_0\text{ AND }1\}$. Bob, holding the bit $b_0$, can ask for $T[b_0]$ to get the value $(a_0\text{ AND }b_0)$ without revealing $b_0$ to Alice. Then Bob can simply tell Alice the result.
• Well to prevent eavesdropping you can always wrap this with a PKS right? Alice should let $T = \{E_b(a_0\text{ AND }0), E_b(a_0\text{ AND }1)\}$ where $E_b$ is the encryption function using Bob's public key. Bob then can first obtain the value then decrypt it to see the real value of $T[b_0]$. Commented May 16, 2012 at 1:17