# Homomorphic encryption - Why does addition not imply multiplication?

As far as I know:

There are some partially homomorphic encryption (PHE) systems that support either addition or multiplication.

A fully homomorphic encryption (FHE) system can do addition as well as multiplication and thus supports arbitrary computation on ciphertexts.

My question is (disregarding computational efficiency):

Why does a PHE-system that allows addition on ciphertext not directly imply that it also can do multiplication, since

$$a \times b$$

is the same as

$$\underbrace{a + a + \cdots + a}_{b\text{ times}}?$$

Are there some computations that are only possible with a direct multiplication instead of a continuous addition?

• What you do is multiplication by a constant value $b$. Indeed you can do it, and also you can use double-and-add to perform multiplication by $b$ in $\log{b}$ additions. However, you can not multiply by encrypted value $b$ publicly (without knowing the secret key), and that is what FHE is expected to provide. – Hyperflame Jan 3 '19 at 21:18

There are at least two problems;

1. The $$b$$-times addition leaks the $$b$$. A semi-honest observer can see that you add the $$a$$ by $$b$$ times. However, in FHE, the $$b$$ is also encrypted with semantically secure that leaks no information. The only information available to the observer is the circuit.

2. In FHE, the $$b$$ is coming (or may come) from another result, which means that $$b$$ is also encrypted. In additive PHE, you cannot multiply by $$b$$ without decryption.

You can look at some example of FHE circuits from this answer to see that some of them are not even possible with additive PHE.

• Why do you care about "leakage" in the first place? – Hyperflame Jan 3 '19 at 21:16
• @Hyperflame It is writing style, keep the important ones lastly! In Cryptanalysis every leak is important. – kelalaka Jan 3 '19 at 21:23
• I think the FHE notion does not care about leakage of computations. Having a gate 'multiply by 10' or 'multiply by 123' in homomorphic encryption setting is not a problem at all (and as the topic suggests, PHE implies it). – Hyperflame Jan 5 '19 at 9:46

$$b$$ is encrypted and therefore unknown to the machine doing the multiplication. So, you cannot just "add $$b$$ times".

One thing you may be tempted to think is just subtract 1 from the encrypted $$b$$ and stop when $$b$$ is zero. For a semantically secure homomorphic cipher, this is impossible. If your homomorphic cipher is not semantically secure, it can easily be broken.

• Also: for any ciphertext that is larger than 128 bits in size, it would take an obscenely long amount of time to do the subtract-by-1-until-0 method, even if it worked. – Ella Rose Dec 29 '18 at 16:41

The other answers are correct, but I wanted to note that:

If you can add ciphertexts together, then you can multiply them by a plaintext value, because of the reason you described in your question.

Similarly, if you can multiply ciphertexts together, then you can exponentiate them by a plaintext value as well.

So if you distribute two ciphertexts $$c_0, c_1$$ and your algorithm supports only the ability to add ciphertexts together, then it is not possible to meaningfully evaluate $$c_0 c_1$$, but it is possible for anyone to meaningfully evaluate $$c_0p_0$$.