# Chapter 15: Public-Key Encryption

### Return to Table of Contents

So far, the encryption schemes that we’ve seen are **symmetric-key** schemes. The same key is used to encrypt and decrypt. In this chapter we introduce **public-key** (sometimes called *asymmetric*) encryption schemes, which use different keys for encryption and decryption. The idea is that the encryption key can be made *public*, so that anyone can send an encryption to the owner of that key, even if the two users have never spoken before and have no shared secrets. The decryption key is private, so that only the designated owner can decrypt.

We modify the syntax of an encryption scheme in the following way. A public-key encryption scheme consists of the following three algorithms:

KeyGen: Outputs a *pair* (*pk,sk*) where *pk* is a public key and *sk* is a private/secret key.

Enc: Takes the public key *pk* and a plaintext *m* as input, and outputs a ciphertext *c*.

Dec: Takes the secret key *sk* and a ciphertext *c* as input, and outputs a plaintext *m*.

We modify the correctness condition similarly. A public-key encryption scheme satisfies *correctness* if, for all *m* ∈ ? and all (*pk,sk*) ← KeyGen, we have Dec(*sk*,Enc(*pk,m*)) = *m* (with probability 1 over the randomness of Enc).

**15.1: Security Definitions**

We now modify the definition of CPA security to fit the setting of public-key encryption. As before, the adversary calls a CHALLENGE subroutine with two plaintexts — the difference between the two libraries is which plaintext is actually encrypted. Of course, the encryption operation now takes the public key.

Then the biggest change is that we would like to make the public key *public*. In other words, the calling program should have a way to learn the public key (otherwise the library cannot model a situation where the public key is known to the adversary). To do this, we simply add another subroutine that returns the public key.

### Definition 15.1

*Let* Σ *be a public-key encryption scheme. Then* Σ *is secure against chosen-plaintext attacks (CPA secure) if* ℒ

^{Σ}

_{pk-cpa-L}≋ ℒ

^{Σ}

_{pk-cpa-R}, where:

#### Pseudorandom Ciphertexts

We can modify/adapt the definition of pseudorandom ciphertexts to public-key encryption in a similar way:

### Definition 15.2

*Let* Σ *be a public-key encryption scheme. Then* Σ *has pseudorandom ciphertexts in the presence of chosen-plaintext attacks (CPA$ security) if* ℒ

^{Σ}

_{pk-cpa$-real}≋ ℒ

^{Σ}

_{pk-cpa$-rand, where:}

As in the symmetric-key setting, CPA$ security (for public-key encryption) implies CPA security:

### Claim 15.3

*Let* Σ *be a public-key encryption scheme. If* Σ *has CPA$ security, then* Σ *has CPA security*

The proof is extremely similar to the proof of the analogous statement for symmetric-key encryption (Theorem 8.3), and is left as an exercise.

**15.2: One-time Security Implies Many-Time Security**

So far, everything about public-key encryption has been directly analogous to what we’ve seen about symmetric-key encryption. We now discuss a peculiar property that is different between the two settings.

In symmetric-key encryption, we saw examples of encryption schemes that are secure when the adversary sees only one ciphertext, but insecure when the adversary sees more ciphertexts. One-time pad is the standard example of such an encryption scheme.

Surprisingly, if a *public-key* encryption scheme is secure when the adversary sees just one ciphertext, then it is also secure for many ciphertexts! In short, there is no public-key one-time pad that is weaker than full-edged public-key encryption — there is public-key encryption or nothing.

To show this property formally, we first adapt the definition of one time secrecy (Definition 2.5) to the public-key setting. There is one small but important technical subtlety: in Definition 2.5 the encryption key is chosen at the last possible moment in the body of CHALLENGE. This ensures that the key is local to this scope, and therefore each value of the key is only used to encrypt one plaintext.

In the public-key setting, however, it turns out to be important to allow the adversary to see the public key before deciding which plaintexts to encrypt. (This concern is not present in the symmetric-key setting precisely because there is nothing public upon which the adversary’s choice of plaintexts can depend.) For that reason, in the public-key setting we must sample the keys at initialization time so that the adversary can obtain the public key via GETPK. To ensure that the key is used to encrypt only one plaintext, we add a counter and a guard condition to CHALLENGE, so that it only responds once with a ciphertext.

