9.4☆: A Simple CCA-Secure Scheme

Last updated
Save as PDF

Page ID: 86430

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

Recall the definition of a strong pseudorandom permutation (PRP) (Definition 6.13). A strong PRP is one that is indistinguishable from a randomly chosen permutation, even to an adversary that can make both forward (i.e., to $F$ ) and reverse (i.e., to $F^{-1}$ ) queries.

This concept has some similarity to the definition of CCA security, in which the adversary can make queries to both Enc and its inverse Dec. Indeed, a strong PRP can be used to construct a CCA-secure encryption scheme in a natural way:

Construction $9.3$

Let $F$ be a pseudorandom permutation with block length blen $=n+\lambda$. Define the following encryption scheme with message space $\mathcal{M}=\{0,1\}^{n}$:

In this scheme, $m$ is encrypted by appending a random value $r$ to it, then applying a PRP. While this scheme is conceptually quite simple, it is generally not used in practice since it requires a block cipher with a fairly large block size, and these are rarely encountered.

We can informally reason about the security of this scheme as follows:

Imagine an adversary linked to one of the CCA libraries. As long as the random value $r$ does not repeat, all inputs to the $\mathrm{PRP}$ are distinct. The guarantee of a pseudorandom function/permutation is that its outputs (which are the ciphertexts in this scheme) will therefore all look independently uniform.
The CCA library prevents the adversary from asking for $c$ to be decrypted, if $c$ was itself generated by the library. For any other value $c^{\prime}$ that the adversary asks to be decrypted, the guarantee of a strong PRP is that the result will look independently random. In particular, the result will not depend on the choice of plaintexts used to generate challenge ciphertexts. Since this choice of plaintexts is the only difference between the two CCA libraries, these decryption queries (intuitively) do not help the adversary.

We now prove the CCA security of Construction $9.3$ formally:

Claim 9.4

If $F$ is a strong $P R P$ (Definition 6.13) then Construction 9.3 has CCA$ security (and therefore CCA security).

Proof

As usual, we prove the claim in a sequence of hybrids.

Figure $\PageIndex{1}$: Copy and Paste Caption here. (Copyright; author via source)	The starting point is $\mathcal{L}_{\text {cca\$-real }}^{\Sigma}$, as expected, where $\Sigma$ refers to Construction 9.3.
Figure $\PageIndex{1}$: Copy and Paste Caption here. (Copyright; author via source)	We have applied the strong PRP security (Definition 6.13) of $F$, skipping some standard intermediate steps. We factored out all invocations of $F$ and $F^{-1}$ in terms of the $\mathcal{L}_{\text {sprp-real }}$ library, replaced that library with $\mathcal{L}_{\text {sprp-rand, }}$, and finally inlined it.

This proof has some subtleties, so it’s a good time to stop and think about what needs to be done. To prove CCA$-security, we must reach a hybrid in which the responses of CTXT are uniform. In the current hybrid there are two properties in the way of this goal:

The ciphertext values $c$ are sampled from $\{0,1\}^{\text {blen }} \backslash T$.values, rather than $\{0,1\}^{\text {blen }}$.
When the if-condition in ctXT is false, the return value of ctXT is not a fresh random value but an old, repeated one. This happens when $T[m \| r]$ is already defined. Note that both CTXT and DECRYPT assign to $T$, so either one of these subroutines may be the cause of a pre-existing $T[m \| r]$ value.

