Is there a way of maintaining malleability in a homomorphic encryption system while making it infeasible to...
- Is there a way of maintaining malleability in a homomorphic encryption system while making it infeasible to perform chosen ciphertext attacks?
I have been reading about homomorphic encryption and malleable cryptosystems lately and have found it fascinating. I still have a lot of reading to do, however, I came across a statement in my reading that suggested malleability is inherently counter to security against chosen ciphertext attacks.
While I read up more about this relationship, I am curious to learn if there a way to maintain malleability while making a chosen ciphertext attack computationally infeasible? Why or why not?
homomorphic-encryption provable-security chosen-ciphertext-attack malleability
edited Nov 26 at 20:55
kelalaka
5,28821939
asked Nov 26 at 20:38
hdu
284
add a comment |
- Is there a way of maintaining malleability in a homomorphic encryption system while making it infeasible to perform chosen ciphertext attacks?
I have been reading about homomorphic encryption and malleable cryptosystems lately and have found it fascinating. I still have a lot of reading to do, however, I came across a statement in my reading that suggested malleability is inherently counter to security against chosen ciphertext attacks.
While I read up more about this relationship, I am curious to learn if there a way to maintain malleability while making a chosen ciphertext attack computationally infeasible? Why or why not?
homomorphic-encryption provable-security chosen-ciphertext-attack malleability
edited Nov 26 at 20:55
kelalaka
5,28821939
asked Nov 26 at 20:38
hdu
284
add a comment |
- Is there a way of maintaining malleability in a homomorphic encryption system while making it infeasible to perform chosen ciphertext attacks?
I have been reading about homomorphic encryption and malleable cryptosystems lately and have found it fascinating. I still have a lot of reading to do, however, I came across a statement in my reading that suggested malleability is inherently counter to security against chosen ciphertext attacks.
While I read up more about this relationship, I am curious to learn if there a way to maintain malleability while making a chosen ciphertext attack computationally infeasible? Why or why not?
homomorphic-encryption provable-security chosen-ciphertext-attack malleability
edited Nov 26 at 20:55
kelalaka
5,28821939
asked Nov 26 at 20:38
hdu
284
- Is there a way of maintaining malleability in a homomorphic encryption system while making it infeasible to perform chosen ciphertext attacks?
I have been reading about homomorphic encryption and malleable cryptosystems lately and have found it fascinating. I still have a lot of reading to do, however, I came across a statement in my reading that suggested malleability is inherently counter to security against chosen ciphertext attacks.
While I read up more about this relationship, I am curious to learn if there a way to maintain malleability while making a chosen ciphertext attack computationally infeasible? Why or why not?
homomorphic-encryption provable-security chosen-ciphertext-attack malleability
homomorphic-encryption provable-security chosen-ciphertext-attack malleability
edited Nov 26 at 20:55
kelalaka
5,28821939
asked Nov 26 at 20:38
hdu
284
edited Nov 26 at 20:55
kelalaka
5,28821939
asked Nov 26 at 20:38
hdu
284
edited Nov 26 at 20:55
kelalaka
5,28821939
edited Nov 26 at 20:55
kelalaka
5,28821939
edited Nov 26 at 20:55
kelalaka
5,28821939
5,28821939
asked Nov 26 at 20:38
hdu
284
asked Nov 26 at 20:38
hdu
284
asked Nov 26 at 20:38
hdu
284
284
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
I know of two lines of work on this question. It is indeed possible to allow malleability but still make some guarantees in the presence of a chosen-ciphertext attack:
Manoj Prabhakaran & Mike Rosulek: Reconciling Non-malleability with Homomorphic Encryption.
Dan Boneh and Gil Segev and Brent Waters: Targeted Malleability: Homomorphic Encryption for Restricted Computations.
Both papers present encryption schemes (and security definitions) that allow malleability $textsf{Enc}(m) leadsto textsf{Enc}(T(m))$ for some set of allowed transformations $T$ (as a feature), but where any other kind of malleability is infeasible.
As a concrete example, suppose the only allowable transformation is the identity transformation. Then it is possible to transform $textsf{Enc}(m)$ into another "fresh" encryption of the same (unknown) $m$. But it is infeasible to transform $textsf{Enc}(m)$ into any $m' ne m$ that is related to $m$. This special case is called "rerandomizable RCCA" encryption.
The first paper is my work, a combination of 3 of our conference papers; the one most relevant to your question is this one. Our construction has additional security requirement: a "transformed" ciphertext obtained via $textsf{Enc}(m) leadsto textsf{Enc}(T(m))$ should be indistinguishable from a "fresh" ciphertext (even to the private-key holder). We only consider the case of unary transformations, since n-ary transformations (i.e., combining several ciphertexts in a transformation) are impossible under these definitions.
The second paper does not have this extra requirement --- so "transformed" ciphertexts look different than "fresh" ciphertexts. They use an approach of appending a ZK proof that an allowable transformation was used on some original ciphertext.
answered Nov 26 at 21:58
Mikero
5,35411521
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%2f64335%2fis-there-a-way-of-maintaining-malleability-in-a-homomorphic-encryption-system-wh%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
I know of two lines of work on this question. It is indeed possible to allow malleability but still make some guarantees in the presence of a chosen-ciphertext attack:
Manoj Prabhakaran & Mike Rosulek: Reconciling Non-malleability with Homomorphic Encryption.
Dan Boneh and Gil Segev and Brent Waters: Targeted Malleability: Homomorphic Encryption for Restricted Computations.
Both papers present encryption schemes (and security definitions) that allow malleability $textsf{Enc}(m) leadsto textsf{Enc}(T(m))$ for some set of allowed transformations $T$ (as a feature), but where any other kind of malleability is infeasible.
As a concrete example, suppose the only allowable transformation is the identity transformation. Then it is possible to transform $textsf{Enc}(m)$ into another "fresh" encryption of the same (unknown) $m$. But it is infeasible to transform $textsf{Enc}(m)$ into any $m' ne m$ that is related to $m$. This special case is called "rerandomizable RCCA" encryption.
The first paper is my work, a combination of 3 of our conference papers; the one most relevant to your question is this one. Our construction has additional security requirement: a "transformed" ciphertext obtained via $textsf{Enc}(m) leadsto textsf{Enc}(T(m))$ should be indistinguishable from a "fresh" ciphertext (even to the private-key holder). We only consider the case of unary transformations, since n-ary transformations (i.e., combining several ciphertexts in a transformation) are impossible under these definitions.
The second paper does not have this extra requirement --- so "transformed" ciphertexts look different than "fresh" ciphertexts. They use an approach of appending a ZK proof that an allowable transformation was used on some original ciphertext.
answered Nov 26 at 21:58
Mikero
5,35411521
add a comment |
I know of two lines of work on this question. It is indeed possible to allow malleability but still make some guarantees in the presence of a chosen-ciphertext attack:
Manoj Prabhakaran & Mike Rosulek: Reconciling Non-malleability with Homomorphic Encryption.
Dan Boneh and Gil Segev and Brent Waters: Targeted Malleability: Homomorphic Encryption for Restricted Computations.
Both papers present encryption schemes (and security definitions) that allow malleability $textsf{Enc}(m) leadsto textsf{Enc}(T(m))$ for some set of allowed transformations $T$ (as a feature), but where any other kind of malleability is infeasible.
As a concrete example, suppose the only allowable transformation is the identity transformation. Then it is possible to transform $textsf{Enc}(m)$ into another "fresh" encryption of the same (unknown) $m$. But it is infeasible to transform $textsf{Enc}(m)$ into any $m' ne m$ that is related to $m$. This special case is called "rerandomizable RCCA" encryption.
The first paper is my work, a combination of 3 of our conference papers; the one most relevant to your question is this one. Our construction has additional security requirement: a "transformed" ciphertext obtained via $textsf{Enc}(m) leadsto textsf{Enc}(T(m))$ should be indistinguishable from a "fresh" ciphertext (even to the private-key holder). We only consider the case of unary transformations, since n-ary transformations (i.e., combining several ciphertexts in a transformation) are impossible under these definitions.
The second paper does not have this extra requirement --- so "transformed" ciphertexts look different than "fresh" ciphertexts. They use an approach of appending a ZK proof that an allowable transformation was used on some original ciphertext.
answered Nov 26 at 21:58
Mikero
5,35411521
add a comment |
I know of two lines of work on this question. It is indeed possible to allow malleability but still make some guarantees in the presence of a chosen-ciphertext attack:
Manoj Prabhakaran & Mike Rosulek: Reconciling Non-malleability with Homomorphic Encryption.
Dan Boneh and Gil Segev and Brent Waters: Targeted Malleability: Homomorphic Encryption for Restricted Computations.
Both papers present encryption schemes (and security definitions) that allow malleability $textsf{Enc}(m) leadsto textsf{Enc}(T(m))$ for some set of allowed transformations $T$ (as a feature), but where any other kind of malleability is infeasible.
As a concrete example, suppose the only allowable transformation is the identity transformation. Then it is possible to transform $textsf{Enc}(m)$ into another "fresh" encryption of the same (unknown) $m$. But it is infeasible to transform $textsf{Enc}(m)$ into any $m' ne m$ that is related to $m$. This special case is called "rerandomizable RCCA" encryption.
The first paper is my work, a combination of 3 of our conference papers; the one most relevant to your question is this one. Our construction has additional security requirement: a "transformed" ciphertext obtained via $textsf{Enc}(m) leadsto textsf{Enc}(T(m))$ should be indistinguishable from a "fresh" ciphertext (even to the private-key holder). We only consider the case of unary transformations, since n-ary transformations (i.e., combining several ciphertexts in a transformation) are impossible under these definitions.
The second paper does not have this extra requirement --- so "transformed" ciphertexts look different than "fresh" ciphertexts. They use an approach of appending a ZK proof that an allowable transformation was used on some original ciphertext.
answered Nov 26 at 21:58
Mikero
5,35411521
I know of two lines of work on this question. It is indeed possible to allow malleability but still make some guarantees in the presence of a chosen-ciphertext attack:
Manoj Prabhakaran & Mike Rosulek: Reconciling Non-malleability with Homomorphic Encryption.
Dan Boneh and Gil Segev and Brent Waters: Targeted Malleability: Homomorphic Encryption for Restricted Computations.
Both papers present encryption schemes (and security definitions) that allow malleability $textsf{Enc}(m) leadsto textsf{Enc}(T(m))$ for some set of allowed transformations $T$ (as a feature), but where any other kind of malleability is infeasible.
As a concrete example, suppose the only allowable transformation is the identity transformation. Then it is possible to transform $textsf{Enc}(m)$ into another "fresh" encryption of the same (unknown) $m$. But it is infeasible to transform $textsf{Enc}(m)$ into any $m' ne m$ that is related to $m$. This special case is called "rerandomizable RCCA" encryption.
The first paper is my work, a combination of 3 of our conference papers; the one most relevant to your question is this one. Our construction has additional security requirement: a "transformed" ciphertext obtained via $textsf{Enc}(m) leadsto textsf{Enc}(T(m))$ should be indistinguishable from a "fresh" ciphertext (even to the private-key holder). We only consider the case of unary transformations, since n-ary transformations (i.e., combining several ciphertexts in a transformation) are impossible under these definitions.
The second paper does not have this extra requirement --- so "transformed" ciphertexts look different than "fresh" ciphertexts. They use an approach of appending a ZK proof that an allowable transformation was used on some original ciphertext.
answered Nov 26 at 21:58
Mikero
5,35411521
edited Nov 26 at 22:19
answered Nov 26 at 21:58
Mikero
5,35411521
answered Nov 26 at 21:58
Mikero
5,35411521
answered Nov 26 at 21:58
Mikero
5,35411521
5,35411521
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%2f64335%2fis-there-a-way-of-maintaining-malleability-in-a-homomorphic-encryption-system-wh%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