### Claim 15.4

*Let* Σ * be a public-key encryption scheme. Then* Σ *has one-time secrecy if* ℒ

^{Σ}

_{pk-ots-L}≋ ℒ

^{Σ}

_{pk-ots-R}

*where:*

### Claim 15.5

*Let* Σ *be a public-key encryption scheme. If* Σ *has one-time secrecy, then* Σ *is CPA-secure.*

#### Proof

Suppose ℒ^{Σ}_{pk-ots-L} ≋ ℒ^{Σ}_{pk-ots-R}. Our goal is to show that ℒ^{Σ}_{pk-cpa-L} ≋ ℒ^{Σ}_{pk-cpa-R}. The proof centers around the following hybrid library ℒ_{hyb-h}, which is designed to be linked to either ℒ_{pk-ots-L} or ℒ_{pk-ots-R}:

Here the value *h* is an unspecified value that will be a hard-coded constant, and CHALLENGE’ (called by the “elsif” branch) and GETPK refer to the subroutine in ℒ_{pk-ots-*}. Note that ℒ_{hyb-h} is designed so that it only makes one call to CHALLENGE’ — in particular, only when its OWN CHALLENGE subroutine is called for the *h*^{th} time.

We now make a few observations:

ℒ_{hyb-1} ◊ ℒ_{pk-ots-L} ≡ ℒ_{pk-cpa-L}:

In both libraries, every call to CHALLENGE encrypts the left plaintext. In particular, the first call to CHALLENGE in ℒ_{hyb-1} triggers the “elsif” branch, so the challenge is routed to ℒ_{pk-ots-L}, which encrypts the left plaintext. In all other calls to CHALLENGE, the “else” branch is triggered and the left plaintext is encrypted explicitly.

ℒ_{hyb-h} ◊ ℒ_{pks-ots-L} ≡ ℒ_{hyb-(h + 1)} ◊ ℒ_{pks-ots-R},

for all *h*. In both of these libraries, the first *h* calls to CHALLENGE encrypt the left plaintext, and all subsequent calls encrypt the right plaintext.

ℒ_{hyb-h} ◊ ℒ_{pks-ots-L} ≋ ℒ_{hyb-h} ◊ ℒ_{pks-ots-R},

for all *h*. This simply follows from the fact that ℒ_{pks-ots-L} ≋ ℒ_{pks-ots-R}.

ℒ_{hyb-q} ◊ ℒ_{pks-ots-R} ≡ ℒ_{pk-cpa-R},

where *q* is the number of times the calling program calls CHALLENGE. In particular, every call to CHALLENGE encrypts the right plaintext.

Putting everything together, we have that:

ℒ_{pk-cpa-L} ≡ ℒ_{hyb-1} ◊ ℒ_{pk-ots-L} ≋ ℒ_{hyb-1} ◊ ℒ_{pk-ots-R}

≡ ℒ_{hyb-2} ◊ ℒ_{pk-ots-L} ≋ ℒ_{hyb-2} ◊ ℒ_{pk-ots-R}

…

≡ ℒ_{hyb-q} ◊ ℒ_{pk-ots-L} ≋ ℒ_{hyb-q} ◊ ℒ_{pk-ots-R}

≡ ℒ_{pk-cpa-R},

and so ℒ_{pk-cpa-L} ≋ ℒ_{pk-cpa-R}.

The reason this proof goes through for public-key encryption but not symmetric-key encryption is that *anyone can encrypt* in a public-key scheme. In a symmetric-key scheme, it is not possible to generate encryptions without the key. But in a public-key scheme, the encryption key is public.

In more detail, the ℒ_{hyb-h} library can indeed obtain *pk* from ℒ_{pk-ots-*}. It therefore has enough information to perform the encryptions for all calls to challenge. Indeed, you can think of ℒ_{hyb-0} as doing everything that ℒ_{pk-cpa-L} does, even though it doesn’t know the secret key. We let ℒ_{hyb-h} designate the *h*^{th} call to challenge as a special one to be handled by ℒ_{pk-ots-*}. This allows us to change the *h*^{th} encryption from using *m _{L}* to

*m*.

_{R}

**15.3: ElGamal Encryption**

