15.2: One-Time Security Implies Many-Time Security

Last updated
Save as PDF

Page ID: 86473

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

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-fledged 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.6) to the public-key setting. There is one small but important technical subtlety: in Definition \(2.6\) 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.

Definition \(15.4\)

Let \(\Sigma\) be a public-key encryption scheme. Then \(\Sigma\) has one-time secrecy if \(\mathcal{L}_{\mathrm{pk} \text {-ots-L }}^{\Sigma} \approx\) \(\mathcal{L}_{\text {pk-ots-R }}^{\Sigma}\), where:

Claim \(15.5\)

Let \(\Sigma\) be a public-key encryption scheme. If \(\Sigma\) has one-time secrecy, then \(\Sigma\) is \(C P A\)-secure.

Proof

Suppose \(\mathcal{L}_{p k-o t s-L}^{\Sigma} \approx \mathcal{L}_{\text {pk-ots-R. }}^{\Sigma}\) Our goal is to show that \(\mathcal{L}_{\text {pk-cpa-L }}^{\Sigma} \approx \mathcal{L}_{\text {pk-cpa-R. }}^{\Sigma}\) The proof centers around the following hybrid library \(\mathcal{L}_{\text {hyb- } h}\), which is designed to be linked to either \(\mathcal{L}_{\mathrm{pk} \text {-ots-L }}\) or \(\mathcal{L}_{\mathrm{pk} \text {-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 \(\mathcal{L}_{\text {pk-ots- } \star \text {. }}\). Note that \(\mathcal{L}_{\mathrm{hyb}-h}\) is designed so that it only makes one call to CHALLENGE \({ }^{\prime}-\) in particular, only when its own CHALLENGE subroutine is called for the \(h^{\text {th }}\) time.

We now make a few observations:

\(\mathcal{L}_{\text {hyb-1 }} \diamond \mathcal{L}_{\text {pk-ots-L }} \equiv \mathcal{L}_{\text {pk-cpa-L }}:\),	In both libraries, every call to CHALLENGE encrypts the left plaintext. In particular, the first call to CHALLENGE in \(\mathcal{L}_{\text {hyb-1 }}\) triggers the "elsif" branch, so the challenge is routed to \(\mathcal{L}_{\text {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.
\(\mathcal{L}_{\text {hyb- } h} \diamond \mathcal{L}_{\text {pk-ots-R }} \equiv \mathcal{L}_{\text {hyb- }(h+1)} \diamond \mathcal{L}_{\text {pk-ots-L, for all }} h\),	for all \(h\). In both of these libraries, the first \(h\) calls to CHALLENGE encrypt the right plaintext, and all subsequent calls encrypt the left plaintext.
\(\mathcal{L}_{\text {hyb- } h} \diamond \mathcal{L}_{\text {pk-ots-L }} \approx \mathcal{L}_{\text {hyb- } h} \diamond \mathcal{L}_{\text {pk-ots-R }}\),	for all \(h\). This simply follows from the fact that \(\mathcal{L}_{\mathrm{pk}-\mathrm{ots}-\mathrm{L}} \approx \mathcal{L}_{\mathrm{pk}-\mathrm{ots}-\mathrm{R}}\)
\(\mathcal{L}_{\text {hyb- } q} \diamond \mathcal{L}_{\mathrm{pk}-\text { ots-R }} \equiv \mathcal{L}_{\mathrm{pk} \text {-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:

\[\begin{aligned} \mathcal{L}_{\text {pk-cpa-L }} & \equiv \mathcal{L}_{\text {hyb-1 }} \diamond \mathcal{L}_{\text {pk-ots-L }} \approx \mathcal{L}_{\text {hyb-1 }} \diamond \mathcal{L}_{\text {pk-ots-R }} \\ & \equiv \mathcal{L}_{\text {hyb-2 }} \diamond \mathcal{L}_{\text {pk-ots-L }} \approx \mathcal{L}_{\text {hyb-2 }} \diamond \mathcal{L}_{\text {pk-ots-R }} \end{aligned}\] \[\begin{aligned} &\equiv \mathcal{L}_{\text {hyb- } q} \diamond \mathcal{L}_{\text {pk-ots-L }} \approx \mathcal{L}_{\text {hyb- } q} \diamond \mathcal{L}_{\text {pk-ots-R }} \\ &\equiv \mathcal{L}_{\text {pk-cpa-R }} \end{aligned}\] and so \(\mathcal{L}_{\mathrm{pk}-\mathrm{cpa}-\mathrm{L}} \approx \mathcal{L}_{\mathrm{pk}-\mathrm{cpa}-\mathrm{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 \(\mathcal{L}_{\text {hyb-h}}\) library can indeed obtain \(pk\) from \(\mathcal{L}_{\text {pk-ots-}\star}\). It therefore has enough information to perform the encryptions for all calls to CHALLENGE. Indeed, you can think of \(\mathcal{L}_{\text {hyb-0 }}\) as doing everything that \(\mathcal{L}_{\text {pk-cpa-L }}\) does, even though it doesn’t know the secret key. We let \(\mathcal{L}_{\text {hyb- } h}\) designate the \(h^{\text {th }}\) call to CHALLENGE as a special one to be handled by \(\mathcal{L}_{\text {pk-ots-}\star}\).This allow us to change the \(h^{\text {th}}\) encryption from using \(m_L\) to \(m_R\).