Skip to main content
Engineering LibreTexts

15.4: Hybrid Encryption

  • Page ID
    86475
  • \( \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:

    fig-ch01_patchfile_01.jpg
    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:

    fig-ch01_patchfile_01.jpg
    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:

    fig-ch01_patchfile_01.jpg
    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:

    fig-ch01_patchfile_01.jpg
    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:

    fig-ch01_patchfile_01.jpg
    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.


    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) .

    • Was this article helpful?