# Is it possible to build a CPA-secure encryption scheme which remains secure even when the encryption of secret key is given?

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, $$\mathit{Enc}_{\mathit{pk}}(\mathit{sk})$$ is given to the attacker, where $$(\mathit{sk},\mathit{pk})$$ is the key pair.

• We can also assume that there exists a deterministic poly time algorithm T that on input sk outputs pk. – kiran Mar 25 at 15:04

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.

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:

1. (KEM) Generate a uniform random $$k$$ and encapsulation $$y$$ using $$\mathit{pk}$$.

Examples:

• RSA-KEM: $$\mathit{pk} = 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} \pmod{\lambda(n)}$$.

• RSA-OAEP KEM: $$\mathit{pk} = 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 $$\lfloor\log_2 n\rfloor$$-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} \pmod{\lambda(n)}$$, and then solve for $$k$$.

• DH-based KEM: $$\mathit{pk} = 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$$.

2. (DEM) Use $$k$$ as a one-time key for a one-time authenticated cipher $$\operatorname{AE}$$ to encrypt the message $$m$$ as $$c = \operatorname{AE}_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.

3. 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 $$\mathit{sk}$$, so there is no problem with the symmetric encryption $$\operatorname{AE}_k(\mathit{sk})$$ 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_{\mathit{pk}}(r) \mathbin\| (H(r) \oplus m)$$ for uniform random $$r$$ has it if $$E_{\mathit{pk}}$$ 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.

• The accepted answer (from Hilder Vítor) appears to contradict you. Is it because you are dismissing the "pathological examples"? – Stop Harming Monica Mar 25 at 18:24
• @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. – Squeamish Ossifrage Mar 25 at 22:18
• @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. – Squeamish Ossifrage Mar 25 at 22:23
• @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. – Squeamish Ossifrage Mar 25 at 22:36
• Actually what you are refering to is a hybrid encryption scheme, however I am only looking for a public key encryption scheme. – kiran Mar 26 at 14:30

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.