# 15.4: Hybrid Encryption

$$\newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} }$$ $$\newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}}$$$$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}[1]{\| #1 \|}$$ $$\newcommand{\inner}[2]{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}[1]{\| #1 \|}$$ $$\newcommand{\inner}[2]{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$$$\newcommand{\AA}{\unicode[.8,0]{x212B}}$$

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:

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:

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:

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:

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.

This page titled 15.4: Hybrid Encryption is shared under a CC BY-NC-SA 4.0 license and was authored, remixed, and/or curated by Mike Rosulek (Open Oregon State) .