Is it possible to build a CPA-secure encryption scheme which remains secure even when the encryption of secret key is given?What is the “Random Oracle Model” and why is it controversial?Is the software that uses PGP broken, or is it PGP itself?Why is an Encrypt-and-MAC scheme with deterministic MAC not IND-CPA secure?Is the AES encryption scheme CPA secure?Building a combined encryption scheme from two encryption schemes that's secure if at least on of them is secureCiphertext size of any CPA-secure public-key encryption schemeProve that the given scheme is CPA secure or notAre there deterministic private-key encryption schemes that are CPA-secure?Proving that there is no scheme which would be perfectly CPA-secureCPA-secure private-key encryption scheme that is unforgeable but is not CCA-secureIs the scheme $(r, Mac_k(r) oplus m)$ CPA-secure?Proof that secret sharing based scheme is CPA secure as long as one of the scheme is CPA secure
Why did Kant, Hegel, and Adorno leave some words and phrases in the Greek alphabet?
Is HostGator storing my password in plaintext?
How do I rename a LINUX host without needing to reboot for the rename to take effect?
Why does John Bercow say “unlock” after reading out the results of a vote?
Do I need a multiple entry visa for a trip UK -> Sweden -> UK?
Why Were Madagascar and New Zealand Discovered So Late?
Why are on-board computers allowed to change controls without notifying the pilots?
Transcription Beats per minute
There is only s̶i̶x̶t̶y one place he can be
The baby cries all morning
Your magic is very sketchy
Hostile work environment after whistle-blowing on coworker and our boss. What do I do?
Greatest common substring
Was Spock the First Vulcan in Starfleet?
Is the destination of a commercial flight important for the pilot?
Opposite of a diet
What are the ramifications of creating a homebrew world without an Astral Plane?
Can I Retrieve Email Addresses from BCC?
Student evaluations of teaching assistants
Is there a problem with hiding "forgot password" until it's needed?
voltage of sounds of mp3files
Personal Teleportation as a Weapon
Can a monster with multiattack use this ability if they are missing a limb?
Generic lambda vs generic function give different behaviour
Is it possible to build a CPA-secure encryption scheme which remains secure even when the encryption of secret key is given?
What is the “Random Oracle Model” and why is it controversial?Is the software that uses PGP broken, or is it PGP itself?Why is an Encrypt-and-MAC scheme with deterministic MAC not IND-CPA secure?Is the AES encryption scheme CPA secure?Building a combined encryption scheme from two encryption schemes that's secure if at least on of them is secureCiphertext size of any CPA-secure public-key encryption schemeProve that the given scheme is CPA secure or notAre there deterministic private-key encryption schemes that are CPA-secure?Proving that there is no scheme which would be perfectly CPA-secureCPA-secure private-key encryption scheme that is unforgeable but is not CCA-secureIs the scheme $(r, Mac_k(r) oplus m)$ CPA-secure?Proof that secret sharing based scheme is CPA secure as long as one of the scheme is CPA secure
$begingroup$
How can I design a CPA-secure encryption scheme which is secure even after the encryption of secret key is given in the training phase? I.e., in the training phase, $mathitEnc_mathitpk(mathitsk)$ is given to the attacker, where $(mathitsk,mathitpk)$ is the key pair.
chosen-plaintext-attack
New contributor
$endgroup$
add a comment |
$begingroup$
How can I design a CPA-secure encryption scheme which is secure even after the encryption of secret key is given in the training phase? I.e., in the training phase, $mathitEnc_mathitpk(mathitsk)$ is given to the attacker, where $(mathitsk,mathitpk)$ is the key pair.
chosen-plaintext-attack
New contributor
$endgroup$
$begingroup$
We can also assume that there exists a deterministic poly time algorithm T that on input sk outputs pk.
$endgroup$
– kiran
yesterday
add a comment |
$begingroup$
How can I design a CPA-secure encryption scheme which is secure even after the encryption of secret key is given in the training phase? I.e., in the training phase, $mathitEnc_mathitpk(mathitsk)$ is given to the attacker, where $(mathitsk,mathitpk)$ is the key pair.
chosen-plaintext-attack
New contributor
$endgroup$
How can I design a CPA-secure encryption scheme which is secure even after the encryption of secret key is given in the training phase? I.e., in the training phase, $mathitEnc_mathitpk(mathitsk)$ is given to the attacker, where $(mathitsk,mathitpk)$ is the key pair.
chosen-plaintext-attack
chosen-plaintext-attack
New contributor
New contributor
edited 19 hours ago
Squeamish Ossifrage
21.3k13198
21.3k13198
New contributor
asked yesterday
kirankiran
334
334
New contributor
New contributor
$begingroup$
We can also assume that there exists a deterministic poly time algorithm T that on input sk outputs pk.
$endgroup$
– kiran
yesterday
add a comment |
$begingroup$
We can also assume that there exists a deterministic poly time algorithm T that on input sk outputs pk.
$endgroup$
– kiran
yesterday
$begingroup$
We can also assume that there exists a deterministic poly time algorithm T that on input sk outputs pk.
$endgroup$
– kiran
yesterday
$begingroup$
We can also assume that there exists a deterministic poly time algorithm T that on input sk outputs pk.
$endgroup$
– kiran
yesterday
add a comment |
3 Answers
3
active
oldest
votes
$begingroup$
It turns out that what you are looking for is not trivial... A scheme that satisfies such property is called (CPA) circular secure scheme.
There are some schemes that satisfy that, but I don't know if they have publicly available implementions. For example, you can take a look to this scheme.
In the notation used on the paper, $ell$ is the number of pairs of public and secret keys (so, in your case, $ell = 1$). They prove a stronger security notion (KDM - Key dependent messages) that implies circular security (at least in their setting).
--EDIT--
As the other users pointed out, on the Random Oracle Model (ROM) there are other (more standard) constructions which meet this security definition. When I wrote this answer, I didn't consider this security model, but I made this unconsciously. I didn't want to say that schemes proved secure on ROM must be simply rejected. To be honest, I think that a correct answer to your question should merge my original answer with other answers and point out these details.
$endgroup$
add a comment |
$begingroup$
You're in luck! Essentially every secure public-key encryption scheme on bit strings that is actually in use already has this property—and, even better, not just IND-CPA but often IND-CCA2/NM-CCA2*—because they can all be factored into a KEM/DEM structure via a hash function $H$ like SHAKE128:†
(KEM) Generate a uniform random $k$ and encapsulation $y$ using $mathitpk$.
Examples:
RSA-KEM: $mathitpk = n$, a large integer; choose $x$ uniformly at random in $0, 1, 2, dots, n - 1$, and compute $y = x^3 bmod n$ and $k = H(x)$.
The recipient will recover $x = y^d bmod n$ with secret knowledge of $d equiv e^-1 pmodlambda(n)$.
RSA-OAEP KEM: $mathitpk = n$, a large integer; choose $k$ and $r$ uniformly at random, compute $a = k oplus H(0 mathbin| r), b = r oplus H(1 mathbin| a)$ (of appropriate bit lengths so they fill a $lfloorlog_2 nrfloor$-bit integer), and $y = (a mathbin| b)^3 bmod n$.
The recipient will recover $a mathbin| b = y^d bmod n$ with secret knowledge of $d equiv e^-1 pmodlambda(n)$, and then solve for $k$.
DH-based KEM: $mathitpk = h$, an element of prime order in a group $G$ generated by a standard base $g$; choose $x$ uniformly at random, and compute $y = g^x$, and $k = H(h^x)$.
The recipient will recover $k = H(y^z)$ with secret knowledge of $z$ such that $h = g^z$, so that $h^x = (g^z)^x = (g^x)^z = y^z$.
(DEM) Use $k$ as a one-time key for a one-time authenticated cipher $operatornameAE$ to encrypt the message $m$ as $c = operatornameAE_k(m)$.
Any authenticated cipher works here, like AES-GCM or crypto_secretbox_xsalsa20poly1305; technically the security requirements of a DEM are lighter than AEAD, e.g. you could just use most of $k$ as a one-time pad and the rest as a one-time authenticator key, but it is simplest—and most common—to use an authenticated cipher.
Transmit $(y, c)$, the encapsulation $y$ of the one-time key $k$ and the authenticated encryption $c$ of the message $m$.
The one-time key $k$ is (effectively) independent of the secret key $mathitsk$, so there is no problem with the symmetric encryption $operatornameAE_k(mathitsk)$ used here.
This notion of security is sometimes called circular security or key-dependent message (KDM) security.
- In 2001, Camenisch and Lysyanskaya defined circular security and proved that $(m, r) mapsto E_mathitpk(r) mathbin| (H(r) oplus m)$ for uniform random $r$ has it if $E_mathitpk$ is semantically secure[1].
- Independently, in 2002, Black, Rogaway, and Shrimpton defined the slightly stronger KDM security and suggested but could not prove that KEM/DEM hybrid constructions like this would have it[2].
- Then in 2014, Davies and Stam finally found formal techniques to prove that KEM/DEM via $H$ generically has KDM security[3].
Skipping the hash $H$, of course, can ruin the security, as in many cryptosystems. If for some reason you need a system that is secure even without a hash, then the Camenisch–Lysyanskaya and Black–Rogaway–Shrimpton papers are a good starting point for a literature search, with over a thousand papers citing them, from a cursory glance.
Of course, if you need additional structure—e.g., the homomorphic property of Elgamal encryption $(h^r, g^r m)$ for a highly restricted message space—then the answer may be different, because such additional structure is incompatible with NM-CCA2. But in that case, you'll need to ask a more specific question about your specific additional structure.
* Well, some of the practical ones fail IND-CCA2/NM-CCA2, like S/MIME and OpenPGP, because their designers made foolish decisions leading to EFAIL[4]. But those particular mistakes don't imply problems with circular/KDM security: they are still effectively factored into KEM/not-quite-DEM.
† In academic cryptography jargon, the security here is usually presented in the ‘random oracle model’. Essentially, this means that we can prove any attacker that doesn't depend on the details of $H$ can be used, if parametrized by $H$, as a subroutine in a procedure to factor large semiprimes, compute discrete logs, etc. In principle, it could be that particular choices of hash function $H$ could interact with the public-key mathematical structure to enable other attacks; pathological examples have been exhibited[5] where any choice of hash function is insecure. But these pathological examples are of little consequence in the real world, and they give no reason to doubt the practical security of the KEMs actually in widespread use today like these; these pathological examples are more of an interesting quirk of the formalism than anything else. More on the random oracle model.
$endgroup$
$begingroup$
great. thanks a lot
$endgroup$
– kiran
yesterday
2
$begingroup$
The accepted answer (from Hilder Vítor) appears to contradict you. Is it because you are dismissing the "pathological examples"?
$endgroup$
– OrangeDog
yesterday
2
$begingroup$
@OrangeDog It would seem that Hilder tacitly rejects the random oracle model altogether—which flies in the face of essentially all public-key cryptography in practice. This is a perspective taken by some academic cryptography theoreticians, but it explains why one can't find practical implementations: because practitioners are justifiably unconcerned by the contortions that Canetti–Goldreich–Halevi go through to exhibit pathological counterexamples. By the same token, one might reject SHA-3 because there's technically no formalization of its ‘collision resistance’, per se.
$endgroup$
– Squeamish Ossifrage
yesterday
$begingroup$
@OrangeDog In particular, Canetti–Goldreich–Halevi concoct a signature scheme leaks the private key on inputs of the form $(x, H(x), pi)$ where $pi$ is a valid proof that $(x, H(x))$ is in the graph of some fixed polynomial-time function ensemble, which has negligible probability when $H$ is a uniform random function so the scheme is ROM-secure, but can be exhibited easily when $H$ is drawn from any concrete family of functions so the scheme is not instantiable. In other words, it's a signature scheme that by construction throws a tantrum if you instantiate it in practice.
$endgroup$
– Squeamish Ossifrage
yesterday
1
$begingroup$
@OrangeDog The theoretical concern high in the ivory tower is that a counterexample proves that ROM security doesn't imply concrete security. The sensible inference is not that schemes with ROM security should be silently ignored. Rather, there is probably some technical criterion separating the pathologically hopeless cases like Canetti–Goldreich–Halevi's tantrum-throwing signatures from real schemes we actually use, which we haven't identified yet. It's not the only such academic problem: collision resistance, free precomputation, etc., also have technical issues of little consequence.
$endgroup$
– Squeamish Ossifrage
yesterday
|
show 2 more comments
$begingroup$
This is secure for practically all hybrid asymmetric encryption algorithms, like ECIES or RSA-KEM. However it violates the security assumptions of the standard model, so you have to resort to the random oracle model.
I would avoid overly complicated designs, like those from the paper Hilder mentions, just for the sake of a standard model security proof.
New contributor
$endgroup$
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
);
);
kiran is a new contributor. Be nice, and check out our Code of Conduct.
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%2f68270%2fis-it-possible-to-build-a-cpa-secure-encryption-scheme-which-remains-secure-even%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
$begingroup$
It turns out that what you are looking for is not trivial... A scheme that satisfies such property is called (CPA) circular secure scheme.
There are some schemes that satisfy that, but I don't know if they have publicly available implementions. For example, you can take a look to this scheme.
In the notation used on the paper, $ell$ is the number of pairs of public and secret keys (so, in your case, $ell = 1$). They prove a stronger security notion (KDM - Key dependent messages) that implies circular security (at least in their setting).
--EDIT--
As the other users pointed out, on the Random Oracle Model (ROM) there are other (more standard) constructions which meet this security definition. When I wrote this answer, I didn't consider this security model, but I made this unconsciously. I didn't want to say that schemes proved secure on ROM must be simply rejected. To be honest, I think that a correct answer to your question should merge my original answer with other answers and point out these details.
$endgroup$
add a comment |
$begingroup$
It turns out that what you are looking for is not trivial... A scheme that satisfies such property is called (CPA) circular secure scheme.
There are some schemes that satisfy that, but I don't know if they have publicly available implementions. For example, you can take a look to this scheme.
In the notation used on the paper, $ell$ is the number of pairs of public and secret keys (so, in your case, $ell = 1$). They prove a stronger security notion (KDM - Key dependent messages) that implies circular security (at least in their setting).
--EDIT--
As the other users pointed out, on the Random Oracle Model (ROM) there are other (more standard) constructions which meet this security definition. When I wrote this answer, I didn't consider this security model, but I made this unconsciously. I didn't want to say that schemes proved secure on ROM must be simply rejected. To be honest, I think that a correct answer to your question should merge my original answer with other answers and point out these details.
$endgroup$
add a comment |
$begingroup$
It turns out that what you are looking for is not trivial... A scheme that satisfies such property is called (CPA) circular secure scheme.
There are some schemes that satisfy that, but I don't know if they have publicly available implementions. For example, you can take a look to this scheme.
In the notation used on the paper, $ell$ is the number of pairs of public and secret keys (so, in your case, $ell = 1$). They prove a stronger security notion (KDM - Key dependent messages) that implies circular security (at least in their setting).
--EDIT--
As the other users pointed out, on the Random Oracle Model (ROM) there are other (more standard) constructions which meet this security definition. When I wrote this answer, I didn't consider this security model, but I made this unconsciously. I didn't want to say that schemes proved secure on ROM must be simply rejected. To be honest, I think that a correct answer to your question should merge my original answer with other answers and point out these details.
$endgroup$
It turns out that what you are looking for is not trivial... A scheme that satisfies such property is called (CPA) circular secure scheme.
There are some schemes that satisfy that, but I don't know if they have publicly available implementions. For example, you can take a look to this scheme.
In the notation used on the paper, $ell$ is the number of pairs of public and secret keys (so, in your case, $ell = 1$). They prove a stronger security notion (KDM - Key dependent messages) that implies circular security (at least in their setting).
--EDIT--
As the other users pointed out, on the Random Oracle Model (ROM) there are other (more standard) constructions which meet this security definition. When I wrote this answer, I didn't consider this security model, but I made this unconsciously. I didn't want to say that schemes proved secure on ROM must be simply rejected. To be honest, I think that a correct answer to your question should merge my original answer with other answers and point out these details.
edited 18 hours ago
answered yesterday
Hilder Vítor Lima PereiraHilder Vítor Lima Pereira
4,019930
4,019930
add a comment |
add a comment |
$begingroup$
You're in luck! Essentially every secure public-key encryption scheme on bit strings that is actually in use already has this property—and, even better, not just IND-CPA but often IND-CCA2/NM-CCA2*—because they can all be factored into a KEM/DEM structure via a hash function $H$ like SHAKE128:†
(KEM) Generate a uniform random $k$ and encapsulation $y$ using $mathitpk$.
Examples:
RSA-KEM: $mathitpk = n$, a large integer; choose $x$ uniformly at random in $0, 1, 2, dots, n - 1$, and compute $y = x^3 bmod n$ and $k = H(x)$.
The recipient will recover $x = y^d bmod n$ with secret knowledge of $d equiv e^-1 pmodlambda(n)$.
RSA-OAEP KEM: $mathitpk = n$, a large integer; choose $k$ and $r$ uniformly at random, compute $a = k oplus H(0 mathbin| r), b = r oplus H(1 mathbin| a)$ (of appropriate bit lengths so they fill a $lfloorlog_2 nrfloor$-bit integer), and $y = (a mathbin| b)^3 bmod n$.
The recipient will recover $a mathbin| b = y^d bmod n$ with secret knowledge of $d equiv e^-1 pmodlambda(n)$, and then solve for $k$.
DH-based KEM: $mathitpk = h$, an element of prime order in a group $G$ generated by a standard base $g$; choose $x$ uniformly at random, and compute $y = g^x$, and $k = H(h^x)$.
The recipient will recover $k = H(y^z)$ with secret knowledge of $z$ such that $h = g^z$, so that $h^x = (g^z)^x = (g^x)^z = y^z$.
(DEM) Use $k$ as a one-time key for a one-time authenticated cipher $operatornameAE$ to encrypt the message $m$ as $c = operatornameAE_k(m)$.
Any authenticated cipher works here, like AES-GCM or crypto_secretbox_xsalsa20poly1305; technically the security requirements of a DEM are lighter than AEAD, e.g. you could just use most of $k$ as a one-time pad and the rest as a one-time authenticator key, but it is simplest—and most common—to use an authenticated cipher.
Transmit $(y, c)$, the encapsulation $y$ of the one-time key $k$ and the authenticated encryption $c$ of the message $m$.
The one-time key $k$ is (effectively) independent of the secret key $mathitsk$, so there is no problem with the symmetric encryption $operatornameAE_k(mathitsk)$ used here.
This notion of security is sometimes called circular security or key-dependent message (KDM) security.
- In 2001, Camenisch and Lysyanskaya defined circular security and proved that $(m, r) mapsto E_mathitpk(r) mathbin| (H(r) oplus m)$ for uniform random $r$ has it if $E_mathitpk$ is semantically secure[1].
- Independently, in 2002, Black, Rogaway, and Shrimpton defined the slightly stronger KDM security and suggested but could not prove that KEM/DEM hybrid constructions like this would have it[2].
- Then in 2014, Davies and Stam finally found formal techniques to prove that KEM/DEM via $H$ generically has KDM security[3].
Skipping the hash $H$, of course, can ruin the security, as in many cryptosystems. If for some reason you need a system that is secure even without a hash, then the Camenisch–Lysyanskaya and Black–Rogaway–Shrimpton papers are a good starting point for a literature search, with over a thousand papers citing them, from a cursory glance.
Of course, if you need additional structure—e.g., the homomorphic property of Elgamal encryption $(h^r, g^r m)$ for a highly restricted message space—then the answer may be different, because such additional structure is incompatible with NM-CCA2. But in that case, you'll need to ask a more specific question about your specific additional structure.
* Well, some of the practical ones fail IND-CCA2/NM-CCA2, like S/MIME and OpenPGP, because their designers made foolish decisions leading to EFAIL[4]. But those particular mistakes don't imply problems with circular/KDM security: they are still effectively factored into KEM/not-quite-DEM.
† In academic cryptography jargon, the security here is usually presented in the ‘random oracle model’. Essentially, this means that we can prove any attacker that doesn't depend on the details of $H$ can be used, if parametrized by $H$, as a subroutine in a procedure to factor large semiprimes, compute discrete logs, etc. In principle, it could be that particular choices of hash function $H$ could interact with the public-key mathematical structure to enable other attacks; pathological examples have been exhibited[5] where any choice of hash function is insecure. But these pathological examples are of little consequence in the real world, and they give no reason to doubt the practical security of the KEMs actually in widespread use today like these; these pathological examples are more of an interesting quirk of the formalism than anything else. More on the random oracle model.
$endgroup$
$begingroup$
great. thanks a lot
$endgroup$
– kiran
yesterday
2
$begingroup$
The accepted answer (from Hilder Vítor) appears to contradict you. Is it because you are dismissing the "pathological examples"?
$endgroup$
– OrangeDog
yesterday
2
$begingroup$
@OrangeDog It would seem that Hilder tacitly rejects the random oracle model altogether—which flies in the face of essentially all public-key cryptography in practice. This is a perspective taken by some academic cryptography theoreticians, but it explains why one can't find practical implementations: because practitioners are justifiably unconcerned by the contortions that Canetti–Goldreich–Halevi go through to exhibit pathological counterexamples. By the same token, one might reject SHA-3 because there's technically no formalization of its ‘collision resistance’, per se.
$endgroup$
– Squeamish Ossifrage
yesterday
$begingroup$
@OrangeDog In particular, Canetti–Goldreich–Halevi concoct a signature scheme leaks the private key on inputs of the form $(x, H(x), pi)$ where $pi$ is a valid proof that $(x, H(x))$ is in the graph of some fixed polynomial-time function ensemble, which has negligible probability when $H$ is a uniform random function so the scheme is ROM-secure, but can be exhibited easily when $H$ is drawn from any concrete family of functions so the scheme is not instantiable. In other words, it's a signature scheme that by construction throws a tantrum if you instantiate it in practice.
$endgroup$
– Squeamish Ossifrage
yesterday
1
$begingroup$
@OrangeDog The theoretical concern high in the ivory tower is that a counterexample proves that ROM security doesn't imply concrete security. The sensible inference is not that schemes with ROM security should be silently ignored. Rather, there is probably some technical criterion separating the pathologically hopeless cases like Canetti–Goldreich–Halevi's tantrum-throwing signatures from real schemes we actually use, which we haven't identified yet. It's not the only such academic problem: collision resistance, free precomputation, etc., also have technical issues of little consequence.
$endgroup$
– Squeamish Ossifrage
yesterday
|
show 2 more comments
$begingroup$
You're in luck! Essentially every secure public-key encryption scheme on bit strings that is actually in use already has this property—and, even better, not just IND-CPA but often IND-CCA2/NM-CCA2*—because they can all be factored into a KEM/DEM structure via a hash function $H$ like SHAKE128:†
(KEM) Generate a uniform random $k$ and encapsulation $y$ using $mathitpk$.
Examples:
RSA-KEM: $mathitpk = n$, a large integer; choose $x$ uniformly at random in $0, 1, 2, dots, n - 1$, and compute $y = x^3 bmod n$ and $k = H(x)$.
The recipient will recover $x = y^d bmod n$ with secret knowledge of $d equiv e^-1 pmodlambda(n)$.
RSA-OAEP KEM: $mathitpk = n$, a large integer; choose $k$ and $r$ uniformly at random, compute $a = k oplus H(0 mathbin| r), b = r oplus H(1 mathbin| a)$ (of appropriate bit lengths so they fill a $lfloorlog_2 nrfloor$-bit integer), and $y = (a mathbin| b)^3 bmod n$.
The recipient will recover $a mathbin| b = y^d bmod n$ with secret knowledge of $d equiv e^-1 pmodlambda(n)$, and then solve for $k$.
DH-based KEM: $mathitpk = h$, an element of prime order in a group $G$ generated by a standard base $g$; choose $x$ uniformly at random, and compute $y = g^x$, and $k = H(h^x)$.
The recipient will recover $k = H(y^z)$ with secret knowledge of $z$ such that $h = g^z$, so that $h^x = (g^z)^x = (g^x)^z = y^z$.
(DEM) Use $k$ as a one-time key for a one-time authenticated cipher $operatornameAE$ to encrypt the message $m$ as $c = operatornameAE_k(m)$.
Any authenticated cipher works here, like AES-GCM or crypto_secretbox_xsalsa20poly1305; technically the security requirements of a DEM are lighter than AEAD, e.g. you could just use most of $k$ as a one-time pad and the rest as a one-time authenticator key, but it is simplest—and most common—to use an authenticated cipher.
Transmit $(y, c)$, the encapsulation $y$ of the one-time key $k$ and the authenticated encryption $c$ of the message $m$.
The one-time key $k$ is (effectively) independent of the secret key $mathitsk$, so there is no problem with the symmetric encryption $operatornameAE_k(mathitsk)$ used here.
This notion of security is sometimes called circular security or key-dependent message (KDM) security.
- In 2001, Camenisch and Lysyanskaya defined circular security and proved that $(m, r) mapsto E_mathitpk(r) mathbin| (H(r) oplus m)$ for uniform random $r$ has it if $E_mathitpk$ is semantically secure[1].
- Independently, in 2002, Black, Rogaway, and Shrimpton defined the slightly stronger KDM security and suggested but could not prove that KEM/DEM hybrid constructions like this would have it[2].
- Then in 2014, Davies and Stam finally found formal techniques to prove that KEM/DEM via $H$ generically has KDM security[3].
Skipping the hash $H$, of course, can ruin the security, as in many cryptosystems. If for some reason you need a system that is secure even without a hash, then the Camenisch–Lysyanskaya and Black–Rogaway–Shrimpton papers are a good starting point for a literature search, with over a thousand papers citing them, from a cursory glance.
Of course, if you need additional structure—e.g., the homomorphic property of Elgamal encryption $(h^r, g^r m)$ for a highly restricted message space—then the answer may be different, because such additional structure is incompatible with NM-CCA2. But in that case, you'll need to ask a more specific question about your specific additional structure.
* Well, some of the practical ones fail IND-CCA2/NM-CCA2, like S/MIME and OpenPGP, because their designers made foolish decisions leading to EFAIL[4]. But those particular mistakes don't imply problems with circular/KDM security: they are still effectively factored into KEM/not-quite-DEM.
† In academic cryptography jargon, the security here is usually presented in the ‘random oracle model’. Essentially, this means that we can prove any attacker that doesn't depend on the details of $H$ can be used, if parametrized by $H$, as a subroutine in a procedure to factor large semiprimes, compute discrete logs, etc. In principle, it could be that particular choices of hash function $H$ could interact with the public-key mathematical structure to enable other attacks; pathological examples have been exhibited[5] where any choice of hash function is insecure. But these pathological examples are of little consequence in the real world, and they give no reason to doubt the practical security of the KEMs actually in widespread use today like these; these pathological examples are more of an interesting quirk of the formalism than anything else. More on the random oracle model.
$endgroup$
$begingroup$
great. thanks a lot
$endgroup$
– kiran
yesterday
2
$begingroup$
The accepted answer (from Hilder Vítor) appears to contradict you. Is it because you are dismissing the "pathological examples"?
$endgroup$
– OrangeDog
yesterday
2
$begingroup$
@OrangeDog It would seem that Hilder tacitly rejects the random oracle model altogether—which flies in the face of essentially all public-key cryptography in practice. This is a perspective taken by some academic cryptography theoreticians, but it explains why one can't find practical implementations: because practitioners are justifiably unconcerned by the contortions that Canetti–Goldreich–Halevi go through to exhibit pathological counterexamples. By the same token, one might reject SHA-3 because there's technically no formalization of its ‘collision resistance’, per se.
$endgroup$
– Squeamish Ossifrage
yesterday
$begingroup$
@OrangeDog In particular, Canetti–Goldreich–Halevi concoct a signature scheme leaks the private key on inputs of the form $(x, H(x), pi)$ where $pi$ is a valid proof that $(x, H(x))$ is in the graph of some fixed polynomial-time function ensemble, which has negligible probability when $H$ is a uniform random function so the scheme is ROM-secure, but can be exhibited easily when $H$ is drawn from any concrete family of functions so the scheme is not instantiable. In other words, it's a signature scheme that by construction throws a tantrum if you instantiate it in practice.
$endgroup$
– Squeamish Ossifrage
yesterday
1
$begingroup$
@OrangeDog The theoretical concern high in the ivory tower is that a counterexample proves that ROM security doesn't imply concrete security. The sensible inference is not that schemes with ROM security should be silently ignored. Rather, there is probably some technical criterion separating the pathologically hopeless cases like Canetti–Goldreich–Halevi's tantrum-throwing signatures from real schemes we actually use, which we haven't identified yet. It's not the only such academic problem: collision resistance, free precomputation, etc., also have technical issues of little consequence.
$endgroup$
– Squeamish Ossifrage
yesterday
|
show 2 more comments
$begingroup$
You're in luck! Essentially every secure public-key encryption scheme on bit strings that is actually in use already has this property—and, even better, not just IND-CPA but often IND-CCA2/NM-CCA2*—because they can all be factored into a KEM/DEM structure via a hash function $H$ like SHAKE128:†
(KEM) Generate a uniform random $k$ and encapsulation $y$ using $mathitpk$.
Examples:
RSA-KEM: $mathitpk = n$, a large integer; choose $x$ uniformly at random in $0, 1, 2, dots, n - 1$, and compute $y = x^3 bmod n$ and $k = H(x)$.
The recipient will recover $x = y^d bmod n$ with secret knowledge of $d equiv e^-1 pmodlambda(n)$.
RSA-OAEP KEM: $mathitpk = n$, a large integer; choose $k$ and $r$ uniformly at random, compute $a = k oplus H(0 mathbin| r), b = r oplus H(1 mathbin| a)$ (of appropriate bit lengths so they fill a $lfloorlog_2 nrfloor$-bit integer), and $y = (a mathbin| b)^3 bmod n$.
The recipient will recover $a mathbin| b = y^d bmod n$ with secret knowledge of $d equiv e^-1 pmodlambda(n)$, and then solve for $k$.
DH-based KEM: $mathitpk = h$, an element of prime order in a group $G$ generated by a standard base $g$; choose $x$ uniformly at random, and compute $y = g^x$, and $k = H(h^x)$.
The recipient will recover $k = H(y^z)$ with secret knowledge of $z$ such that $h = g^z$, so that $h^x = (g^z)^x = (g^x)^z = y^z$.
(DEM) Use $k$ as a one-time key for a one-time authenticated cipher $operatornameAE$ to encrypt the message $m$ as $c = operatornameAE_k(m)$.
Any authenticated cipher works here, like AES-GCM or crypto_secretbox_xsalsa20poly1305; technically the security requirements of a DEM are lighter than AEAD, e.g. you could just use most of $k$ as a one-time pad and the rest as a one-time authenticator key, but it is simplest—and most common—to use an authenticated cipher.
Transmit $(y, c)$, the encapsulation $y$ of the one-time key $k$ and the authenticated encryption $c$ of the message $m$.
The one-time key $k$ is (effectively) independent of the secret key $mathitsk$, so there is no problem with the symmetric encryption $operatornameAE_k(mathitsk)$ used here.
This notion of security is sometimes called circular security or key-dependent message (KDM) security.
- In 2001, Camenisch and Lysyanskaya defined circular security and proved that $(m, r) mapsto E_mathitpk(r) mathbin| (H(r) oplus m)$ for uniform random $r$ has it if $E_mathitpk$ is semantically secure[1].
- Independently, in 2002, Black, Rogaway, and Shrimpton defined the slightly stronger KDM security and suggested but could not prove that KEM/DEM hybrid constructions like this would have it[2].
- Then in 2014, Davies and Stam finally found formal techniques to prove that KEM/DEM via $H$ generically has KDM security[3].
Skipping the hash $H$, of course, can ruin the security, as in many cryptosystems. If for some reason you need a system that is secure even without a hash, then the Camenisch–Lysyanskaya and Black–Rogaway–Shrimpton papers are a good starting point for a literature search, with over a thousand papers citing them, from a cursory glance.
Of course, if you need additional structure—e.g., the homomorphic property of Elgamal encryption $(h^r, g^r m)$ for a highly restricted message space—then the answer may be different, because such additional structure is incompatible with NM-CCA2. But in that case, you'll need to ask a more specific question about your specific additional structure.
* Well, some of the practical ones fail IND-CCA2/NM-CCA2, like S/MIME and OpenPGP, because their designers made foolish decisions leading to EFAIL[4]. But those particular mistakes don't imply problems with circular/KDM security: they are still effectively factored into KEM/not-quite-DEM.
† In academic cryptography jargon, the security here is usually presented in the ‘random oracle model’. Essentially, this means that we can prove any attacker that doesn't depend on the details of $H$ can be used, if parametrized by $H$, as a subroutine in a procedure to factor large semiprimes, compute discrete logs, etc. In principle, it could be that particular choices of hash function $H$ could interact with the public-key mathematical structure to enable other attacks; pathological examples have been exhibited[5] where any choice of hash function is insecure. But these pathological examples are of little consequence in the real world, and they give no reason to doubt the practical security of the KEMs actually in widespread use today like these; these pathological examples are more of an interesting quirk of the formalism than anything else. More on the random oracle model.
$endgroup$
You're in luck! Essentially every secure public-key encryption scheme on bit strings that is actually in use already has this property—and, even better, not just IND-CPA but often IND-CCA2/NM-CCA2*—because they can all be factored into a KEM/DEM structure via a hash function $H$ like SHAKE128:†
(KEM) Generate a uniform random $k$ and encapsulation $y$ using $mathitpk$.
Examples:
RSA-KEM: $mathitpk = n$, a large integer; choose $x$ uniformly at random in $0, 1, 2, dots, n - 1$, and compute $y = x^3 bmod n$ and $k = H(x)$.
The recipient will recover $x = y^d bmod n$ with secret knowledge of $d equiv e^-1 pmodlambda(n)$.
RSA-OAEP KEM: $mathitpk = n$, a large integer; choose $k$ and $r$ uniformly at random, compute $a = k oplus H(0 mathbin| r), b = r oplus H(1 mathbin| a)$ (of appropriate bit lengths so they fill a $lfloorlog_2 nrfloor$-bit integer), and $y = (a mathbin| b)^3 bmod n$.
The recipient will recover $a mathbin| b = y^d bmod n$ with secret knowledge of $d equiv e^-1 pmodlambda(n)$, and then solve for $k$.
DH-based KEM: $mathitpk = h$, an element of prime order in a group $G$ generated by a standard base $g$; choose $x$ uniformly at random, and compute $y = g^x$, and $k = H(h^x)$.
The recipient will recover $k = H(y^z)$ with secret knowledge of $z$ such that $h = g^z$, so that $h^x = (g^z)^x = (g^x)^z = y^z$.
(DEM) Use $k$ as a one-time key for a one-time authenticated cipher $operatornameAE$ to encrypt the message $m$ as $c = operatornameAE_k(m)$.
Any authenticated cipher works here, like AES-GCM or crypto_secretbox_xsalsa20poly1305; technically the security requirements of a DEM are lighter than AEAD, e.g. you could just use most of $k$ as a one-time pad and the rest as a one-time authenticator key, but it is simplest—and most common—to use an authenticated cipher.
Transmit $(y, c)$, the encapsulation $y$ of the one-time key $k$ and the authenticated encryption $c$ of the message $m$.
The one-time key $k$ is (effectively) independent of the secret key $mathitsk$, so there is no problem with the symmetric encryption $operatornameAE_k(mathitsk)$ used here.
This notion of security is sometimes called circular security or key-dependent message (KDM) security.
- In 2001, Camenisch and Lysyanskaya defined circular security and proved that $(m, r) mapsto E_mathitpk(r) mathbin| (H(r) oplus m)$ for uniform random $r$ has it if $E_mathitpk$ is semantically secure[1].
- Independently, in 2002, Black, Rogaway, and Shrimpton defined the slightly stronger KDM security and suggested but could not prove that KEM/DEM hybrid constructions like this would have it[2].
- Then in 2014, Davies and Stam finally found formal techniques to prove that KEM/DEM via $H$ generically has KDM security[3].
Skipping the hash $H$, of course, can ruin the security, as in many cryptosystems. If for some reason you need a system that is secure even without a hash, then the Camenisch–Lysyanskaya and Black–Rogaway–Shrimpton papers are a good starting point for a literature search, with over a thousand papers citing them, from a cursory glance.
Of course, if you need additional structure—e.g., the homomorphic property of Elgamal encryption $(h^r, g^r m)$ for a highly restricted message space—then the answer may be different, because such additional structure is incompatible with NM-CCA2. But in that case, you'll need to ask a more specific question about your specific additional structure.
* Well, some of the practical ones fail IND-CCA2/NM-CCA2, like S/MIME and OpenPGP, because their designers made foolish decisions leading to EFAIL[4]. But those particular mistakes don't imply problems with circular/KDM security: they are still effectively factored into KEM/not-quite-DEM.
† In academic cryptography jargon, the security here is usually presented in the ‘random oracle model’. Essentially, this means that we can prove any attacker that doesn't depend on the details of $H$ can be used, if parametrized by $H$, as a subroutine in a procedure to factor large semiprimes, compute discrete logs, etc. In principle, it could be that particular choices of hash function $H$ could interact with the public-key mathematical structure to enable other attacks; pathological examples have been exhibited[5] where any choice of hash function is insecure. But these pathological examples are of little consequence in the real world, and they give no reason to doubt the practical security of the KEMs actually in widespread use today like these; these pathological examples are more of an interesting quirk of the formalism than anything else. More on the random oracle model.
edited 7 hours ago
answered yesterday
Squeamish OssifrageSqueamish Ossifrage
21.3k13198
21.3k13198
$begingroup$
great. thanks a lot
$endgroup$
– kiran
yesterday
2
$begingroup$
The accepted answer (from Hilder Vítor) appears to contradict you. Is it because you are dismissing the "pathological examples"?
$endgroup$
– OrangeDog
yesterday
2
$begingroup$
@OrangeDog It would seem that Hilder tacitly rejects the random oracle model altogether—which flies in the face of essentially all public-key cryptography in practice. This is a perspective taken by some academic cryptography theoreticians, but it explains why one can't find practical implementations: because practitioners are justifiably unconcerned by the contortions that Canetti–Goldreich–Halevi go through to exhibit pathological counterexamples. By the same token, one might reject SHA-3 because there's technically no formalization of its ‘collision resistance’, per se.
$endgroup$
– Squeamish Ossifrage
yesterday
$begingroup$
@OrangeDog In particular, Canetti–Goldreich–Halevi concoct a signature scheme leaks the private key on inputs of the form $(x, H(x), pi)$ where $pi$ is a valid proof that $(x, H(x))$ is in the graph of some fixed polynomial-time function ensemble, which has negligible probability when $H$ is a uniform random function so the scheme is ROM-secure, but can be exhibited easily when $H$ is drawn from any concrete family of functions so the scheme is not instantiable. In other words, it's a signature scheme that by construction throws a tantrum if you instantiate it in practice.
$endgroup$
– Squeamish Ossifrage
yesterday
1
$begingroup$
@OrangeDog The theoretical concern high in the ivory tower is that a counterexample proves that ROM security doesn't imply concrete security. The sensible inference is not that schemes with ROM security should be silently ignored. Rather, there is probably some technical criterion separating the pathologically hopeless cases like Canetti–Goldreich–Halevi's tantrum-throwing signatures from real schemes we actually use, which we haven't identified yet. It's not the only such academic problem: collision resistance, free precomputation, etc., also have technical issues of little consequence.
$endgroup$
– Squeamish Ossifrage
yesterday
|
show 2 more comments
$begingroup$
great. thanks a lot
$endgroup$
– kiran
yesterday
2
$begingroup$
The accepted answer (from Hilder Vítor) appears to contradict you. Is it because you are dismissing the "pathological examples"?
$endgroup$
– OrangeDog
yesterday
2
$begingroup$
@OrangeDog It would seem that Hilder tacitly rejects the random oracle model altogether—which flies in the face of essentially all public-key cryptography in practice. This is a perspective taken by some academic cryptography theoreticians, but it explains why one can't find practical implementations: because practitioners are justifiably unconcerned by the contortions that Canetti–Goldreich–Halevi go through to exhibit pathological counterexamples. By the same token, one might reject SHA-3 because there's technically no formalization of its ‘collision resistance’, per se.
$endgroup$
– Squeamish Ossifrage
yesterday
$begingroup$
@OrangeDog In particular, Canetti–Goldreich–Halevi concoct a signature scheme leaks the private key on inputs of the form $(x, H(x), pi)$ where $pi$ is a valid proof that $(x, H(x))$ is in the graph of some fixed polynomial-time function ensemble, which has negligible probability when $H$ is a uniform random function so the scheme is ROM-secure, but can be exhibited easily when $H$ is drawn from any concrete family of functions so the scheme is not instantiable. In other words, it's a signature scheme that by construction throws a tantrum if you instantiate it in practice.
$endgroup$
– Squeamish Ossifrage
yesterday
1
$begingroup$
@OrangeDog The theoretical concern high in the ivory tower is that a counterexample proves that ROM security doesn't imply concrete security. The sensible inference is not that schemes with ROM security should be silently ignored. Rather, there is probably some technical criterion separating the pathologically hopeless cases like Canetti–Goldreich–Halevi's tantrum-throwing signatures from real schemes we actually use, which we haven't identified yet. It's not the only such academic problem: collision resistance, free precomputation, etc., also have technical issues of little consequence.
$endgroup$
– Squeamish Ossifrage
yesterday
$begingroup$
great. thanks a lot
$endgroup$
– kiran
yesterday
$begingroup$
great. thanks a lot
$endgroup$
– kiran
yesterday
2
2
$begingroup$
The accepted answer (from Hilder Vítor) appears to contradict you. Is it because you are dismissing the "pathological examples"?
$endgroup$
– OrangeDog
yesterday
$begingroup$
The accepted answer (from Hilder Vítor) appears to contradict you. Is it because you are dismissing the "pathological examples"?
$endgroup$
– OrangeDog
yesterday
2
2
$begingroup$
@OrangeDog It would seem that Hilder tacitly rejects the random oracle model altogether—which flies in the face of essentially all public-key cryptography in practice. This is a perspective taken by some academic cryptography theoreticians, but it explains why one can't find practical implementations: because practitioners are justifiably unconcerned by the contortions that Canetti–Goldreich–Halevi go through to exhibit pathological counterexamples. By the same token, one might reject SHA-3 because there's technically no formalization of its ‘collision resistance’, per se.
$endgroup$
– Squeamish Ossifrage
yesterday
$begingroup$
@OrangeDog It would seem that Hilder tacitly rejects the random oracle model altogether—which flies in the face of essentially all public-key cryptography in practice. This is a perspective taken by some academic cryptography theoreticians, but it explains why one can't find practical implementations: because practitioners are justifiably unconcerned by the contortions that Canetti–Goldreich–Halevi go through to exhibit pathological counterexamples. By the same token, one might reject SHA-3 because there's technically no formalization of its ‘collision resistance’, per se.
$endgroup$
– Squeamish Ossifrage
yesterday
$begingroup$
@OrangeDog In particular, Canetti–Goldreich–Halevi concoct a signature scheme leaks the private key on inputs of the form $(x, H(x), pi)$ where $pi$ is a valid proof that $(x, H(x))$ is in the graph of some fixed polynomial-time function ensemble, which has negligible probability when $H$ is a uniform random function so the scheme is ROM-secure, but can be exhibited easily when $H$ is drawn from any concrete family of functions so the scheme is not instantiable. In other words, it's a signature scheme that by construction throws a tantrum if you instantiate it in practice.
$endgroup$
– Squeamish Ossifrage
yesterday
$begingroup$
@OrangeDog In particular, Canetti–Goldreich–Halevi concoct a signature scheme leaks the private key on inputs of the form $(x, H(x), pi)$ where $pi$ is a valid proof that $(x, H(x))$ is in the graph of some fixed polynomial-time function ensemble, which has negligible probability when $H$ is a uniform random function so the scheme is ROM-secure, but can be exhibited easily when $H$ is drawn from any concrete family of functions so the scheme is not instantiable. In other words, it's a signature scheme that by construction throws a tantrum if you instantiate it in practice.
$endgroup$
– Squeamish Ossifrage
yesterday
1
1
$begingroup$
@OrangeDog The theoretical concern high in the ivory tower is that a counterexample proves that ROM security doesn't imply concrete security. The sensible inference is not that schemes with ROM security should be silently ignored. Rather, there is probably some technical criterion separating the pathologically hopeless cases like Canetti–Goldreich–Halevi's tantrum-throwing signatures from real schemes we actually use, which we haven't identified yet. It's not the only such academic problem: collision resistance, free precomputation, etc., also have technical issues of little consequence.
$endgroup$
– Squeamish Ossifrage
yesterday
$begingroup$
@OrangeDog The theoretical concern high in the ivory tower is that a counterexample proves that ROM security doesn't imply concrete security. The sensible inference is not that schemes with ROM security should be silently ignored. Rather, there is probably some technical criterion separating the pathologically hopeless cases like Canetti–Goldreich–Halevi's tantrum-throwing signatures from real schemes we actually use, which we haven't identified yet. It's not the only such academic problem: collision resistance, free precomputation, etc., also have technical issues of little consequence.
$endgroup$
– Squeamish Ossifrage
yesterday
|
show 2 more comments
$begingroup$
This is secure for practically all hybrid asymmetric encryption algorithms, like ECIES or RSA-KEM. However it violates the security assumptions of the standard model, so you have to resort to the random oracle model.
I would avoid overly complicated designs, like those from the paper Hilder mentions, just for the sake of a standard model security proof.
New contributor
$endgroup$
add a comment |
$begingroup$
This is secure for practically all hybrid asymmetric encryption algorithms, like ECIES or RSA-KEM. However it violates the security assumptions of the standard model, so you have to resort to the random oracle model.
I would avoid overly complicated designs, like those from the paper Hilder mentions, just for the sake of a standard model security proof.
New contributor
$endgroup$
add a comment |
$begingroup$
This is secure for practically all hybrid asymmetric encryption algorithms, like ECIES or RSA-KEM. However it violates the security assumptions of the standard model, so you have to resort to the random oracle model.
I would avoid overly complicated designs, like those from the paper Hilder mentions, just for the sake of a standard model security proof.
New contributor
$endgroup$
This is secure for practically all hybrid asymmetric encryption algorithms, like ECIES or RSA-KEM. However it violates the security assumptions of the standard model, so you have to resort to the random oracle model.
I would avoid overly complicated designs, like those from the paper Hilder mentions, just for the sake of a standard model security proof.
New contributor
New contributor
answered yesterday
user66919user66919
311
311
New contributor
New contributor
add a comment |
add a comment |
kiran is a new contributor. Be nice, and check out our Code of Conduct.
kiran is a new contributor. Be nice, and check out our Code of Conduct.
kiran is a new contributor. Be nice, and check out our Code of Conduct.
kiran is a new contributor. Be nice, and check out our Code of Conduct.
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%2f68270%2fis-it-possible-to-build-a-cpa-secure-encryption-scheme-which-remains-secure-even%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
$begingroup$
We can also assume that there exists a deterministic poly time algorithm T that on input sk outputs pk.
$endgroup$
– kiran
yesterday