<p>An <a href="http://en.wikipedia.org/wiki/Oblivious_transfer" rel="nofollow">OT1/2 protocol</a> 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.</p>

CC BY-SA 3.0
2012-05-16T01:00:08.527Z
ok, but Alice has revealed a0 to Bob... so they would have to decide randomly which ones each reveals to the other like this... unless I am missing something I want neither to have any idea of the value of the others' bits unless that party has a 1 in that position.
hackartist
CC BY-SA 3.0
2012-05-16T01:11:01.010Z
What I mean is someone who is listening to the messages in between will see the table Alice sends for a0 and can just look at the value of a0 AND 1 if they wanted to find out that bit. Sure from Bob's point of view if he plays by the rules and only looks at T[b0] and not T[1] all the time this works but that assumes Bob and any eavesdroppers play by those rules.
hackartist
CC BY-SA 3.0
2012-05-16T01:17:08.067Z
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]$.
Charles Fu
CC BY-SA 3.0
2012-05-16T01:26:46.637Z
I know but Bob has to play by the rules still because he could gain advantage by just looking at T[1] all the time... sure this weeds out the possibility of Eve listening in.  But for the bits Alice sends a table for, Bob has advantage and for the bits Bob sends a table for Alice has the advantage.  It needs to be that neither one can have any idea for any bit that is 0 in their string and this would allow them to cheat if they wanted to on some of their 0 bits.
hackartist
CC BY-SA 3.0
2012-05-16T00:50:08.757Z
2012-05-16T00:50:08.757Z
Charles Fu
<p>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. </p>

<p>This problem is well studied. See, for example, Freedman, Nissim, and Pinkas: <a href="http://www.pinkas.net/PAPERS/FNP04.pdf">http://www.pinkas.net/PAPERS/FNP04.pdf</a></p>

CC BY-SA 3.0
2012-05-16T01:33:02.713Z
This sounds like exactly what I am looking for... I have to read the paper before I know if this is exactly right but thank you
hackartist
CC BY-SA 3.0
2012-05-16T01:29:03.677Z
2012-05-16T01:29:03.677Z
Aaron Roth
<blockquote>
  <p>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).</p>
</blockquote>

<p>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?</p>

<reference-request><cr.crypto-security><homomorphic-encryption>
Algorithm Design for only Mutual Information Sharing
hackartist
# Algorithm Design for only Mutual Information Sharing

(Asked by: username_0 on 2012-05-16)

> 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?

**Tags:** reference-request, cr.crypto-security, homomorphic-encryption


---

## 2 answers

### Answer by username_2 on 2012-05-16. Score: 7 | Accepted answer

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>

> **Comments:**
> **username_0**: This sounds like exactly what I am looking for... I have to read the paper before I know if this is exactly right but thank you  

---

### Answer by username_1 on 2012-05-16. Score: 1

An [OT1/2 protocol](http://en.wikipedia.org/wiki/Oblivious_transfer) 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.

> **Comments:**
> **username_0**: ok, but Alice has revealed a0 to Bob... so they would have to decide randomly which ones each reveals to the other like this... unless I am missing something I want neither to have any idea of the value of the others' bits unless that party has a 1 in that position.  
> **username_0**: What I mean is someone who is listening to the messages in between will see the table Alice sends for a0 and can just look at the value of a0 AND 1 if they wanted to find out that bit. Sure from Bob's point of view if he plays by the rules and only looks at T[b0] and not T[1] all the time this works but that assumes Bob and any eavesdroppers play by those rules.  
> **username_1**: 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]$.  
> **username_0**: I know but Bob has to play by the rules still because he could gain advantage by just looking at T[1] all the time... sure this weeds out the possibility of Eve listening in.  But for the bits Alice sends a table for, Bob has advantage and for the bits Bob sends a table for Alice has the advantage.  It needs to be that neither one can have any idea for any bit that is 0 in their string and this would allow them to cheat if they wanted to on some of their 0 bits.  

---

