# 15.4: Hybrid Encryption

- Page ID
- 7414

As a rule, public-key encryption schemes are much more computationally expensive than symmetric-key schemes. Taking ElGamal as a representative example, computing *g ^{b}* in a cryptographically secure cyclic group is considerably more expensive than one evaluation of AES. As the plaintext data increases in length, the difference in cost between public-key and symmetric-key techniques only gets worse.

A clever way to minimize the cost of public-key cryptography is to use a method called **hybrid encryption**. The idea is to use the expensive public-key scheme to encrypt a *temporary key* for a symmetric-key scheme. Then use the temporary key to (cheaply) encrypt the large plaintext data.

To decrypt, one can use the decryption key of the public-key scheme to obtain the temporary key. Then the temporary key can be used to decrypt the main payload.

**Construction 15.8: Hybrid Enc**

*Let* Σ* _{pub} be a public-key encryption scheme, and let* Σ

*Σ*

_{sym}be a symmetric-key encryption scheme, where*.? ⊆ Σ*

_{sym}*.? —*

_{pub}*that is, the public-key scheme is capable of encrypting keys of the symmetric-key scheme.*

*Then we define Σ _{hyb} to be the following construction:*

Importantly, the message space of the hybrid encryption scheme is the message space of the symmetric-key scheme (think of this as involving very long plaintexts), but encryption and decryption involves expensive public-key operations only on a small temporary key (think of this as a very short string).

The correctness of the scheme can be verified via:

To show that hybrid encryption is a valid way to encrypt data, we prove that it provides CPA security, when its two components have appropriate security properties:

**Claim 15.9**

*If* Σ_{sym} is a one-time-secret symmetric-key encryption scheme *and*Σ* _{pub} is a CPA-secure public-key encryption scheme, then the hybrid scheme* Σ

_{hyb}(__) is also a CPA-secure public-key encryption scheme.____Construction 15.8__Note that Σ_{sym} does not even need to be CPA-secure. Intuitively, one-time secrecy suffices because each temporary key *tk* is used only once to encrypt just a single plaintext.

**Proof**

As usual, our goal is to show that ℒ^{Σhyb}_{pk-cpa-L} ≋ ℒ^{Σhyb}_{hybpk-cpa-R}, which we do in a standard sequence of hybrids:

The starting point is ℒ_{pk-cpa-L}, shown here with the details of Σ_{hyb} filled in.

Our only goal is to somehow replace *m _{L}* with

*m*. Since

_{R}*m*is only used as a plaintext for Σ

_{L}_{sym}, it is tempting to simply apply the one-time-secrecy property of Σ

_{sym}to argue that

*m*can be replaced with

_{L}*m*. Unfortunately, this cannot work because the

_{R}*key*used for that ciphertext is

*tk*, which is used elsewhere. In particular, it is used as an argument to Σ

_{pub}.Enc

However, using *tk* as the plaintext argument to Σ_{pub}.Enc should *hide tk* to the calling program, if Σ_{pub} is CPA-secure. That is, the Σ_{pub} encryption of *tk* should look like a Σ_{pub} encryption of some unrelated dummy value. More formally, we can factor out the call to Σ_{pub}.Enc in terms of the ℒ_{pk-cpa-L} library, as follows:

Here we have changed the variable names of the arguments of CHALLENGE’ to avoid unnecessary confusion. Note also that CHALLENGE now chooses *two* temporary keys — one which is actually used to encrypt *m _{L}* and one which is not used anywhere. This is because syntactically we must have two arguments to pass into CHALLENGE’.

Now imagine replacing ℒ_{pk-cpa-L} with ℒ_{k-cpa-R} and then inlining subroutine calls. The result is:

At this point, it does now work to factor out the call to Σ_{sym}.Enc in terms of the ℒ_{ots-L} library. This is because the key *tk* is not used anywhere else in the library. The result of factoring out in this way is:

At this point, we can replace ℒ_{ots-L} with ℒ_{ots-R}. After this change the Σ_{sym}-ciphertext encrypts *m _{R}* instead of

*m*. This is the “half-way point” of the proof, and the rest of the steps are a mirror image of what has come before. In summary: we inline ℒ

_{L}_{ots-R}, then we apply CPA security to replace the Σ

_{pub}-encryption of

*tk’*with

*tk*. The result is exactly ℒ

_{pk-cpa-R}, as desired.