Cfrgtkky

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.

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 $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} 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.}

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.