15.1: Security Definitions

Last updated
Save as PDF

Page ID: 86472

$ \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}}$

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 $\Sigma$ be a public-key encryption scheme. Then $\Sigma$ is secure against chosen-plaintext at-tacks (CPA secure) if $\mathcal{L}_{\mathrm{pk} \text {-cpa-L}}^{\Sigma} \approx \mathcal{L}_{\mathrm{pk} \text {-cpa-R}}^{\Sigma}$, where:

Pseudorandom Ciphertexts

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

Definition $15.2$

Let $\Sigma$ be a public-key encryption scheme. Then $\Sigma$ has pseudorandom ciphertexts in the presence of chosen-plaintext attacks (CPA$ security) if $\mathcal{L}_{\mathrm{pk} \text {-cpa\$-real }}^{\Sigma} \approx \mathcal{L}_{\mathrm{pk} \text {-cpa\$-rand }}^{\Sigma}$, where:

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

Claim $15.3$

Let $\Sigma$ be a public-key encryption scheme. If $\sum$ has $C P A \$$ security, then $\Sigma$ has CPA security.

The proof is extremely similar to the proof of the analogous statement for symmetrickey encryption (Theorem 7.3), and is left as an exercise.

Search

Definition \(15.2\)

Claim \(15.3\)

Definition \(15.1\)

Pseudorandom Ciphertexts

Definition \(15.2\)

Claim \(15.3\)