15.4: Hybrid Encryption

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 \(\Sigma_{p u b}\) be a public-key encryption scheme, and let \(\Sigma_{\text {sym }}\) be a symmetric-key encryption scheme, where \(\Sigma_{\text {sym }} . \mathcal{K} \subseteq \Sigma_{p u b} \cdot \mathcal{M}-\) that is, the public-key scheme is capable of encrypting keys of the symmetric-key scheme.

Then we define \(\Sigma_{h y b}\) to be the following construction:

Figure \(\PageIndex{1}\): Copy and Paste Caption here. (Copyright; author via source)

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:

\[\begin{aligned} \operatorname{Dec}(s k, \operatorname{Enc}(p k, m)) &=\operatorname{Dec}\left(s k,\left(\Sigma_{\text {pub }} \cdot \operatorname{Enc}(p k, t k), \Sigma_{\text {sym }} \cdot \operatorname{Enc}(t k, m)\right)\right) \\ &=\Sigma_{\text {sym }} \cdot \operatorname{Dec}\left(\Sigma_{\text {pub }} \cdot \operatorname{Dec}\left(s k, \Sigma_{\text {pub }} \cdot \operatorname{Enc}(p k, t k)\right), \Sigma_{\text {sym }} \cdot \operatorname{Enc}(t k, m)\right) \\ &=\Sigma_{\text {sym }} \cdot \operatorname{Dec}\left(t k, \Sigma_{\text {sym }} \cdot \operatorname{Enc}(t k, m)\right) \\ &=m \end{aligned}\]

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 \(\Sigma_{s y m}\) is a one-time-secret symmetric-key encryption scheme and \(\Sigma_{\text {pub }}\) is a CPA-secure publickey encryption scheme, then the hybrid scheme \(\Sigma_{\text {hyb }}\) (Construction 15.8) is also a CPA-secure public-key encryption scheme.

Note that \(\Sigma_{\text {sym }}\) does not even need to be CPA-secure. Intuitively, one-time secrecy suffices because each temporary key \(t k\) is used only once to encrypt just a single plaintext.

Proof

As usual, our goal is to show that \(\mathcal{L}_{\mathrm{pk}-\mathrm{cpa}-\mathrm{L}}^{\Sigma_{\mathrm{hyb}}} \approx \mathcal{L}_{\mathrm{pk} \text {-cpa-R }}^{\Sigma_{\mathrm{hyb}}}\), which we do in a standard sequence of hybrids:

Figure \(\PageIndex{1}\): Copy and Paste Caption here. (Copyright; author via source)

The starting point is \(\mathcal{L}_{\mathrm{pk}-\mathrm{cpa}-\mathrm{L}}\), shown here with the details of \(\sum_{\text {hyb }}\) filled in. Our only goal is to somehow replace \(m_{L}\) with \(m_{R}\). Since \(m_{L}\) is only used as a plaintext for \(\Sigma_{\text {sym }}\), it is tempting to simply apply the one-time-secrecy property of \(\Sigma_{\text {sym }}\) to argue that \(m_{L}\) can be replaced with \(m_{R}\). Unfortunately, this cannot work because the key used for that ciphertext is \(t k\), which is used elsewhere. In particular, it is used as an argument to \(\Sigma_{\text {pub. }}\).Enc.

However, using \(t k\) as the plaintext argument to \(\Sigma_{\text {pub. }}\).Enc should hide \(t k\) to the calling program, if \(\Sigma_{\text {pub }}\) is CPA-secure. That is, the \(\Sigma_{\text {pub }}\)-encryption of \(t k\) should look like a \(\Sigma_{\text {pub- }}{ }^{-}\) encryption of some unrelated dummy value. More formally, we can factor out the call to \(\Sigma_{\text {pub. }}\).Enc in terms of the \(\mathcal{L}_{\mathrm{pk}-\mathrm{cpa}-\mathrm{L}}\) library, as follows:

Figure \(\PageIndex{1}\): Copy and Paste Caption here. (Copyright; author via source)

Here we have changed the variable names of the arguments of CHALLENGE \({ }^{\prime}\) 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 \(\mathcal{L}_{\mathrm{pk}-\mathrm{cpa}-\mathrm{L}}\) with \(\mathcal{L}_{\mathrm{pk} \text {-cpa-R }}\) and then inlining subroutine calls. The result is:

Figure \(\PageIndex{1}\): Copy and Paste Caption here. (Copyright; author via source)

At this point, it does now work to factor out the call to \(\Sigma_{\text {sym. Enc in terms of the }} \mathcal{L}_{\text {ots-L }}\) library. This is because the key \(t k\) is not used anywhere else in the library. The result of factoring out in this way is:

Figure \(\PageIndex{1}\): Copy and Paste Caption here. (Copyright; author via source)

At this point,  we can replace \(\mathcal{L}_{\text {ots-L}}\) with \(\mathcal{L}_{\text {ots-R}}\). After this change the \(\Sigma _{\textrm{sym}}\)-ciphertext encrypts \(m_{R}\) instead of \(m_{L}\). 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 \(\mathcal{L}_{\text {ots-R }}\), then we apply CPA security to replace the \(\Sigma_{\text {pub }}\)-encryption of \(t k^{\prime}\) with \(t k\). The result is exactly \(\mathcal{L}_{\text {pk-cpa-R}}\), as desired.