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.
Let Σ be a public-key encryption scheme. Then Σ has one-time secrecyif ℒΣpk-ots-L ≋ ℒΣpk-ots-R where:
Let Σ be a public-key encryption scheme. If Σ has one-time secrecy, then Σ is CPA-secure.
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 hth 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
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 hth call to challenge as a special one to be handled by ℒpk-ots-*. This allows us to change the hth encryption from using mL to mR.