Homomorphic encryption for multiplication (AND) on bits only?

Question

I am reading the Wikipedia article https://en.wikipedia.org/wiki/Homomorphic_encryption and it lists unpadded RSA, ElGamal, Goldwasser-Micali, Benaloh, Paillier as possible partially homomorphic encryption (PHE) schemes.

Of these, only Goldwasser-Micali seems to be for bits and it is XOR-homomorphic. The other encryption schemes seem to be for group elements, and it seems like if you say you only encrypt 0 or 1 then the operations won't hold (because, e.g., $1+1 =2$ now).

Assuming that I only want to encrypt 0 or 1, is there a partial HE that can do ANDs (aka multiplication)? Or, is it only possible to do multiplication on a larger group? I understand that many fully homomorphic encryption schemes do just work on bits, but then there's issues with noise growing/boot strapping. (Whereas, for example, multiplying two ElGamal ciphertexts together is a "clean" operation).

Is there a simple PHE that works on bits only and allows you to do an unbounded number of ANDs? Or is FHE required?

To try to give some context: what if there are $n$ people who are voting yes/no with 1 or 0 and you want to find out if the vote is unanimous for yes? I guess here there's some issue with having to do some sort of threshold decryption or multi-key encryption as well, and from my understanding from 2016/196 or 2017/956that makes the ciphertext be of size $n$ also, which seems like a big hassle for a simple operation. That's why I thought perhaps a PHE would be enough, and perhaps give you the chance of having smaller ciphertexts.

Answer 1

Assuming that I only want to encrypt 0 or 1, is there a partial HE that can do ANDs (aka multiplication)?

Yes.

In fact, there is a generic way of converting any additively homomorphic encryption scheme with large plaintext space into a PHE for AND with plaintexts in $\{0,1\}$.

Here is the idea: let $(\mathsf{KeyGen}, \mathsf{Enc},\mathsf{Dec})$ be an additively homomorphic encryption scheme; for simplicity, suppose that the plaintext space is $\mathbb{Z}_p$ for some large prime $p$. Define $(\mathsf{KeyGen}^*, \mathsf{Enc}^*,\mathsf{Dec}^*)$ as follows:

$\mathsf{KeyGen}^*$: same as $\mathsf{KeyGen}$.

$\mathsf{Enc}^*(m)$: if $m=0$, sample a uniformly random value $R \gets \mathbb{Z}_p$. If $m = 1$, set $R \gets 0$. Output an encryption $\mathsf{Enc}(R)$ of $R$ with the original scheme.

$\mathsf{Dec}^*(C)$: decrypt $C$ with $\mathsf{Dec}$ to get $R$. If $R = 0$, output $1$; else, output $0$.

Claim: $(\mathsf{KeyGen}^*, \mathsf{Enc}^*,\mathsf{Dec}^*)$ is a multiplicatively homomorphic encryption scheme over $\{0,1\}$, with negligible correctness error; the procedure for homomorphic multiplication is just the procedure for homomorphic addition of the original scheme.

This is easy to check: a sum of any number of encryptions of zero is still an encryption of zero. However, if a single ciphertext encrypts a nonzero value, the result becomes nonzero. In terms of the scheme $\mathsf{Enc}^*$, this translates to the fact that the AND of many 1's is still 1, but if a single bit is zero, the result is zero.

Since the addition is done mod $p$, there is a tiny chance that a sum of nonzero values will give a zero, hence the homomorphic algorithm has imperfect correctness; however, if $p$ is large enough, this happens only with negligible probability.

Two additional comments:

• The above transformation gives an additional useful property: if the original encryption scheme is rerandomizable, then so is the new encryption scheme. Said otherwise, you canc guarantee that the homomorphic AND of $n$ ciphertexts only leaks the AND of the plaintexts, and nothing about the individual values of the plaintext (a generic PHE does not necessarily satisfy that, but this is often needed in applications - for example, this is needed in the example application of unanimous voting in your question)
• The additively homomorphic variant of ElGamal (a ciphertext is of the form $(g^r, h^r\cdot g^m)$) can be used here: it does not enjoy efficient decryption, but it is easy to check that it is not important in this transformation, since we only need to be able to check whether a ciphertext decrypts to 0 or not, and this can always be checked given $g^m$ (which is what you get when decrypting ElGamal).