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 29 mins ago
kelalaka
5,34821939
asked 46 mins ago
AleksanderRas
1,7281525
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 29 mins ago
kelalaka
5,34821939
asked 46 mins ago
AleksanderRas
1,7281525
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 29 mins ago
kelalaka
5,34821939
asked 46 mins ago
AleksanderRas
1,7281525
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 29 mins ago
kelalaka
5,34821939
asked 46 mins ago
AleksanderRas
1,7281525
edited 29 mins ago
kelalaka
5,34821939
asked 46 mins ago
AleksanderRas
1,7281525
edited 29 mins ago
kelalaka
5,34821939
edited 29 mins ago
kelalaka
5,34821939
edited 29 mins ago
kelalaka
5,34821939
5,34821939
asked 46 mins ago
AleksanderRas
1,7281525
asked 46 mins ago
AleksanderRas
1,7281525
asked 46 mins ago
AleksanderRas
1,7281525
1,7281525
add a comment |
add a comment |
2 Answers
2
active
oldest
votes
$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 32 mins ago
mikeazo
32.7k787144
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 33 mins ago
kelalaka
5,34821939
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
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$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 32 mins ago
mikeazo
32.7k787144
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 32 mins ago
mikeazo
32.7k787144
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 32 mins ago
mikeazo
32.7k787144
$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 32 mins ago
mikeazo
32.7k787144
answered 32 mins ago
mikeazo
32.7k787144
answered 32 mins ago
mikeazo
32.7k787144
answered 32 mins ago
mikeazo
32.7k787144
32.7k787144
add a comment |
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 33 mins ago
kelalaka
5,34821939
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 33 mins ago
kelalaka
5,34821939
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 33 mins ago
kelalaka
5,34821939
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 33 mins ago
kelalaka
5,34821939
edited 20 mins ago
answered 33 mins ago
kelalaka
5,34821939
answered 33 mins ago
kelalaka
5,34821939
answered 33 mins ago
kelalaka
5,34821939
5,34821939
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.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- 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.
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
