# Authenticate encrypted seed for KEM + AEAD hybrid cryptosystem

Say I want to encrypt something using RSA / KEM and an authenticated cipher. I encrypt using the following scheme:

1. generate random seed z using n - 1 bits - where n is the size of the modulus N
2. interpret the seed z as unsigned number and encrypt using the public key e: w = RSA(e, z)
3. derive a session key and IV using s = KDF(z, "skey") and iv = KDF(z, "iv")
4. encrypt the plaintext message m' using (c, t) = AEAD(s, iv, ad, m), where t is the authentication tag and ad is (additional) authenticated data
5. output w | c | t

Would it be advantageous to include the value of w - the encrypted key seed - in the authenticated data ad?

• I've left the decryption scheme to your imagination :) – Maarten Bodewes Sep 8 '15 at 21:10
• As this uses the standard RSA-KEM and a CCA secure private key encryption scheme in a standard composition (for which security proofs are available) I'd say the answer will be: "You don't have to include the encrypted seed in the AD, the scheme will be provably secure without doing this." Will it provide any advantages? maybe. Will it break anything? unlikely but possible. Result: You may do it if you see any advantages. This isn't an answer as I don't how the security proofs will behave with this modification – SEJPM Sep 8 '15 at 21:35
• @SEJPM That's my feeling as well. I'm slightly worried about meet-in-the-middle attacks though, so I'm just posting this question as a safeguard in case I'm overlooking something. – Maarten Bodewes Sep 8 '15 at 21:38
• This is CCA-secure in the random oracle model (assuming the KDF behaves like a random oracle). So there's no need to include $w$. In general, I am in favor of making it as simple as possible. – Yehuda Lindell Sep 9 '15 at 5:53
• Isn't conventional RSA-KEM already CCA-secure in the random oracle model? – cygnusv Sep 9 '15 at 8:54

It probably doesn't hurt to include the encapsulation as additional data for the AEAD, but there is no need. The generic KEM/DEM composition,

\begin{align} &(C_0, k) \leftarrow \operatorname{KEM}_{\mathit{pk}}() \\ &C_1 \leftarrow \operatorname{DEM}_k(M) \\ &\operatorname{return} C_0\mathbin\|C_1, \end{align}

provides adequate security by the standard theorems, e.g. Cramer–Shoup 2001, Theorem 5 on p. 41.

You can safely separate the concerns of

1. generating the encapsulation $$C_0$$ and the key $$k$$ with RSA, and
2. one-time authenticated encryption under $$k$$,

as separate subroutines that communicate only $$k$$.

See Shoup's ISO proposal for more practical details of composition and instantiation with less math.

Incidentally, it is also unnecessary to generate an IV, since the key is used only once: you can safely use an IV/nonce of zero for the AEAD as a DEM.