# Homomorphic encryption for multiplication (AND) on bits only?

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.

• It seems like you are trying to avoid FHE in your project. What are you trying to do? What you listed are called partial FHE. Commented Jan 26, 2021 at 14:34
• partial FHE is not a thing, since "partial fully" would be weird ^^ the standard terms are fully/partially/somewhat/leveled HE Commented Jan 27, 2021 at 21:19

## 1 Answer

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).
• The interested reader may want to know that for this you don't actually need an additive homomorphism here but only a group homomorphism which also allows to use eg 1 with multiplication. Commented Jan 29, 2021 at 8:27
• Yep, that's perfectly right - it is actually a much cleaner way of pointing out that this can be instantiated under ElGamal without going through "there is an additive variant of ElGamal which has imperfect decryption but this imperfect decryption is not an issue here." Commented Jan 29, 2021 at 8:50
• I'm slightly confused by the $R$ and $r$ for ElGamal because if you set $r=0$ and the first element in the tuple is $g^0 = 1$ then it's obvious what you're encrypting, no? Unless $R$ and $r$ aren't meant to be equal? Commented Feb 4, 2021 at 19:34
• R and r are unrelated: r is the randomness of the encryption scheme, but R is a (randomized) encoding of the message (R(m) = 0 when m is 1 and random otherwise. For ElGamal, formally that would be: $\mathsf{Enc}^*(m, (r,r')) = (g^r, h^r*g^{R(m,r')})$, where r' is the randomness used by the encoding, namely, R(m,r') is 0 if m is 1 and r' if m is zero. Does that clarify? Commented Feb 4, 2021 at 20:04