8
$\begingroup$

I have been reading a bit about homomorphic encryption, and have been intrigued by its properties.

If I have some cryptosystem that is homomorphic and supports addition, from my understanding, I can do this:

E(A) + E(B) = E(A+B)

...And then I can decrypt E(A+B) without knowing either A or B.

However, if A and B were something like salaries stored somewhere...

E($120k) + E($100k) = E($120k + $100k) = E($220k)

From what I understand, I may not be able to decrypt A or B, but I can calculate A or B given some math. For example:

D(E(A+B)) = $220k (since I can decrypt the result without knowing the individual encryptions)
X = E(-$220k) (since I can encrypt any values myself)
X + E(A) = E(-$220k) + E($120k) = E(-$100k) (this gives me the negative of B... but I can negate that to get B)

Am I understanding this correctly? If so, how is homomorphic encryption secure?

$\endgroup$
  • 1
    $\begingroup$ Well, any cryptosystem is insecure if you can decrypt... The interesting part about homomorphic crypto is that you push the operations away but keep the key $\endgroup$ – SEJPM Mar 2 '17 at 15:57
  • $\begingroup$ Right, so maybe that's what I'm not understanding. I had thought the idea of a homomorphic encryption system is that you can have encrypted data, perform operations on the ciphertext, and then decrypt the result. Is that not correct? $\endgroup$ – NT3RP Mar 2 '17 at 16:03
  • 1
    $\begingroup$ The implication that a party can encrypt values, A and B then another party can compute f and decrypt result = D( f( E(A), E(B) ) ) is supported by Functional Encryption which is still orders of magnitude slower than homomorphic encryption. $\endgroup$ – Thomas M. DuBuisson Mar 2 '17 at 17:46
  • $\begingroup$ How did you magically turn E(-\$100k) into -\$100k? $\endgroup$ – user253751 Mar 3 '17 at 2:46
  • 1
    $\begingroup$ @NT3RP (Answering here instead of the other answer, because it adresses the question itself) You really need to figure out who knows what. If the recipient is the same as the one who does the aggregation, this doesn't work with encryption alone (recipient knows the key and can just decrypt everything he gets individually). And you definately need to change the question to reflect your problem / goal, and remove your proposed (wrong) way to solve it. This is a typical XY problem $\endgroup$ – tylo Mar 3 '17 at 11:35
12
$\begingroup$

The use case for homomorphic encryption is that I encrypt my own data with my public key. I then ship this data to the cloud. The cloud can perform operations on those ciphertexts. But, since the cloud does not have the private key, the cloud cannot decrypt the results of the operations.

Once the operations have been performed, the cloud sends the resulting ciphertext back to me. I can decrypt that to get the answer.

So the key is allowing another untrusted party access to encrypted versions of my data that they can compute on, but can't get the results of the computations. If someone else encrypts their private data with your public key and sends it to you, you will be able to get their private data since you can decrypt.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Oh, ok. So its focussed on individual privacy. That was the part that I was missing. I had thought that anyone could decrypt (which is useful for my case, but clearly homomorphic encryption is not a good fit for what I am investigating). Thanks! $\endgroup$ – NT3RP Mar 2 '17 at 16:22
  • 8
    $\begingroup$ @NT3RP "anyone can decrypt" is a wierd case, and have you have to ask yourself: Why have encryption at all, if everyone is allowed to know the information anyway? $\endgroup$ – tylo Mar 2 '17 at 16:54
  • 1
    $\begingroup$ I was trying to figure out if it is possible for employees to submit salary information (encrypted) to calculate aggregate data (avg salary) without knowing any individual salary and definitely misunderstood the encryption. $\endgroup$ – NT3RP Mar 2 '17 at 17:12
  • 4
    $\begingroup$ This is possible, it's called functional encryption, and in your case this scheme should do the trick. $\endgroup$ – Geoffroy Couteau Mar 2 '17 at 17:20
4
$\begingroup$

