7  Cryptographic proofs – example

We now begin studying how we can demonstrate the security of an algorithm \(E'\) given that we know the security of another related algorithm \(E\) from which it is derived. Recall the definition of a \((t,q,\epsilon)\)-PRP (Definition 5.1). There we quantify over \(t\)-time \(q\)-query adversaries.

The of an algorithm is defined as the number of steps that it runs in the worst case, without counting the time spent inside an oracle. Rather, every time an oracle is called by the algorithm, its is increased. This excludes calls to other oracles that are called by the first oracle. We illustrate how we reason about this in the following theorem and proof.

Theorem 7.1 Let \(E(k,m)\) be a \((t,q,\epsilon)\)-PRP. Then \(E'(k,m):=rev(E(k,rev(m)))\) is a \((t',q',\epsilon')\)-PRP, where \(t'=t-2qt_{rev}\), \(q'=q\), \(\epsilon'=\epsilon\), and \(rev(\mathcal{M})\) reverts the order of the bits of \(\mathcal{M}\).

This proof will proceed in a series of steps. First, we will fix a \(t'\)-time, \(q'\)-query adversary \(A\) attacking \(E'\), and we will define two games:

• Game 1: \(k \xleftarrow{\$} \mathcal{K}, b \leftarrow A^{E'(k, \cdot)}()\)
• Game 2: \(\pi \xleftarrow{\$} Perm(\mathcal{M}\rightarrow \mathcal{M}),b \leftarrow A^{\pi}()\)

These are the games from the definition of a PRP. Define a second adversary \(B^{\mathcal{O}}\) that returns \(A^F\), where \(F(m):=rev(\mathcal{O}(rev(m)))\). Then, define the following games:

• Game 3: \(k \xleftarrow{\$} \mathcal{K}, b \leftarrow B^{E(k, \cdot)}()\)
• Game 4: \(\pi \xleftarrow{\$} Perm(\mathcal{M}\rightarrow \mathcal{M}),b \leftarrow B^{\pi}()\)

These are also the games from the definition of a PRP, but for an adversary \(B\) attacking the algorithm \(E\). The query count of \(B\) is the same as the query count of A because \(B\) simulates \(A\), and whenever \(A\) makes a query, \(B\) needs to evaluate \(rev(\mathcal{O}(rev(m)))\), which contains one query to \(\mathcal{O}\). So \(B\) queries \(\mathcal{O}\) once for each query of \(A\).

Similarly, the runtime of \(B\) can be obtained by the runtime of \(A\) plus the time spent evaluating \(rev(\mathcal{O}(rev(m)))\) \(q'\) times, so \(t'+2q't_{rev}\). Since \(q=q'\) and \(t'+2q't_{rev} = (t-2q't_{rev})+2q't_{rev} = t\), \(B\) is a \(t\)-time \(q\)-query adversary. Since \(E\) is a \((t,q,\epsilon)\)-PRP by assumption, we have \(|\Pr[b=1: \textrm{Game 3}]-\Pr[b=1: \textrm{Game 4}]|\leq\epsilon=\epsilon'\).

If we unfold/inline the definition of \(B\) in Game 3 and simplify a bit, we get:

• Game \(3_{\textrm{refactored}}\): \(k \xleftarrow{\$} \mathcal{K}, b \leftarrow A^{E(k,\cdot)}()\),

where we used that \(rev(E'(k,rev(m)))=E(k,m)\) to rewrite the oracle call of \(A\). Since this is just rewriting the definition of Game 3, we have that \(\Pr[b=1: \textrm{Game 3}]=\Pr[b=1: \textrm{Game 3}_{\textrm{refactored}}]=\Pr[b=1: \textrm{Game 1}]\). Similarly, we define:

• Game \(4_{\textrm{refactored}}\): \(\pi \xleftarrow{\$} Perm(\mathcal{M}\rightarrow \mathcal{M}),b \leftarrow A^{F}()\),

where \(F(x)=rev(\pi(rev(x)))\). Since \(\pi\) is a random permutation, so is \(F\), and thus we have \(\Pr[b=1: \textrm{Game 4}]=\Pr[b=1: \textrm{Game 4}_{\textrm{refactored}}]=\Pr[b=1: \textrm{Game 2}]\). This finally leads us to \(|\Pr[b=1: \textrm{Game 1}]-\Pr[b=1: \textrm{Game 2}]|=|\Pr[b=1: \textrm{Game 3}]-Pr[b=1: \textrm{Game 4}]|\leq\epsilon\). Thus \(A\) has success probability \(\leq\epsilon'\) in attacking \(E'\), so \(E'\) is a \((t',q',\epsilon')\)-PRP. \(\hfill\blacksquare\)