Suppose there are two parties with binary strings of equal length. What would be the most efficient way to securely calculate the bitwise multiplication of these strings (i.e if one party has 0101 and the other party has 0011 then the product would be 0001)?
My current thinking is that some sort of single-bit multiplicatively homomorphic cryptosystem would work best, but I have been unable to think of any (ElGamal, for example, does not support encryption of 0).
The most natural method for this task would be to use oblivious transfer: on input a bit $x$ for Alice and a bit $y$ for Bob, Alice plays the role of the sender in an oblivious transfer with input $(x_0,x_1) = (0,x)$, and Bob plays the role of the receiver with input $y$, and learns $x_y = x\cdot y$. By repeating this method in parallel for all the bits of their input, Alice and Bob get the bitwise multiplication.
This is probably the most natural and efficient method to perform this task. An alternative is to use ElGamal over a group $\mathbb{G}$ with generator $g$ and public key $h$ for which Alice knows the corresponding secret key.
Alice sends an encryption $(c_0,c_1) = (g^r, h^rg^{x})$ of $g^x$. Bob computes $(c'_0,c'_1) = (c_0g^{r'},c_1^y)h^{r'})$, that is, a rerandomized encryption of $g^{xy}$, and sends it back to Alice, who decrypts and get $g^{xy}$. As $xy \in \{0,1\}$, she easily recover $xy$ from that. Again, by repeating this method in parallel for all the bits of their input, Alice and Bob get the bitwise multiplication.