A possible definition of homomorphic encryption scheme is that an encryption scheme $E$ is homomorphic with respect to law $+$ over its plaintext set $\mathcal P$, when $E$, and it's matching decryption $D$ (such that $\forall A\in\mathcal P, D(E(A))=A$), come with a publicly computable law $\circledcirc$ over the ciphertext set $\mathcal C$ such that$$\forall A\in\mathcal P,\forall B\in\mathcal P,\;D(E(A)\circledcirc E(B))=A+B$$

In some systems, this definition is restricted to $A$ and $B$ matching some condition (such as $A+B$ not exceeding some thresold over which the homomorphic property might get lost). It might be that $\mathcal P=\mathcal C$ or $\mathcal P\subset\mathcal C$, and then it might be that $\circledcirc$ is the same as $+$.

Homomorphic encryption schemes can in principle be symmetric or asymmetric; and deterministic or randomized; but the most studied ones are asymmetric and randomized. The Pailler cryptosystem is the archetypal example, where $+$ is addition modulo $N$, and $\circledcirc$ is multiplication modulo $N^2$.

For randomized schemes (both symmetric and asymmetric), the common security definition of ciphertext indistinguishability under chosen plaintext needs no adaptation for homomorphic ciphers, and is the most studied.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Is there any symmetric homomorphic encryption that allows two operations? $\endgroup$ – kelalaka Nov 20 '18 at 22:08
3
$\begingroup$

If I have some cryptosystem that is homomorphic and supports addition, from my understanding, I can do this:

E(A) + E(B) = E(A+B)

Yes, anyone that hold the ciphertexts E(A) and E(B) can end up with an encryption of A+B. But please, make sure you understood that the addition on E(A) and E(B) (ciphertext domain) may not be the same that the addition you perform on A and B (plaintext domain). Also, this is not really an equality, since the scheme may be not deterministic, so, the right way to write this is "Dec(E(A) + E(B)) = A + B".

And then I can decrypt E(A+B) without knowing either A or B.

This is the point you are misunderstanding... Only the person possessing the decryption key can decrypt.

You say "I can calculate", "I can decrypt", etc... Maybe, to avoid confusion, you should fix some parties. What is is typically done when homomorphic encryption schemes are presented is to define

  • Data owner: is the party that has the data to be encrypted and (generally) generates the keys $pk$ (encryption key) and $sk$ (decryption key).
  • Third-party: is anyone that receives the encrypted data, the key $pk$, and whose role is to store and compute over the encrypted data. This third-party is, in general, presented as some cloud service.

Thus, the data owner can encrypt, decrypt, and compute homomorphically while the third-party (or, anyone else), can only compute homomorphically, but can't learn the results of those computations.

Further details

As fgrieu said in her/his answer, homomorphic schemes may be symmetric. In this case, $pk = sk$ and, of course, the third-party can't receive $pk$. Therefore, the cloud can't encrypt anymore, which means that all the auxiliary values used in the computation have to be encrypted by the client and send to the cloud as well. For instance, to homomorphically compute the average of $n$ numbers, the client would have to encrypt also the auxiliary value $n$ and send $E(n)$ to the cloud...

Furthermore, deterministic homomorphic encryption can't even be IND-CPA secure. So, this is way randomized homomorphic encryption is studied.

And the last point: the scenario I have described is not the most general one, because it is common to have a third key, called evaluation key, which is used to perform homomorphic operations (so, it has to be submitted with the data to the third-party).

| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ I think the answer would be better if it pointed out that $E(A)+E(B)=E(A+B)$ will hold only for deterministic schemes. The appropriate general definition is $D(E(A)+E(B))=A+B$. $\endgroup$ – fgrieu Mar 13 '17 at 14:42
  • $\begingroup$ Yes, I agree. By the way, feel free to edit my answers in order to improve them. (: $\endgroup$ – Hilder Vitor Lima Pereira Mar 13 '17 at 15:33

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.