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^b,M g^ab) go by. Intuitively, the Decisional Diffie-Hellman assumption says that the value g^ab looks random, even to someone who has seen g^a and g^b. Thus, the message 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 ℒΣ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 m_L with m_R. Since m_L is only used as a plaintext for Σ_sym, it is tempting to simply apply the one-time-secrecy property of Σ_sym to argue that m_L can be replaced with m_R. 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 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_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 ℒ_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₁,M₂ ∈ ?. Show how to construct a ciphertext that decrypts to their product M₁ · M₂.

15.4: Suppose you obtain two ElGamal ciphertexts (B₁,C₁), (B₂,C₂) that encrypt unknown plaintexts M₁ and M₂. Suppose you also know the public key A and cyclic group generator g.

(a). What information can you infer about M₁ and M₂ if you observe that B₁ = B₂?

(b). What information can you infer about M₁ and M₂ if you observe that B₁ = g · B₂?

(c). What information can you infer about M₁ and M₂ if you observe that B₁ = (B₂)²?