10
$\begingroup$

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?

Improve this question
$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – Fractalice
    Jan 3, 2019 at 21:18

3 Answers 3

Reset to default
12
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Why do you care about "leakage" in the first place? $\endgroup$
    – Fractalice
    Jan 3, 2019 at 21:16
  • $\begingroup$ @Hyperflame It is writing style, keep the important ones lastly! In Cryptanalysis every leak is important. $\endgroup$
    – kelalaka
    Jan 3, 2019 at 21:23
  • $\begingroup$ 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). $\endgroup$
    – Fractalice
    Jan 5, 2019 at 9:46
5
$\begingroup$

$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.

Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ 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. $\endgroup$
    – Ella Rose
    Dec 29, 2018 at 16:41
4
$\begingroup$

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$.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.