As a rule, public-key encryption schemes are much more computationally expensive than symmetric-key schemes. Taking ElGamal as a representative example, computing gb 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:
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 (Construction 15.8) is also a CPA-secure public-key encryption scheme.
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.
As usual, our goal is to show that ℒΣhybpk-cpa-L ≋ ℒΣhybhybpk-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 mL with mR. Since mL is only used as a plaintext for Σsym, it is tempting to simply apply the one-time-secrecy property of Σsym to argue that mL can be replaced with mR. Unfortunately, this cannot work because the 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 mL 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 mR instead of mL. 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 ℒ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.