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}_{btext{ times}}?$$
Are there some computations that are only possible with a direct multiplication instead of a continuous addition?
homomorphic-encryption
edited Dec 29 '18 at 14:15
kelalaka
6,16522142
asked Dec 29 '18 at 13:57
AleksanderRasAleksanderRas
1,9251628
add a comment |
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}_{btext{ times}}?$$
Are there some computations that are only possible with a direct multiplication instead of a continuous addition?
homomorphic-encryption
edited Dec 29 '18 at 14:15
kelalaka
6,16522142
asked Dec 29 '18 at 13:57
AleksanderRasAleksanderRas
1,9251628
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 at 21:18
add a comment |
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}_{btext{ times}}?$$
Are there some computations that are only possible with a direct multiplication instead of a continuous addition?
homomorphic-encryption
edited Dec 29 '18 at 14:15
kelalaka
6,16522142
asked Dec 29 '18 at 13:57
AleksanderRasAleksanderRas
1,9251628
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}_{btext{ times}}?$$
Are there some computations that are only possible with a direct multiplication instead of a continuous addition?
homomorphic-encryption
homomorphic-encryption
edited Dec 29 '18 at 14:15
kelalaka
6,16522142
asked Dec 29 '18 at 13:57
AleksanderRasAleksanderRas
1,9251628
edited Dec 29 '18 at 14:15
kelalaka
6,16522142
asked Dec 29 '18 at 13:57
AleksanderRasAleksanderRas
1,9251628
edited Dec 29 '18 at 14:15
kelalaka
6,16522142
edited Dec 29 '18 at 14:15
kelalaka
6,16522142
edited Dec 29 '18 at 14:15
kelalaka
6,16522142
6,16522142
asked Dec 29 '18 at 13:57
AleksanderRasAleksanderRas
1,9251628
asked Dec 29 '18 at 13:57
AleksanderRasAleksanderRas
1,9251628
asked Dec 29 '18 at 13:57
AleksanderRasAleksanderRas
1,9251628
1,9251628
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 at 21:18
add a comment |
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 at 21:18
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 at 21:18
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 at 21:18
add a comment |
3 Answers
3
active
oldest
votes
There are at least two problems;
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.
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.
answered Dec 29 '18 at 14:11
kelalakakelalaka
6,16522142
Why do you care about "leakage" in the first place?
– Hyperflame
Jan 3 at 21:16
@Hyperflame It is writing style, keep the important ones lastly! In Cryptanalysis every leak is important.
– kelalaka
Jan 3 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 at 9:46
add a comment |
$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.
answered Dec 29 '18 at 14:11
mikeazomikeazo
32.8k788145
2
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
add a comment |
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$.
answered Dec 29 '18 at 16:40
Ella Rose♦Ella Rose
15.4k44279
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "281"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcrypto.stackexchange.com%2fquestions%2f66151%2fhomomorphic-encryption-why-does-addition-not-imply-multiplication%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
There are at least two problems;
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.
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.
answered Dec 29 '18 at 14:11
kelalakakelalaka
6,16522142
Why do you care about "leakage" in the first place?
– Hyperflame
Jan 3 at 21:16
@Hyperflame It is writing style, keep the important ones lastly! In Cryptanalysis every leak is important.
– kelalaka
Jan 3 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 at 9:46
add a comment |
There are at least two problems;
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.
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.
answered Dec 29 '18 at 14:11
kelalakakelalaka
6,16522142
Why do you care about "leakage" in the first place?
– Hyperflame
Jan 3 at 21:16
@Hyperflame It is writing style, keep the important ones lastly! In Cryptanalysis every leak is important.
– kelalaka
Jan 3 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 at 9:46
add a comment |
There are at least two problems;
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.
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.
answered Dec 29 '18 at 14:11
kelalakakelalaka
6,16522142
There are at least two problems;
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.
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.
answered Dec 29 '18 at 14:11
kelalakakelalaka
6,16522142
edited Dec 29 '18 at 14:23
answered Dec 29 '18 at 14:11
kelalakakelalaka
6,16522142
answered Dec 29 '18 at 14:11
kelalakakelalaka
6,16522142
answered Dec 29 '18 at 14:11
kelalakakelalaka
6,16522142
6,16522142
Why do you care about "leakage" in the first place?
– Hyperflame
Jan 3 at 21:16
@Hyperflame It is writing style, keep the important ones lastly! In Cryptanalysis every leak is important.
– kelalaka
Jan 3 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 at 9:46
add a comment |
Why do you care about "leakage" in the first place?
– Hyperflame
Jan 3 at 21:16
@Hyperflame It is writing style, keep the important ones lastly! In Cryptanalysis every leak is important.
– kelalaka
Jan 3 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 at 9:46
Why do you care about "leakage" in the first place?
– Hyperflame
Jan 3 at 21:16
Why do you care about "leakage" in the first place?
– Hyperflame
Jan 3 at 21:16
@Hyperflame It is writing style, keep the important ones lastly! In Cryptanalysis every leak is important.
– kelalaka
Jan 3 at 21:23
@Hyperflame It is writing style, keep the important ones lastly! In Cryptanalysis every leak is important.
– kelalaka
Jan 3 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 at 9:46
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 at 9:46
add a comment |
$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.
answered Dec 29 '18 at 14:11
mikeazomikeazo
32.8k788145
2
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
add a comment |
$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.
answered Dec 29 '18 at 14:11
mikeazomikeazo
32.8k788145
2
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
add a comment |
$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.
answered Dec 29 '18 at 14:11
mikeazomikeazo
32.8k788145
$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.
answered Dec 29 '18 at 14:11
mikeazomikeazo
32.8k788145
answered Dec 29 '18 at 14:11
mikeazomikeazo
32.8k788145
answered Dec 29 '18 at 14:11
mikeazomikeazo
32.8k788145
answered Dec 29 '18 at 14:11
mikeazomikeazo
32.8k788145
32.8k788145
2
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
add a comment |
2
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
2
2
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
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
add a comment |
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$.
answered Dec 29 '18 at 16:40
Ella Rose♦Ella Rose
15.4k44279
add a comment |
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$.
answered Dec 29 '18 at 16:40
Ella Rose♦Ella Rose
15.4k44279
add a comment |
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$.
answered Dec 29 '18 at 16:40
Ella Rose♦Ella Rose
15.4k44279
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$.
answered Dec 29 '18 at 16:40
Ella Rose♦Ella Rose
15.4k44279
answered Dec 29 '18 at 16:40
Ella Rose♦Ella Rose
15.4k44279
answered Dec 29 '18 at 16:40
Ella Rose♦Ella Rose
15.4k44279
answered Dec 29 '18 at 16:40
Ella Rose♦Ella Rose
15.4k44279
15.4k44279
add a comment |
add a comment |
Thanks for contributing an answer to Cryptography Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcrypto.stackexchange.com%2fquestions%2f66151%2fhomomorphic-encryption-why-does-addition-not-imply-multiplication%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
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 at 21:18