ElGamal encryption is a public-key encryption scheme that is based on DHKA

### construction 15.6: ElGamal

*The public parameters are a choice of cyclic group* ? *with n elements and generator g.*

The scheme satisfies correctness, since for all *M*:

#### Security

Imagine an adversary who is interested in attacking an ElGamal scheme. This adversary sees the public key *A* = *g ^{a}* and a ciphertext (

*g*) go by. Intuitively, the Decisional Diffie-Hellman assumption says that the value

^{b},M g^{ab}*g*looks random, even to someone who has seen

^{ab}*g*and

^{a}*g*. Thus, the message

^{b}*M*is masked with a pseudorandom group element — as we’ve seen before, this is a lot like masking the message with a random pad as in one-time pad. The only change here is that instead of the XOR operation, we are using the group operation in ?.

More formally, we can prove the security of ElGamal under the DDH assumption:

### Claim 15.7

*If the DDH assumption in group* ? *is true, then ElGamal in group* ? *is CPA$-secure.*

#### Proof

It suffices to show that ElGamal has pseudorandom ciphertexts when the calling program sees only a single ciphertext. In other words, we will show that ℒ_{pk-ots$-real} ≋ ℒ_{pk-ots$-rand}, where these libraries are the ℒ_{pk-cpa$-*} libraries from Definition 15.2 but with the singleciphertext restriction used in Definition 15.4. It is left as an exercise to show that ℒ_{pk-ots$-real} ≋ ℒ_{pk-ots$-rand} implies CPA$ security (which in turn implies CPA security); the proof is very similar to that of Claim 15.5.

The sequence of hybrid libraries is given below:

The starting point is the ℒ_{pk-ots$-real} library, shown here with the details of ElGamal filled in.

The main body of QUERY computes some intermediate values *B* and *A ^{b}* . But since those lines are only reachable one time, it does not change anything to pre-compute them at initialization time.

We can factor out the generation of *A*,*B*,*C* in terms of the ℒ_{dh-real} library from the Decisional Diffie-Hellman security definition (Definition 14.5).

Applying the security of DDH, we can replace ℒ_{dh-real} with ℒ_{dh-rand}.

The call to DHQUERY has been inlined.

As before, since the main body of QUERY is only reachable once, we can move the choice of *B* and *C* into that subroutine instead of at initialization time.

When *b* is sampled uniformly from ℤ_{n}, the expression *B* = *g ^{b}* is a uniformly distributed element of ?. Also recall that when

*C*is a uniformly distributed element of ?, then

*M*·

*C*is uniformly distributed — this is analogous to the one-time pad property (see Exercise 2.1). Applying this change gives the library to the left.

In the final hybrid, the response to QUERY is a pair of uniformly distributed group elements (*B,X*). Hence that library is exactly ℒ_{pk-ots$-rand, as desired.}

** **

## 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* Σ* _{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}(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.

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

**Exercises**

15.1: Prove Claim 15.3

15.2: Show that a 2-message key-agreement protocol exists if and only if CPA-secure public-key encryption exists.

In other words, show how to construct a CPA-secure encryption scheme from any 2- message KA protocol, and vice-versa. Prove the security of your constructions.

15.3: (a). Suppose you are given an ElGamal encryption of an unknown plaintext *M* ∈ ?. Show how to construct a different ciphertext that also decrypts to the same *M*.

(b). Suppose you are given two ElGamal encryptions, of unknown plaintexts *M*_{1},*M*_{2} ∈ ?. Show how to construct a ciphertext that decrypts to their product *M*_{1} · *M*_{2}.

15.4: Suppose you obtain two ElGamal ciphertexts (*B*_{1},*C*_{1}), (*B*_{2},*C*_{2}) that encrypt unknown plaintexts *M*_{1} and *M*_{2}. Suppose you also know the public key *A* and cyclic group generator *g*.

(a). What information can you infer about *M*_{1} and *M*_{2} if you observe that *B*_{1} = *B*_{2}?

(b). What information can you infer about *M*_{1} and *M*_{2} if you observe that *B*_{1} = g · *B*_{2}?

(c). What information can you infer about *M*_{1} and *M*_{2} if you observe that *B*_{1} = (*B*_{2})^{2}?