Perhaps the most subtle fact about our current hybrid is that arguments of cTXT can affect responses from DECRYPT! In CTXT, the library assigns $m \| r$ to a value $T_{\text {inv }}[c]$. Later calls to DECRYPT will not read this value directly; these values of $c$ are off-limits due to the guard condition in the first line of DECRYPT. However, DECRYPT samples a value from $\{0,1\}^{\text {blen }} \backslash T_{i n v}$.values, which indeed uses the values $T_{i n v}[c]$. To show CCA$ security, we must remove this dependence of DECRYPT on previous values given to CTXT.

	We have added some book-keeping that is not used anywhere. Every time an assignment of the form $T[m \\| r]$ happens, we add $r$ to the set $\mathcal{R}$. Looking ahead, we eventually want to ensure that $r$ is chosen so that the if-statement in cTXT is always taken, and the return value of cTXT is always a fresh random value.
	We have applied Lemma $4.12$ three separate times. The standard intermediate steps (factor out, swap library, inline) have been skipped, and this shows only the final result. In CTXT, we’ve added a restriction to how $r$ is sampled. Looking ahead, sampling $r$ in this way means that the if-statement in cTXT is always taken. In CTXT, we’ve removed the restriction in how $c$ is sampled. Since $c$ is the final return value of CTXT, this gets us closer to our goal of this return value being uniformly random. In DECRYPT, we have removed the restriction in how $m \\| r$ is sampled. As described above, this is because $T_{i n v}$. values contains previous arguments of CTXT, and we don’t want these arguments to affect the result of DECRYPT in any way.
	In the previous hybrid, the if-statement in CTXT is always taken. This is because if $T[m \\| r]$ is already defined, then $r$ would already be in $R$, but we are sampling $r$ to avoid everything in $\mathcal{R}$. We can therefore simply execute the body of the if-statement without actually checking the condition.
	In the previous hybrid, no line of code ever reads from $T$; they only write to $T$. It has no effect to remove a line that assigns to $T$, so we do so in CTXT. CTXT also writes to $T_{i n v}[c]$, but for a value $c \in \mathcal{S}$. The only line that reads from $T_{i n v}$ is in DECRYPT, but the first line of DECRYPT prevents it from being reached for such a $c \in \mathcal{S}$. It therefore has no effect to remove this assignment to $T_{i n v}$.

	We have applied Lemma $4.12$ to the sampling step in DECRYPT. The standard intermediate steps have been skipped. Now the second if-statement in DECRYPT $\left(c \in \sum . C\right)$ DECRYPT exactly matches $\mathcal{L}_{\text {sprp-rand }}$.
	We have applied the strong PRP security of $F$ to replace $\mathcal{L}_{\text {sprp-rand }}$ with $\mathcal{L}_{\text {sprp-real. }}$. The standard intermediate steps have been skipped. The result is $\mathcal{L}_{\mathrm{cca} \$ \text {-rand }}$. We showed that $\mathcal{L}_{\text {cca\$-real }}^{\Sigma} \approx \mathcal{L}_{\text {cca\$-rand }}^{\Sigma}$, so the scheme has CCA$ security.

Figure \(\PageIndex{1}\): Copy and Paste Caption here. (Copyright; author via source)	The starting point is \(\mathcal{L}_{\text {cca\$-real }}^{\Sigma}\), as expected, where \(\Sigma\) refers to Construction 9.3.
Figure \(\PageIndex{1}\): Copy and Paste Caption here. (Copyright; author via source)	We have applied the strong PRP security (Definition 6.13) of \(F\), skipping some standard intermediate steps. We factored out all invocations of \(F\) and \(F^{-1}\) in terms of the \(\mathcal{L}_{\text {sprp-real }}\) library, replaced that library with \(\mathcal{L}_{\text {sprp-rand, }}\), and finally inlined it.

	We have added some book-keeping that is not used anywhere. Every time an assignment of the form \(T[m \\| r]\) happens, we add \(r\) to the set \(\mathcal{R}\). Looking ahead, we eventually want to ensure that \(r\) is chosen so that the if-statement in cTXT is always taken, and the return value of cTXT is always a fresh random value.
	We have applied Lemma \(4.12\) three separate times. The standard intermediate steps (factor out, swap library, inline) have been skipped, and this shows only the final result. In CTXT, we’ve added a restriction to how \(r\) is sampled. Looking ahead, sampling \(r\) in this way means that the if-statement in cTXT is always taken. In CTXT, we’ve removed the restriction in how \(c\) is sampled. Since \(c\) is the final return value of CTXT, this gets us closer to our goal of this return value being uniformly random. In DECRYPT, we have removed the restriction in how \(m \\| r\) is sampled. As described above, this is because \(T_{i n v}\). values contains previous arguments of CTXT, and we don’t want these arguments to affect the result of DECRYPT in any way.
	In the previous hybrid, the if-statement in CTXT is always taken. This is because if \(T[m \\| r]\) is already defined, then \(r\) would already be in \(R\), but we are sampling \(r\) to avoid everything in \(\mathcal{R}\). We can therefore simply execute the body of the if-statement without actually checking the condition.
	In the previous hybrid, no line of code ever reads from \(T\); they only write to \(T\). It has no effect to remove a line that assigns to \(T\), so we do so in CTXT. CTXT also writes to \(T_{i n v}[c]\), but for a value \(c \in \mathcal{S}\). The only line that reads from \(T_{i n v}\) is in DECRYPT, but the first line of DECRYPT prevents it from being reached for such a \(c \in \mathcal{S}\). It therefore has no effect to remove this assignment to \(T_{i n v}\).

	We have applied Lemma \(4.12\) to the sampling step in DECRYPT. The standard intermediate steps have been skipped. Now the second if-statement in DECRYPT \(\left(c \in \sum . C\right)\) DECRYPT exactly matches \(\mathcal{L}_{\text {sprp-rand }}\).
	We have applied the strong PRP security of \(F\) to replace \(\mathcal{L}_{\text {sprp-rand }}\) with \(\mathcal{L}_{\text {sprp-real. }}\). The standard intermediate steps have been skipped. The result is \(\mathcal{L}_{\mathrm{cca} \$ \text {-rand }}\). We showed that \(\mathcal{L}_{\text {cca\$-real }}^{\Sigma} \approx \mathcal{L}_{\text {cca\$-rand }}^{\Sigma}\), so the scheme has CCA$ security.