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

- Page ID
- 7412

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

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

__Definition 2.5__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 secrecyif* ℒ

^{Σ}

_{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}