Algorithm Design for only Mutual Information Sharing
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 &quot;Private Set Intersection&quot;. You can think of Alice and Bob as each holding sets (the indices for which their strings are &quot;1&quot;), 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