Additionally, in simplification (simplify), if $\mathcal{F}$ contains $M_1 = M_2$ such that $x$ occurs in $M_1$, $x$ is defined only by random choices $x \stackrel{R}{\leftarrow} T$, $T$ is a large type, and $M_1$ characterizes a part of $x$, we trigger the global dependency analysis (Section 5.1.20). If the global dependency analysis succeeds in transforming the game, the simplification is restarted from the game obtained after global dependency analysis.

Rule (21) is applied only when Rules (17) to (20) cannot be applied. Rule (21) transforms equations into rewrite rules by orienting them. We say that $M > M'$ when either $M$ is the form $x[\tilde{M}]$, $x$ does not occur in $M'$, and $x$ is not defined only by random choices, or $M = x[M_1, \dots, M_m]$, $M' = x[M'_1, \dots, M'_m]$, and for all $j \le m$, $M_j > M'_j$. Intuitively, our goal is to replace $M$ with $M'$ when $M'$ defines the content of the variable $M$. (Notice that this is not an ordering; the Knuth-Bendix algorithm normally uses a reduction ordering to orient equations. However, we tried some reduction orderings, namely the lexicographic path ordering and the Knuth-Bendix ordering, and obtained disappointing results: the prover fails to prove many equalities because too many equations are left unoriented. The simple heuristic given above succeeds more often, at the expense of a greater risk of non-termination, but that does not cause problems in practice on our examples. We believe that this comes from the particular structure of equations, which come from let definitions and from conditions of find or if, and tend to define variables from other variables without creating dependency cycles.)

Rules (22) and (23) are systematically applied to simplify all rewrite rules of $\mathcal{R}$ after a new rewrite rule has been added by Rule (21). Since all terms in rewrite rules of $\mathcal{R}$ are considered as constants, Rule (23) in fact includes the deduction of equations from critical pairs done by the standard Knuth-Bendix completion algorithm.

We say that $\mathcal{F}$ yields a contradiction when the prover, starting from $(\mathcal{F}, \emptyset)$, derives false.

**Extension:** That depends on the program point for local dependency analysis. We ignore that point for now. For the proof of correspondences, local dependency analysis is not used. The current game $Q_0$ is used for the basic dependency analysis (rule (19) and first item of (20)).

**Lemma 34** If for all $j \in J$, $\mathcal{F}_j$ yields a contradiction in a game $Q_0$, then CryptoVerif returns a probability $p$ such that for all attackers $A \in \mathcal{BB}$ and all evaluation contexts $C$ acceptable for $Q_0$ with any public variables, $\text{Pr}^A[C[Q_0] \le \bigvee_{j \in J} \exists \tilde{x}_j \in \tilde{T}_j, \bigwedge \mathcal{F}_j] \le p(A, C)$, where $\tilde{x}_j$ are the replication indices and non-process variables that occur in $\mathcal{F}_j$ and $\tilde{T}_j$ are their types.

In particular, the lemma states that, when several sets of facts $\mathcal{F}_j$ yield a contradiction in the same game, CryptoVerif counts only once in the probability $p$ the collisions that are eliminated in proofs that $\mathcal{F}_j$ yields a contradiction for several $j$.

More generally, let us consider an algorithm $\varphi$ built from the following grammar:

<table><tr><td>\varphi ::=</td><td>algorithm</td></tr><tr><td>  <span style="font-family: monospace;">\mathcal{F} yields a contradiction</span></td><td>equational proof</td></tr><tr><td>  <span style="font-family: monospace;">\varphi<sub>1</sub> ∧ \varphi<sub>2</sub></span></td><td>conjunction</td></tr><tr><td>  <span style="font-family: monospace;">\varphi<sub>1</sub> ∨ \varphi<sub>2</sub></span></td><td>disjunction</td></tr><tr><td>  <span style="font-family: monospace;">\psi</span></td><td>mathematical formula</td></tr><tr><td>  if \psi then \varphi<sub>1</sub> else \varphi<sub>2</sub></td><td>test</td></tr></table>

The mathematical formulas $\psi$ in such algorithms must not depend on the executed trace. (They may depend on the syntax of the game $Q_0$ or on the set of public variables $V$, for instance.)

We translate such algorithms into logical formulas on traces:

$$ \{[\mathcal{F} \text{ yields a contradiction}]\} = \neg \exists \tilde{x} \in \tilde{T}, \bigwedge \mathcal{F} \text{ where } \tilde{x} \text{ are the replication indices and non-process variables that occur in } \mathcal{F} \text{ and } \tilde{T} \text{ are their types.} $$
$$ \{\{\varphi_1 \wedge \varphi_2\}\} = \{\{\varphi_1\}\} \wedge \{\{\varphi_2\}\} $$

$$ \{\{\varphi_1 \vee \varphi_2\}\} = \begin{cases} \{\{\varphi_1\}\} & \text{if } \varphi_1 \\ \{\{\varphi_2\}\} & \text{otherwise} \end{cases} $$

$$ \{\psi\} = \psi $$

$$ \{\text{if } \psi \text{ then } \varphi_1 \text{ else } \varphi_2\} = \text{if } \psi \text{ then } \{\{\varphi_1\}\} \text{ else } \{\{\varphi_2\}\} $$

Intuitively, when algorithm $\varphi$ returns true, CryptoVerif shows that the formula $\{\{\varphi\}\}$ holds for most traces. It bounds the probability of the traces for which this formula does not hold, as shown by the following lemma.

**Lemma 35** If algorithm $\varphi$ returns true in a game $Q_0$, then CryptoVerif returns a probability $p$ such that for all attackers $A \in \mathcal{A} \in \mathcal{B}\mathcal{B}$ and all evaluation contexts $C$ acceptable for $Q_0$ with any public variables, $\Pr^A[C|Q_0] \le \neg\{\{\varphi\}\} \le p(A, C)$.

**Proof** We show by induction on the definition of $\varphi$ that, if $\varphi$ returns true and $Tr \vdash \neg\{\{\varphi\}\}$, then there exists $\mathcal{F}$ such that “$\mathcal{F}$ yields a contradiction” has been called in the evaluation of $\varphi$ and returned true, and $Tr \vdash \exists \tilde{x} \in \tilde{T}, \wedge \mathcal{F}$ where $\tilde{x}$ are the replication indices and non-process variables that occur in $\mathcal{F}$ and $\tilde{T}$ are their types.

* Case $\varphi = (\mathcal{F}$ yields a contradiction): obvious.

* Case $\varphi = \varphi_1 \wedge \varphi_2$: Since $\varphi$ returns true, $\varphi_1$ and $\varphi_2$ both return true. Since $Tr \vdash \neg(\{\{\varphi_1\}\} \wedge \{\{\varphi_2\}\})$, we have either $Tr \vdash \neg\{\{\varphi_1\}\}$ or $Tr \vdash \neg\{\{\varphi_2\}\}$. In the first case, by induction hypothesis on $\varphi_1$, there exists $\mathcal{F}$ such that “$\mathcal{F}$ yields a contradiction” has been called in the evaluation of $\varphi_1$ and returned true, and $Tr \vdash \exists \tilde{x} \in \tilde{T}, \wedge \mathcal{F}$ where $\tilde{x}$ are the replication indices and non-process variables that occur in $\mathcal{F}$ and $\tilde{T}$ are their types. Moreover, “$\mathcal{F}$ yields a contradiction” has been called in the evaluation of $\varphi$. The second case is symmetric.

* Case $\varphi = \varphi_1 \vee \varphi_2$: If $\varphi_1$ returns true, then $\{\{\varphi\}\} = \{\{\varphi_1\}\}$, so $Tr \vdash \neg\{\{\varphi_1\}\}$. We conclude by induction hypothesis on $\varphi_1$, as above. If $\varphi_1$ returns false, then $\varphi_2$ returns true, since $\varphi$ returns true. Hence $\{\{\varphi\}\} = \{\{\varphi_2\}\}$, so $Tr \vdash \neg\{\{\varphi_2\}\}$. We conclude by induction hypothesis on $\varphi_2$.

* Case $\varphi = \psi$: since $\psi$ evaluates to true, there is no trace $Tr$ such that $Tr \vdash \neg\psi$, so the property holds trivially.

* Case $\varphi = \text{if } \psi$ then $\varphi_1$ else $\varphi_2$: if $\psi$ evaluates to true, then we conclude by induction hypothesis on $\varphi_1$. Indeed, since $\varphi$ returns true, $\varphi_1$ returns true. Since $Tr \vdash \neg\{\{\varphi\}\}$, we have $Tr \vdash \neg\{\{\varphi_1\}\}$. By induction hypothesis, there exists $\mathcal{F}$ such that “$\mathcal{F}$ yields a contradiction” has been called in the evaluation of $\varphi_1$ and returned true, and $Tr \vdash \exists \tilde{x} \in \tilde{T}, \wedge \mathcal{F}$ where $\tilde{x}$ are the replication indices and non-process variables that occur in $\mathcal{F}$ and $\tilde{T}$ are their types. Then “$\mathcal{F}$ yields a contradiction” has also been called in the evaluation of $\varphi$. Similarly, if $\psi$ evaluates to false, then we conclude by induction hypothesis on $\varphi_2$.

We conclude by Lemma 34. $\square$

# 4 success: Criteria for Proving Security Properties

The command **success** tries to prove the active queries, as explained below. We consider an oracle definition $Q_0$ that satisfies Properties 3 and 4, and prove secrecy and correspondence properties for $Q_0$.
<figure><img src="image_12.png" /><figcaption>Figure 22: Event contexts</figcaption></figure>

## 4.1 Secrecy

Let us now define syntactic criteria that allow us to prove secrecy properties of protocols. We first define the function noleak, explained below. This function implicitly depends on the current game $Q_0$ and the public variables $V$.

$$ \text{noleak}(x[\widetilde{M}'], \mathcal{I}, \mathcal{F}) = (\mathcal{F} \text{ yields a contradiction}) \lor ((x \notin V) \land \bigwedge_{\mu x[\widetilde{M}] \text{ in } Q_0}$$

- if $^\mu x[\widetilde{M}]$ is in $M$ in an assignment let $y[\tilde{i}] = M$ in $Q_0$, $M$ is built from replication indices, variables, function applications, and conditionals, and the current call is not inside a call to noleak($y[-], -, -$), then

$$ \text{noleak}(y[\theta\tilde{i}], \mathcal{I} \cup \{\theta\tilde{i}\}, \mathcal{F} \cup \theta\mathcal{F}_\mu \cup \{\theta\widetilde{M} = \widetilde{M'}\}) \\ \text{where } \theta \text{ is a renaming of } \tilde{i} \text{ to fresh replication indices} $$

- if $^\mu x[\widetilde{M}]$ is in event $e(M_1, \dots, M_{k-1}, C[^\mu x[\widetilde{M}]], M_{k+1}, \dots, M_m)$ in $Q_0$ for $C$ defined in Figure 22, then true

- otherwise, $\mathcal{F} \cup \theta\mathcal{F}_\mu \cup \{\theta\widetilde{M} = \widetilde{M'}\}$ yields a contradiction
  where $\theta$ is a renaming of $I_\mu$ to fresh replication indices)

The function call noleak($x[\widetilde{M}'], \mathcal{I}, \mathcal{F}$) shows that $x[\widetilde{M}']$ does not leak to the adversary, assuming $\mathcal{F}$ holds. The set $\mathcal{I}$ contains all replication indices that appear in $\mathcal{F}$. If $\mathcal{F}$ yields a contradiction, noleak is true, since it shows the absence of leak assuming $\mathcal{F}$ holds. Otherwise, $x[\widetilde{M}']$ may leak either because $x \in V$ so $x$ is a public variable, or because of an occurrence of a term $x[\widetilde{M}]$ in the game that reads $x[\widetilde{M}']$ (so $\widetilde{M} = \widetilde{M}'$ holds) and such that the result of $x[\widetilde{M}]$ leaks.

* In case $x[\widetilde{M}]$ occurs in the term $M$ in an assignment let $y[\tilde{i}] = M$, the function noleak recursively tries to prove that $y[\tilde{i}]$ does not leak, when $y[\tilde{i}]$ may use $x[\widetilde{M}']$, that is, when $\widetilde{M}' = \widetilde{M}$. The fact $\widetilde{M}' = \widetilde{M}$ and the facts $\mathcal{F}_\mu$ that hold at the program point $\mu$ of $x[\widetilde{M}]$
are added to the known facts $\mathcal{F}$ in the recursive call. Indeed, these facts are known to hold in this case. The replication indices are renamed to fresh indices in order to avoid using the same index variable for indices that can actually take different values.

* In case $x[\tilde{M}]$ occurs in the arguments of an event, the arguments of the event do not leak to the adversary, so this occurrence of $x[\tilde{M}]$ does not make $x[\tilde{M}']$ leak.

* In all other cases, we consider that the result of $x[\tilde{M}]$ may leak, so, in order to prove that $x[\tilde{M}']$ does not leak, we show that the occurrence of $x[\tilde{M}]$ at $\mu$ cannot read $x[\tilde{M}']$, by showing that $\tilde{M} = \tilde{M}', \mathcal{F}_{\mu}$, and $\mathcal{F}$ together yield a contradiction.

**Definition 15** ($\mu$ follows a definition of $x$) We say that $\mu$ follows a definition of $x$ when $x[\tilde{i}] \stackrel{R}{\leftarrow} T;^\mu \dots$, let $x[\tilde{i}] = M$ in $^\mu \dots$, find unique? ] ($\bigoplus_{j=1}^m \tilde{u}_j[\tilde{i}] = \tilde{i}_j \le \tilde{n}_j$ such that defined($\tilde{M}_j$) $\wedge$ $M_j$ then $^\mu$ $\dots$ else $\dots$ with $\mu_j = \mu$ and $x$ in $\tilde{u}_j$ for some $j \le m$, or $O(x[\tilde{i}] : T) := ^\mu P$ occurs in $Q_0$.

We do not mention get in the previous definition, because it is excluded by Property 3. For each $\mu$ that follows a definition of $x$ in $Q_0$, we define $\text{defRand}_\mu(x)$ as follows:

$$ \text{defRand}_{\mu}(x) = \begin{cases} x[\tilde{i}] & \text{if } x[\tilde{i}] \stackrel{R}{\leftarrow} T;^\mu \dots \text{ occurs in } Q_0 \\ y[\tilde{M}] & \text{if let } x[\tilde{i}] : T = y[\tilde{M}] \text{ in } ^\mu \dots \text{ occurs in } Q_0 \text{ and} \\ & y \text{ is defined only by random choices in } Q_0 \end{cases} $$

In all other cases, $\text{defRand}_\mu(x)$ is not defined. The variable $\text{defRand}_\mu(x)$ is the random variable that defines $x$ just before program point $\mu$. When $x$ itself is chosen randomly at that point, $\text{defRand}_\mu(x)$ is simply $x[\tilde{i}]$, where $\tilde{i}$ are the current replication indices. When $x$ is defined by an assignment of a variable $y[\tilde{M}]$ that is random, $\text{defRand}_\mu(x)$ is that variable. Otherwise, we give up and do not define $\text{defRand}_\mu(x)$.

$$ \begin{array}{l} \text{prove}^{1\text{-ses.secr.}(x)}(\mu) = \text{defRand}_{\mu}(x) \text{ is defined and} \\ \text{noleak}(\theta\text{defRand}_{\mu}(x), \{\theta I_{\mu}\}, \theta\mathcal{F}_{\mu}) \\ \text{where } \theta \text{ is a renaming of } I_{\mu} \text{ to fresh replication indices} \end{array} $$

$$ \text{prove}^{1\text{-ses.secr.}(x)}(S) = \bigwedge_{\mu \in S} \text{prove}^{1\text{-ses.secr.}(x)}(\mu) $$

The function call $\text{prove}^{1\text{-ses.secr.}(x)}(\mu)$ proves one-session secrecy for the definition of $x$ just before program point $\mu$. It considers only the cases in which $x$ is defined either by a random choice or by an assignment from a random choice. In other cases, the proof fails. (These other cases can typically be handled by first removing assignments as needed.) Intuitively, $\text{prove}^{1\text{-ses.secr.}(x)}(\mu)$ guarantees that, when $x[\tilde{i}]$ is defined just before program point $\mu$, the random variable $\text{defRand}_\mu(x)$ that defines $x[\tilde{i}]$ does not leak, knowing that the facts $\mathcal{F}_\mu$ hold. Only events and variables $y[\tilde{i}']$ that do not leak depend on the random choice that defines $x[\tilde{i}]$; the sent messages and the control flow of the process are independent of $x[\tilde{i}]$, so the adversary obtains no information on $x[\tilde{i}]$. That guarantees the one-session secrecy of $x[\tilde{i}]$ when it is defined just before $\mu$. This is verified for all program points in $S$ by $\text{prove}^{1\text{-ses.secr.}(x)}(S)$. When $x$ is defined by assignment of $z[\tilde{M}]$, this proof of one-session secrecy allows some array cells of $z$ to leak, provided the array cells $z[\tilde{M}]$ used to define $x$ do not leak.
In order to prove secrecy, we also define prove<sup>distinct(x)</sup>(μ₁, μ₂) = (z₁ ≠ z₂) ∨ (θ₁F<sub>μ₁</sub> ∪ θ₂F<sub>μ₂</sub> ∪ {θ₁M̃₁ = θ₂M̃₂, ̃i₁ ≠ ̃i₂}) yields a contradiction), where defRand<sub>μ₁</sub>(x) = z₁[M̃₁], defRand<sub>μ₂</sub>(x) = z₂[M̃₂], ̃i are the current replication indices at the definition of x, θ₁ and θ₂ are two distinct renamings of ̃i to fresh replication indices, ̃i₁ = θ₁̃i, and ̃i₂ = θ₂̃i. Intuitively, prove<sup>distinct(x)</sup>(μ₁, μ₂) guarantees that, if x[̃i₁] is defined at μ₁, so x[̃i₁] = z₁[θ₁M̃₁], and x[̃i₂] is defined at μ₂, so x[̃i₂] = z₂[θ₂M̃₂], with ̃i₁ ≠ ̃i₂, then the random variables that define x in these two cases, z₁[θ₁M̃₁] and z₂[θ₂M̃₂], are different, that is, z₁ ≠ z₂ or θ₁M̃₁ ≠ θ₂M̃₂. Therefore, z₁[θ₁M̃₁] is independent of z₂[θ₂M̃₂], so x[̃i₁] is independent of x[̃i₂]. Combining this information with the proof of one-session secrecy, we can prove secrecy of x: we define

$$ \text{prove}^{\text{Secrecy}(x)}(S) = \text{prove}^{1\text{-ses.secr.}(x)}(S) \wedge \bigwedge_{\mu_1, \mu_2 \in S} \text{prove}^{\text{distinct}(x)}(\mu_1, \mu_2) $$

The proof of bit secrecy is the same as for one-session secrecy:

$$ \text{prove}^{\text{bit secr.}(x)}(S) = \text{prove}^{1\text{-ses.secr.}(x)}(S) $$

The proof of (one-session or bit) secrecy is justified by the following proposition.

**Proposition 1 (One-session or bit) secrecy)** Consider an oracle definition Q₀ that satisfies Properties 3 and 4. Let sp be 1-ses.secr.(x), Secrecy(x), or bit secr.(x). Let S = {μ | μ follows a definition of x}. If prove<sup>sp</sup>(S) and for all attackers A ∈ BB and all evaluation contexts C acceptable for Q₀, Pr<sup>A</sup>[C[Q₀] ≤ ¬{[prove<sup>sp</sup>(S)]}] ≤ p(A, C), then Q₀ satisfies sp with public variables V (x /∈ V) up to probability p' such that p'(A, C) = p(A, C[C<sub>sp</sub>[]]) and Bound<sub>Q₀</sub>(V ∪ {x}, sp, D<sub>false</sub>, p).

The proof of Proposition 1 relies on the following definitions and lemma. We have

$$ \{\text{noleak}(x[\tilde{M}'], \mathcal{I}, \mathcal{F})\} = (\forall \mathcal{I}, \neg \bigwedge \mathcal{F}) \lor ((x \notin V) \land \bigwedge_{\mu} x[\tilde{M}] \text{ in } Q_0) $$

– if μx[tilde{M}] is in M in an assignment let y[̃i] = M, M is built from replication indices, variables, function applications, and conditionals, and the current call is not inside a call to nolek(y, -, -), then

$$ \{\text{noleak}(y[\theta\tilde{i}], \mathcal{I} \cup \{\theta\tilde{i}\}, \mathcal{F} \cup \theta\mathcal{F}_{\mu} \cup \{\theta\tilde{M} = \tilde{M}'\})\} $$
where θ is a renaming of ̃i to fresh replication indices

– if μx[tilde{M}] is in event e(M₁, ..., M<sub>k-1</sub>, C[μx[tilde{M}]], M<sub>k+1</sub>, ..., M<sub>m</sub>) for C defined in Figure 22, then true

– otherwise, ∀(I ∪ θI<sub>μ</sub>), ¬(F ∪ θF<sub>μ</sub> ∪ {θM̃ = M̃'})
where θ is a renaming of I<sub>μ</sub> to fresh replication indices)

{[noleak(x[tilde{M}'], I, F)}} is the logical formula that is guaranteed when nolek(x[tilde{M}'], I, F) succeeds, up to a small probability computed by the equational prover and that bounds the probability Pr<sup>A</sup>[C[Q₀] ≤ ¬{[noleak(x[tilde{M}'], I, F)]}] . It is obtained by collecting formulas guaranteed by each call to “F yields a contradiction”: such a call guarantees ∀z̃ ∈ T'', ¬(F up to a small probability that it evaluates, where z̃ are the non-process variables in F and T'' are their types. In the definition of {[noleak(x[tilde{M}'], I, F]}], the notation ∀I means that all variables in I are
universally quantified in their respective types. The notation $\forall(\mathcal{I} \cup \theta I_\mu)$ is similar. We have similarly

$$
\begin{align*}
\llbracket \text{prove}^{\text{1-ses.secr.}}(x)(\mu) \rrbracket &= \begin{cases}
\llbracket \text{noleak}(\theta \text{defRand}_\mu(x), \{\theta I_\mu\}, \theta \mathcal{F}_\mu) \rrbracket & \text{if } \text{defRand}_\mu(x) \text{ is defined,} \\
\text{where } \theta \text{ is a renaming of } I_\mu \text{ to fresh replication indices} & \\
\text{false otherwise}
\end{cases} \\
\llbracket \text{prove}^{\text{1-ses.secr.}}(x)(S) \rrbracket &= \bigwedge_{\mu \in S} \llbracket \text{prove}^{\text{1-ses.secr.}}(x)(\mu) \rrbracket \\
\llbracket \text{prove}^{\text{distinct}}(x)(\mu_1, \mu_2) \rrbracket &= (z_1 \neq z_2) \lor (\forall \tilde{i}_1, \forall \tilde{i}_2, \neg \bigwedge \theta_1 \mathcal{F}_{\mu_1} \cup \theta_2 \mathcal{F}_{\mu_2} \cup \{\theta_1 \tilde{M}_1 = \theta_2 \tilde{M}_2, \tilde{i}_1 \neq \tilde{i}_2\}) \\
\llbracket \text{prove}^{\text{Secrecy}}(x)(S) \rrbracket &= \llbracket \text{prove}^{\text{1-ses.secr.}}(x)(S) \rrbracket \wedge \bigwedge_{\mu_1, \mu_2 \in S} \llbracket \text{prove}^{\text{distinct}}(x)(\mu_1, \mu_2) \rrbracket \\
\llbracket \text{prove}^{\text{bit secr.}}(x)(S) \rrbracket &= \llbracket \text{prove}^{\text{1-ses.secr.}}(x)(S) \rrbracket
\end{align*}
$$

The only semantic rules that can add $x[\tilde{a}]$ to the environment $E$ are (NewT), (LetT), (FindT1), (New), (Let), (Find1), (OracleCall), (Return), (AttIO), and (AttYield). (**get** is excluded by Property 3.) By Corollary 1, the target term or process of these rules is a subterm or subprocess of $Q_0$ up to renaming of oracles. Hence, the target configuration *Conf* of these rules is at some program point $\mu$ in *Tr*. In this case, we say that $x[\tilde{a}]$ is defined just before $\mu$ in a trace *Tr*. Furthermore, given $x[\tilde{a}]$ and *Tr*, there is at most one program point $\mu$ such that $x[\tilde{a}]$ is defined just before $\mu$ in *Tr*, by Lemma 29.

Let sp be 1-ses.secr.(x), Secrecy(x), or bit secr.(x). Let Tr be a trace of C[C<sub>sp</sub>[Q<sub>0</sub>]]. Let E = E<sub>Tr</sub>. We define the set Tidx(Tr) of indices of successful test queries as follows:

* When sp is 1-ses.secr.(x): Let $\mu_t$ be the program point of the oracle that performs the test query in $Q_{1-ses.secr.}(x): \mu_t O_s(u_1: [1, n_1], \dots, u_m: [1, n_m])$. If there is a (AttIO) or (OracleCall) reduction in Tr with $\mu' = \mu_t$, we define $E'$ to be the environment after that reduction. If $x[E(u_1), \dots, E(u_m)] \in \text{Dom}(E')$, we let $\text{Tidx}(Tr) = \{\epsilon\}$ (the empty sequence of indices). Otherwise, $\text{Tidx}(Tr) = \emptyset$.

* When sp is Secrecy(x): Let $\mu_t$ be the program point of the oracle definition that performs the test query in $Q_{\text{Secrecy}}(x): \mu_t O_s[i_s](u_1: [1, n_1], \dots, u_m: [1, n_m])$. Let $\text{Tidx}(Tr) = \{a \in [1, n_s] \mid$ there is a (AttIO) or (OracleCall) reduction in Tr with $\mu' = \mu_t$, $\sigma'(\tilde{i}) = a$, and $x[E(u_1[a]), \dots, E(u_m[a])] \in \text{Dom}(E')$ where $E'$ is the environment after that reduction, and for all a (AttIO) or (OracleCall) reductions in Tr before the latter reduction, with $\mu' - \mu_t = \sigma'(\tilde{i}) = a'$, $E(u_1[a']) = E(u_1[a]), \dots$, and $E(u_m[a']) = E(u_m[a]),$ we have $x[E(u_1[a]), \dots, E(u_m[a])] \notin \text{Dom}(E'')$ where $E''$ is the environment after that reduction$\}$.

The test query with index $a$ is the first successful test query for $x[E(u_1[a]), \dots, E(u_m[a])]$, so $x[E(u_1[a]), \dots, E(u_m[a])]$ is defined at that test query, that is, $x[E(u_1[a]), \dots, E(u_m[a])] \in \text{Dom}(E')$. For all previous test queries on the same indices, $x[E(u_1[a]), \dots, E(u_m[a])]$ was not defined, that is, $x[E(u_1[a]), \dots, E(u_m[a])] \notin \text{Dom}(E'')$. The bound $n_s$ and the variables $u_1, \dots, u_m$ come from $Q_{\text{Secrecy}}(x)$.

* When sp is bit secr.(x): Let $\mu_t$ be the program point of the oracle definition in $Q_{\text{bit secr.}}(x): \mu_t O_s''(b' : \text{bool})$. If there is a (AttIO) or (OracleCall) reduction in Tr with $\mu' = \mu_t$, we define $E'$ to be the environment after that reduction. If $x \in \text{Dom}(E')$, we let $\text{Tidx}(Tr) = \{\epsilon\}$. Otherwise, $\text{Tidx}(Tr) = \emptyset$.
Let Tpp($Tr$) = {$\mu$ | $\exists a \in \text{Tidx}(Tr), x[E(u_1[a]), \dots, E(u_m[a])]$} is defined just before $\mu$ in $Tr$}. When sp is bit $\text{secr.}(x)$, $m = 0$, so this definition reduces to Tpp($Tr$) = $\emptyset$ if $\text{Tidx}(Tr) = \emptyset$ and Tpp($Tr$) = {$\mu_\epsilon$} where $x$ is defined just before $\mu_\epsilon$ in $Tr$ otherwise. We write $Tr \vdash sp$ when $Tr \vdash [[\text{prove}^{sp}(Tpp(Tr))]]$.

**Lemma 36** Consider a process $Q_0$ that satisfies Properties 3 and 4. Let sp be 1-ses.secr.(x), Secrecy(x), or bit $\text{secr.}(x)$. Let C be an evaluation context acceptable for $C_{sp}[Q_0]$ with any public variables V ($x \notin V$) that does not contain S nor $\bar{S}$ and A be an attacker in BB. We have

$$ \Pr^A[C[C_{sp}[Q_0]] : S \wedge sp] = \Pr^A[C[C_{sp}[Q_0]] : \bar{S} \wedge sp]. $$

**Proof of the cases** sp = 1-ses.secr.(x) and sp = Secrecy(x) Let $Tr$ be a full trace of $C[C_{sp}[Q_0]]$ for attacker A such that $Tr \vdash sp$ and $b$ is defined in $Tr$, that is, $b \in \text{Dom}(E_{Tr})$.

Let $E = E_{Tr}$. Let $\tilde{i}$ be the current replication indices at the definition of $x$ in $Q_0$. For $j \in \text{Tidx}(Tr)$, let $\tilde{a}_j = E(u_1[j]), \dots, E(u_m[j])$, so that the test query at index $j$ tests $x[\tilde{a}_j]$. Let $\text{Conf}_j$ be the target configuration of the semantic rule that adds $x[\tilde{a}_j]$ to $E$, and $\mu_j$ be such that $x[\tilde{a}_j]$ is defined just before $\mu_j$ in $Tr$. So $\text{Conf}_j$ is at program point $\mu_j$ in $Tr$. Let $z_j[\tilde{M}_j] = \text{defRand}_{\mu_j}(x)$ (which is always defined since $\mu_j \in \text{Tpp}(Tr)$ and $Tr \vdash sp$, so $Tr \vdash [[\text{prove}^{1-ses.secr.}(x)(\mu_j)]])$. Let $\tilde{b}_j$ be such that $E, \{\tilde{i} \mapsto \tilde{a}_j\}, \tilde{M}_j \downarrow \tilde{b}_j$. Then $x[\tilde{a}]$ is added to the environment $E$ by (NewT), (LetT), (New), or (Let), we have $E(x[\tilde{a}_j]) = E(z_j[\tilde{b}_j])$, and $z_j[\tilde{b}_j]$ is chosen at random by (NewT) or (New) in $Tr$ by definition of $\text{defRand}_{\mu_j}(x)$. Let us prove that, for all $j_1 \neq j_2$ in $\text{Tidx}(Tr)$, we have $z_{j_1} \neq z_{j_2}$ or $\tilde{b}_{j_1} \neq \tilde{b}_{j_2}$.

* When sp is 1-ses.secr.(x), this is trivially true since $\text{Tidx}(Tr)$ contains at most one element.

* When sp is Secrecy(x), we have $\mu_{j_1}, \mu_{j_2} \in \text{Tpp}(Tr)$ and $Tr \vdash \text{Secrecy}(x)$, so we have $Tr \vdash [[\text{prove}^{\text{distinct}}(x)(\mu_{j_1}, \mu_{j_2})]]$, so $z_{j_1} \neq z_{j_2}$ or $Tr \vdash \forall \tilde{i}_1, \forall \tilde{i}_2, \neg \bigwedge \theta_1 \mathcal{F}_{\mu_{j_1}} \cup \theta_2 \mathcal{F}_{\mu_{j_2}} \cup \{\theta_1 \tilde{M}_{j_1} = \theta_2 \tilde{M}_{j_2}, \tilde{i}_1 \neq \tilde{i}_2\}$ where $\theta_1$ and $\theta_2$ are two distinct renamings of $\tilde{i}$ to fresh replication indices, $\tilde{i}_1 = \theta_1 \tilde{i}$, and $\tilde{i}_2 = \theta_2 \tilde{i}$. In the latter case, let $\rho = \{\tilde{i}_1 \mapsto \tilde{a}_{j_1}, \tilde{i}_2 \mapsto \tilde{a}_{j_2}\}$. We have $\sigma_{\text{Conf}_{j_1}} = [\tilde{i} \mapsto \tilde{a}_{j_1}]$. By Corollary 3, $Tr, \rho \vdash \theta_1 \mathcal{F}_{\mu_{j_1}}$. Similarly, $Tr, \rho \vdash \theta_2 \mathcal{F}_{\mu_{j_2}}$. Since $j_1 \neq j_2$, $\tilde{a}_{j_1} \neq \tilde{a}_{j_2}$. (By construction of $\text{Tidx}(Tr)$, we consider only the first successful test query for a certain $x[\tilde{a}_j]$.) So $Tr, \rho \vdash \tilde{i}_1 \neq \tilde{i}_2$. Therefore, $Tr, \rho \vdash \theta_1 \tilde{M}_{j_1} \neq \theta_2 \tilde{M}_{j_2}$, so $\tilde{b}_{j_1} \neq \tilde{b}_{j_2}$.

For $j \in \text{Tidx}(Tr)$, let us choose elements $v_j$ in $T$, where $T$ is the type of $x$. Let us consider the following two sets of traces:

1. $Tr$ modified by choosing $b = \text{true}$ and $z_j[\tilde{b}_j] = v_j$ for all $j \in \text{Tidx}(Tr)$. (The variable $b$ is chosen and used in $Q_{sp}$. Note that the variable $y$ of $Q_{sp}$ is not defined when $b = \text{true}$. This set contains a single trace.)

2. $Tr$ modified by choosing $b = \text{false}$ and $y[j] = v_j$ and $z_j[\tilde{b}_j] = v'_j$ for any $v'_j \in T$, for all $j \in \text{Tidx}(Tr)$. (This set contains $|T|^{\text{Tidx}(Tr)}$ traces.)

The trace $Tr$ is one of the traces in these two sets: just choose the values of $b, z_j[\tilde{b}_j]$, and $y[j]$ if $b$ is false that are used in $Tr$.

We show by induction on the derivation of these traces $Tr_s$ ($Tr_1$ is in set 1 and $Tr_2$ is in set 2) that they have matching configurations $\text{Conf}'_s = E_s, \sigma, M_s, \mathcal{T}, \mu\mathcal{E}v_s, \text{Conf}'_s = Q_s, \mathcal{O}r$, or $\text{Conf}'_s = E_s, (\sigma, P_s) :: St_s, Q_s, \mathcal{O}r, \mathcal{T}, \mu\mathcal{E}v_s$ for $s \in \{1, 2\}$ that differ as follows:
* $E_1(b) = \text{true while } E_2(b) = \text{false.}$

* $E_1(u'_s[j])$ when sp is Secrecy($x$) and $E_1(y[j])$ are undefined even when $E_2(u'_s[j])$ and $E_2(y[j])$ are defined for some indices $j \in \text{Tidx}(\text{Tr})$.

* $E_1(z[\tilde{a}])$ differs from $E_2(z[\tilde{a}])$ for some $z$ and $\tilde{a}$ such that for some $\tilde{M}, \mathcal{I}, \mathcal{F}$, we have $\text{Tr} \vdash \{[\text{noleak}(z[\tilde{M}], \mathcal{I}, \mathcal{F})]\}$ and $\text{Tr} \vdash \exists \mathcal{I}, (\tilde{M} = \tilde{a}) \wedge \wedge \mathcal{F}$.

* Values inside $M_1$ and $M_2$ may differ when $\text{Conf}'_s$ (for $s \in \{1, 2\}$) occurs in the derivation of

$$ 
\begin{gathered}
E_s, \sigma, \text{let } y[\tilde{i}] = M \text{ in } M', \mathcal{T}, \mu\mathcal{E}v_s \xrightarrow{1} E_s[y[\sigma\tilde{i}] \mapsto a_s], \sigma, M', \mathcal{T}, \mu\mathcal{E}v_s \\
\text{or of } E_s, (\sigma, \text{let } y[\tilde{i}] = M \text{ in } P) :: St_s, Q_s, \text{Or}, \mathcal{T}, \mu\mathcal{E}v_s \xrightarrow{1} \\
E_s[y[\sigma\tilde{i}] \mapsto a_s], (\sigma, P) :: St_s, Q_s, \text{Or}, \mathcal{T}, \mu\mathcal{E}v_s
\end{gathered}
$$

where $M$ is built from replication indices, variables, function applications, and conditionals and for some $\tilde{M}, \mathcal{I}, \mathcal{F}$, we have $\text{Tr} \vdash \{[\text{noleak}(y[\tilde{M}], \mathcal{I}, \mathcal{F})]\}$ and $\text{Tr} \vdash \exists \mathcal{I}, (\tilde{M} = \sigma\tilde{i}) \wedge \wedge \mathcal{F}$.

* Terms $M_1$ and $M_2$ may differ when $\text{Conf}'_s$ (for $s \in \{1, 2\}$) occurs in the derivation of

$$ 
\begin{gathered}
E_s, \sigma, \text{event } e(\tilde{M}_s); M', \mathcal{T}, \mu\mathcal{E}v_s \xrightarrow{1} E_s, \sigma, \text{event } e(\tilde{M}'_s); M', \mathcal{T}, \mu\mathcal{E}v_s \\
\text{or of } E_s, (\sigma, \text{event } e(\tilde{M}_s); P) :: St_s, Q_s, \text{Or}, \mathcal{T}, \mu\mathcal{E}v_s \xrightarrow{1} \\
E_s, (\sigma, \text{event } e(\tilde{M}'_s); P) :: St_s, Q_s, \text{Or}, \mathcal{T}, \mu\mathcal{E}v_s
\end{gathered}
$$

where the terms $M_s$ match and the only rules above this reduction and under $\text{Conf}'_s$ are (CtxT) with matching simple contexts any number of times followed by (CtxT) with context event $e(a_{s,1}, \dots, a_{s,k-1}, \dots, N_{k+1}, \dots, N_l)$; $N$ or (Ctx) with context event $e(a_{s,1}, \dots, a_{s,k-1}, \dots, N_{k+1}, \dots, N_l)$; $P$ once, where

- a simple context is a context of the form $x[a_1, \dots, a_{k-1}, \dots, N_{k+1}, \dots, N_m]$ or $f(a_1, \dots, a_{k-1}, \dots, N_{k+1}, \dots, N_m)$ for some $x, f, k, m, a_1, \dots, a_{k-1}, N_{k+1}, \dots, N_m$,

- simple contexts $C_s$ (for $s \in \{1, 2\}$) match when $C_s = x[a_{s,1}, \dots, a_{s,k-1}, \dots, N_{k+1}, \dots, N_m]$ or $C_s = f(a_{s,1}, \dots, a_{s,k-1}, \dots, N_{k+1}, \dots, N_m)$ for some $x, f, k, m, a_{s,1}, \dots, a_{s,k-1}, N_{k+1}, \dots, N_m$, and

- terms $M_s$ (for $s \in \{1, 2\}$) match when $M_s = a_{s,0}$, or $M_s = x[a_{s,1}, \dots, a_{s,k-1}, M'_s, N_{k+1}, \dots, N_m]$ or $M_s = f(a_{s,1}, \dots, a_{s,k-1}, M'_s, N_{k+1}, \dots, N_m)$ for some $x, f, k, m, a_{s,0}, a_{s,1}, \dots, a_{s,k-1}, N_{k+1}, \dots, N_m$ and matching $M'_s$.

* Terms $M_1$ and $M_2$ (resp. processes $P_1$ and $P_2$) may differ when

$$ 
\begin{gathered}
M_s = C_1[\dots C_k[\text{event } e(\tilde{M}_s); M']\dots], \\
P_s = C_0[C_1[\dots C_k[\text{event } e(\tilde{M}_s); M']\dots]], \\
\text{or } P_s = \text{event } e(\tilde{M}_s); P
\end{gathered}
$$

where $k \in \mathbb{N}$, $C_1, \dots, C_k$ are term contexts defined in Figure 7, $C_0$ is a process context defined in Figure 12, and the terms $\tilde{M}_s$ match, for $s \in \{1, 2\}$.

* Arguments of events in $\mu\mathcal{E}v_1$ and $\mu\mathcal{E}v_2$ may differ.
* The events $S$ and $\bar{S}$ are swapped: when $\mu\mathcal{E}v_1$ contains $S$, $\mu\mathcal{E}v_2$ contains $\bar{S}$, and conversely.

* Some additional configurations corresponding to the execution $Q_{sp}$ differ.

The proof can be sketched as follows. The different choice of $b$ leads to $E_1(b) = \text{true}$ and $E_2(b) = \text{false}$. The only semantic rule that reads the environment is (Var), when it evaluates an occurrence of the variable in question. By Definition 7, $b \notin \text{var}(Q_0) \cup V$, so the only occurrences of $b$ are in $Q_{sp}$.

If the adversary calls oracle $O_s[\dots](\tilde{a})$ and $x[\tilde{a}]$ is not defined, then $Q_{sp}$ simply yields. If the adversary calls oracle $O_s[\dots](\tilde{a})$ and $x[\tilde{a}]$ is defined, then $\tilde{a} = \tilde{a}_j$ for some $j \in \text{Tidx}(\text{Tr})$. In set 1, $E_1(b) = \text{true}$, so $Q_{sp}$ returns $E_1(x[\tilde{a}_j]) = E_1(z_j[\tilde{b}_j]) = v_j$. In set 2, $E_2(b) = \text{false}$, so when it is the first time that the adversary calls oracle $O_s[\dots](\tilde{a})$ and $x[\tilde{a}]$ is defined, $Q_{sp}$ chooses a fresh $y[j]$ equal to $v_j$, and returns $E_2(y[j]) = v_j$; when the adversary calls again $O_s[\dots](\tilde{a})$, $Q_{sp}$ finds $u'_s = j$ (by construction of $\text{Tidx}(\text{Tr}))$, and returns $E_2(y[j]) = v_j$. So in both sets, $Q_{sp}$ returns the same value.

If the adversary calls $O'_s(b')$, then the result of the test $b' = b$ differs between set 1 and set 2, since $E_1(b) \neq E_2(b)$, so if set 1 executes $S$, then set 2 executes $\bar{S}$ and conversely. That is why the events $S$ and $\bar{S}$ are swapped.

By Definition 7, $u'_s, y \notin \text{var}(Q_0) \cup V$, so the only occurrences of $u'_s$ and $y$ are in $Q_{sp}$. Therefore, the changes that come from differences in the definition of $u'_s$ and $y$ are already taken into account above.

The value of $E_1(z_j[\tilde{b}_j])$ is different from the one of $E_2(z_j[\tilde{b}_j])$. Since $\text{Tr} \vdash \text{sp}$, we have $\text{Tr} \vdash \{[\text{prove}^{1\text{-ses.secr.}(x)}(\mu_j)]\}$, so $\text{Tr} \vdash \{[\text{noleak}(\theta z_j[\tilde{M}_j], \{\theta I_{\mu_j}\}, \theta \mathcal{F}_{\mu_j})]\}$ where $\theta$ is a renaming of $I_{\mu_j}$ to fresh replication indices. We have $\sigma_{\text{Conf}_j} = [I_{\mu_j} \mapsto \tilde{a}_j]$. Let $\rho = \{\theta I_{\mu_j} \mapsto \tilde{a}_j\}$. By Corollary 3, $\text{Tr}, \rho \vdash \theta \mathcal{F}_{\mu_j}$. Moreover, $\text{Tr}, \rho \vdash \theta \tilde{M}_j = \tilde{b}_j$. So $\text{Tr} \vdash \exists \theta I_{\mu_j}, (\theta \tilde{M}_j = \tilde{b}_j) \wedge \theta \mathcal{F}_{\mu_j}$. Hence, for $\tilde{M} = \theta \tilde{M}_j$, $\mathcal{I} = \{\theta I_{\mu_j}\}$, and $\mathcal{F} = \theta \mathcal{F}_{\mu_j}$, we have $\text{Tr} \vdash \{[\text{noleak}(z_j[\tilde{M}], \mathcal{I}, \mathcal{F})]\}$ and $\text{Tr} \vdash \exists \mathcal{I}, (\tilde{M} = \tilde{b}_j) \wedge \mathcal{I}$. $\mathcal{F}$.

The difference between $E_1(z[\tilde{a}])$ and $E_2(z[\tilde{a}])$ for $z$ and $\tilde{a}$ such that for some $\tilde{M}, \mathcal{I}, \mathcal{F}$, we have $\text{Tr} \vdash \{[\text{noleak}(z[\tilde{M}], \mathcal{I}, \mathcal{F})]\}$ and $\text{Tr} \vdash \exists \mathcal{I}, (\tilde{M} = \tilde{a}) \wedge \mathcal{I}$. $\mathcal{F}$ has consequences when (Var) evaluates $z[\tilde{a}]$:

$$E_s, \sigma, \mu z[\tilde{a}], \mathcal{T}, \mu\mathcal{E}v_s \xrightarrow{1} E_s, \sigma, E_s(z[\tilde{a}]), \mathcal{T}, \mu\mathcal{E}v_s.$$

By Lemma 8, Property 4 applied to the configuration $\text{Conf} = E_s, \sigma, \mu z[\tilde{a}], \mathcal{T}, \mu\mathcal{E}v_s$ with $l = 0$, we have

$$E'_s, \sigma, \mu z[\tilde{M}'], \mathcal{T}', \mu\mathcal{E}v'_s \xrightarrow{1} E_s, \sigma, \mu z[\tilde{a}], \mathcal{T}, \mu\mathcal{E}v_s$$

by any number of applications of (CtxT), where $\mu z[\tilde{M}']$ is a subterm of $C[C_{sp}[Q_0]]$. Furthermore, if the evaluation of $\tilde{M}'$ itself uses (Var) that evaluates a $z[\tilde{a}]$ that differs, we replace $z[\tilde{M}']$ by the smallest subterm of $\tilde{M}'$ that evaluates a $z[\tilde{a}]$ that differs. By this replacement, we guarantee that the evaluation of $\tilde{M}'$ proceeds in the same way in set 1 and set 2 and yields the same $\tilde{a}$. Recall that $\tilde{M}'$ are simple terms by Invariants 2 and 5, so the evaluation of $\tilde{M}'$ does not change $E_s, \mathcal{T}, \mu\mathcal{E}v_s$. So we have

$$E_s, \sigma, \mu z[\tilde{M}'], \mathcal{T}, \mu\mathcal{E}v_s \xrightarrow{1} E_s, \sigma, \mu z[\tilde{a}], \mathcal{T}, \mu\mathcal{E}v_s \xrightarrow{1} E_s, \sigma, E_s(z[\tilde{a}]), \mathcal{T}, \mu\mathcal{E}v_s$$

for $s \in \{1, 2\}$, where $\mu z[\tilde{M}']$ is a subterm of $C[C_{sp}[Q_0]]$, by any number of applications of (CtxT) followed by one application of (Var). Let $\theta$ be a renaming of $I_\mu$ to fresh replication indices and $\rho = \{\theta I_\mu \mapsto \sigma I_\mu\}$. By Corollary 3, $\text{Tr}_s, \rho \vdash \theta \mathcal{F}_\mu$. Moreover, $E_s, \sigma, \tilde{M}' \vdash \tilde{a}$, so $E_s, \rho, \theta \tilde{M}' \vdash \tilde{a}$. Since $E_{\text{Tr}_s}$ extends $E_s$, we have $\text{Tr}_s, \rho \vdash \theta \tilde{M}' = \tilde{a}$. Since $\text{Tr}$ is among the traces $\text{Tr}_s$, we have
$Tr, \rho \vdash \theta \mathcal{F}_{\mu}$ and $Tr, \rho \vdash \theta \tilde{M}' = \tilde{a}$. There exists $\rho'$ with domain $\mathcal{I}$ such that $Tr, \rho' \vdash (\tilde{M} = \tilde{a}) \wedge \wedge \mathcal{F}$. So $Tr, \rho \cup \rho' \vdash (\mathcal{F} \cup \theta \mathcal{F}_{\mu} \cup \{\theta \tilde{M}' = \tilde{a}, \tilde{M} = \tilde{a}\})$. Since $Tr \vdash \{\text{noleak}(z[\tilde{M}], \mathcal{I}, \mathcal{F})\}$ and $Tr \vdash \exists \mathcal{I}, (\tilde{M} = \tilde{a}) \wedge \wedge \mathcal{F}$, we have $Tr \vdash \neg (\forall \mathcal{I}, \neg \wedge \mathcal{F})$, so $Tr$ satisfies the second disjunct of $\{\text{noleak}(z[\tilde{M}], \mathcal{I}, \mathcal{F})\}$. Therefore, $z \notin V$, so the occurrence of $^{\mu}z[\tilde{M}']$ evaluated above is either in $Q_{sp}$, and in this case $z$ is actually $x$ and this case has already been studied above, or in $Q_0$. In the latter situation, we are in one of the following three cases:

* $^{\mu}z[\tilde{M}']$ is in $M$ in an assignment $^{\mu'}$let $y[\tilde{i}] = M$ in $Q_0$, $M$ is built from replication indices, variables, function applications, and conditionals and $Tr \vdash \{\text{noleak}(y[\theta \tilde{i}], \mathcal{I} \cup \{\theta \tilde{i}\}, \mathcal{F} \cup \theta \mathcal{F}_{\mu} \cup \{\theta \tilde{M}' = \tilde{M}\})\}$ where $\theta$ is a renaming of $\tilde{i}$ to fresh replication indices. Let $\tilde{M}'' = \theta \tilde{i}$, $\mathcal{I}' = \mathcal{I} \cup \{\theta \tilde{i}\}$, and $\mathcal{F}' = \mathcal{F} \cup \theta \mathcal{F}_{\mu} \cup \{\theta \tilde{M}' = \tilde{M}\}$. Since $\mu'$ is above $\mu$, by Lemma 6, there is a configuration inside $\mu'$ before Conf in $Tr$. By Lemma 8 applied to that configuration (Property 1 when the assignment is a process, Property 4 with $l = 0$ when it is a term), the assignment $^{\mu'}$let $y[\tilde{i}] = M$ is evaluated by

$$ 
\begin{array}{l}
E_s, \sigma, ^{\mu'} \text{let } y[\tilde{i}] = M \text{ in } M', \mathcal{T}, \mu \mathcal{E} v_s \xrightarrow{1}^* E_s[y[\sigma \tilde{i}] \mapsto a_s], \sigma, M', \mathcal{T}, \mu \mathcal{E} v_s \\
\text{or } E_s, (\sigma, ^{\mu'} \text{let } y[\tilde{i}] = M \text{ in } P) :: St_s, Q_s, \text{Or}, \mathcal{T}, \mu \mathcal{E} v_s \xrightarrow{1}^* \\
\qquad E_s[y[\sigma \tilde{i}] \mapsto a_s], (\sigma, P) :: St_s, Q_s, \text{Or}, \mathcal{T}, \mu \mathcal{E} v_s
\end{array}
$$

for $s \in \{1, 2\}$. We have $Tr \vdash \{\text{noleak}(y[\tilde{M}''], \mathcal{I}', \mathcal{F}')\}$. Moreover $\tilde{i} = I_{\mu}$ and $Tr, \rho \cup \rho' \vdash \theta \tilde{i} = \sigma \tilde{i}$ by definition of $\rho$. Hence $Tr, \rho \cup \rho' \vdash \tilde{M}'' = \sigma \tilde{i}$ and $Tr, \rho \cup \rho' \vdash \mathcal{F}',$ so $Tr \vdash \exists \mathcal{I}', (\tilde{M}'' = \sigma \tilde{i}) \wedge \wedge \mathcal{F}'$. Hence we are in a case in which different values inside terms $M_1$ and $M_2$ are allowed. Furthermore, the added values $E_s(y[\sigma \tilde{i}]) = a_s$ may differ. Let $\tilde{a}' = \sigma \tilde{i}$. We have $Tr \vdash \{\text{noleak}(y[\tilde{M}''], \mathcal{I}', \mathcal{F}')\}$ and $Tr \vdash \exists \mathcal{I}', (\tilde{M}'' = \tilde{a}') \wedge \wedge \mathcal{F}',$ so $E_1(y[\tilde{a}'])$ is indeed allowed to differ from $E_2(y[\tilde{a}'])$.

* $^{\mu}z[\tilde{M}']$ is in $^{\mu'}$event $e(M_1, \dots, M_{k-1}, C[^{\mu}z[\tilde{M}']], M_{k+1}, \dots, M_m)$ in $Q_0$, for $C$ defined in Figure 22. Since $\mu'$ is above $\mu$, by Lemma 6, there is a configuration inside $\mu'$ before Conf in $Tr$. By Lemma 8 applied to that configuration (Property 1 when the event is a process, Property 4 with $l = 0$ when it is a term), the evaluation of the event starts from a configuration at $\mu'$ in $Tr$. The evaluation of event $e(M_1, \dots, M_{k-1}, C[^{\mu}z[\tilde{M}']], M_{k+1}, \dots, M_m)$ first evaluates $M_1, \dots, M_{k-1}$ to values using (CtxT) or (Context) with an event context. (If they evaluated to abort event values, $C[^{\mu}z[\tilde{M}']]$ would not be evaluated.) Then if evaluates the context $C: y[\tilde{i}] \stackrel{R}{\rightleftharpoons} T; C$ is evaluated by (NewT), let $y[\tilde{i}] = M$ in $C$ is evaluated by (LetT), if $M$ then $C$ else $N'$ is evaluated by (IfT1) ($M$ must evaluate to true because otherwise, $^{\mu}z[\tilde{M}']$ would not be evaluated), if $M$ then $N$ else $C$ is evaluated by (IfT2) ($M$ must not evaluate to true because otherwise, $^{\mu}z[\tilde{M}']$ would not be evaluated), event $e(\tilde{M})$; $C$ is evaluated by (EventT), and find contexts are evaluated by rules for find, until we reach

$$ \text{event } e(a_{s,1}, \dots, a_{s,k-1}, C_{s,1}[\dots C_{s,l}[^{\mu}z[\tilde{M}']][\dots]], M_{k+1}, \dots, M_m) $$

for $s \in \{1, 2\}$, where $C_{s,1}, \dots, C_{s,l}$ are matching simple contexts. (Values may differ in case $M_1, \dots, M_{k-1}$, or terms in $C$ contain other occurrences of variables whose value differs.) At this point, the reduction proceeds as follows:

$$ 
\begin{array}{l}
E_s, \sigma, \text{event } e(\tilde{M}_s); M', \mathcal{T}, \mu \mathcal{E} v_s \xrightarrow{1} E_s, \sigma, \text{event } e(\tilde{M}'_s); M', \mathcal{T}, \mu \mathcal{E} v_s \\
\text{or } E_s, (\sigma, \text{event } e(\tilde{M}_s); P), Q_s, \text{Or}, \mathcal{T}, \mu \mathcal{E} v_s \xrightarrow{1} E_s, (\sigma, \text{event } e(\tilde{M}'_s); P), Q_s, \text{Or}, \mathcal{T}, \mu \mathcal{E} v_s
\end{array}
$$
by (Var), (CtxT) with matching simple contexts any number of times followed by (CtxT) or (Ctx) with context **event** $e(a_{s,1}, \dots, a_{s,k-1}, \dots, M_{k+1}, \dots, M_m)$; ... once, where

$$ \begin{align*} \widetilde{M}_s &= a_{s,1}, \dots, a_{s,k-1}, C_{s,1}[\dots C_{s,l}[\mu z[\widetilde{M}']]\dots], M_{k+1}, \dots, M_m \\ \text{and } \widetilde{M}'_s &= a_{s,1}, \dots, a_{s,k-1}, C_{s,1}[\dots C_{s,l}[a_s]\dots], M_{k+1}, \dots, M_m \end{align*} $$

for $s \in \{1, 2\}$. Further reductions still manipulate configurations of the same form until the event itself is executed by (EventT) or (Event), which adds the event $e$ with possibly different arguments to $\mu\mathcal{E}v_s$.

* $\mathrm{Tr} \vdash \forall (\mathcal{I} \cup \theta I_\mu), \neg \bigwedge (\mathcal{F} \cup \theta \mathcal{F}_\mu \cup \{\theta \widetilde{M}' = \widetilde{M}\})$ where $\theta$ is a renaming of $I_\mu$ to fresh replication indices. We have $\mathrm{Tr}, \rho \cup \rho' \vdash \neg \bigwedge (\mathcal{F} \cup \theta \mathcal{F}_\mu \cup \{\theta \widetilde{M}' = \widetilde{M}\})$. That yields a contradiction, so this case does not happen.

The sequence of events $\mu\mathcal{E}v_1$ (resp. $\mu\mathcal{E}v_2$) is never read by the semantic rules. It is only read by the distinguisher. Therefore, changes in this sequence of events do not modify the rest of the trace.

That concludes the proof that traces in set 1 and set 2 match.

Furthermore, the trace in set 1 and the traces in set 2 have the same probability. All full traces of $C[C_{sp}[Q_0]]$ for attacker $\mathcal{A}$ that define $b$ and that satisfy sp belong to set 1 or to set 2 for some $\mathrm{Tr}$ (for instance using the trace in question as $\mathrm{Tr}$). Therefore, these sets form a partition of the full traces of $C[C_{sp}[Q_0]]$ for attacker $\mathcal{A}$ that define $b$ and that satisfy sp, and the sets that execute $\mathcal{S}$ have the same probability as the sets that execute $\mathcal{S}$. Moreover, the traces of $C[C_{sp}[Q_0]]$ that do not define $b$ execute neither $\mathcal{S}$ nor $\mathcal{S}$. So $\mathrm{Pr}^A[C[C_{sp}[Q_0]] : \mathcal{S} \wedge \mathrm{sp}] = \mathrm{Pr}^A[C[C_{sp}[Q_0]] : \mathcal{S} \wedge \mathrm{sp}]$. $\square$

**Proof of the case** sp = bit secr.(x) Let Tr be a full trace of $C[C_{sp}[Q_0]]$ for attacker $\mathcal{A}$ such that Tr $\vdash$ sp. Let $E = E_{Tr}$.

If $\mathrm{Tidx}(Tr) = \emptyset$, then Tr executes neither $\mathcal{S}$ nor $\mathcal{S}$.

Otherwise, $\mathrm{Tidx}(Tr) = \{\epsilon\}$ and $x$ is defined in $Tr$, that is, $x \in \mathrm{Dom}(E)$. Let $\mathrm{Conf}_\epsilon$ be the target configuration of the semantic rule that adds $x$ to $E$, and $\mu_\epsilon$ be such that $x$ is defined just before $\mu_\epsilon$ in $Tr$. So $\mathrm{Conf}_\epsilon$ is at program point $\mu_\epsilon$ in $Tr$. Let $z_\epsilon[\widetilde{M}_\epsilon] = \mathrm{defRand}_{\mu_\epsilon}(x)$ (which is always defined since $\mu_\epsilon \in \mathrm{Tpp}(Tr)$ and $Tr \vdash$ sp, so $Tr \vdash \{[\mathrm{prove}^{1\text{-ses.secr.}(x)}(\mu_\epsilon)]\}$). Let $\tilde{b}_\epsilon$ be such that $E, \emptyset, \widetilde{M}_\epsilon \downarrow \tilde{b}_\epsilon$. Then $x$ is added to the environment $E$ by (NewT), (LetT), (New), or (Let), we have $E(x) = E(z_\epsilon[\tilde{b}_\epsilon])$, and $z_\epsilon[\tilde{b}_\epsilon]$ is chosen at random by (NewT) or (New) in $Tr$ by definition of $\mathrm{defRand}_{\mu_\epsilon}(x)$.

Let us consider the following two traces:

1. $Tr_1$ is $Tr$ modified by choosing $z_\epsilon[\tilde{b}_\epsilon] = \text{true}$.

2. $Tr_2$ is $Tr$ modified by choosing $z_\epsilon[\tilde{b}_\epsilon] = \text{false}$.

The trace $Tr$ is one of these two traces: just choose the value $z_\epsilon[\tilde{b}_\epsilon]$ that is used in $Tr$.

We show by induction on the derivation of these traces $Tr_s$ that they have matching configurations $\mathrm{Conf}'_s = E_s, \sigma, M_s, \mathcal{T}, \mu\mathcal{E}v_s, \mathrm{Conf}'_s = Q_s, \mathcal{O}r, \text{or } \mathrm{Conf}'_s = E_s, (\sigma, P_s) :: St_s, Q_s, \mathcal{O}r, \mathcal{T}, \mu\mathcal{E}v_s$ for $s \in \{1, 2\}$ that differ as follows:

* $E_1(z[\tilde{a}])$ differs from $E_2(z[\tilde{a}])$ for some $z$ and $\tilde{a}$ such that for some $\widetilde{M}, \mathcal{I}, \mathcal{F}$, we have $Tr \vdash \{[\mathrm{noleak}(z[\widetilde{M}], \mathcal{I}, \mathcal{F})]\}$ and $Tr \vdash \exists \mathcal{I}, (\widetilde{M} = \tilde{a}) \wedge \wedge \mathcal{F}$.
* Values inside $M_1$ and $M_2$ may differ when $Conf'_s$ (for $s \in \{1, 2\}$) occurs in the derivation of

$$ 
\begin{aligned}
E_s, \sigma, \text{let } y[\tilde{i}] &= M \text{ in } M', \mathcal{T}, \mu\mathcal{E}v_s \xrightarrow{1^*} E_s[y[\sigma\tilde{i}] \mapsto a_s], \sigma, M', \mathcal{T}, \mu\mathcal{E}v_s \\
\text{or of } E_s, (\sigma, \text{let } y[\tilde{i}] = M \text{ in } P) &:: St_s, Q_s, \mathcal{O}r, \mathcal{T}, \mu\mathcal{E}v_s \xrightarrow{1^*} \\
E_s[y[\sigma\tilde{i}] \mapsto a_s], (\sigma, P) &:: St_s, Q_s, \mathcal{O}r, \mathcal{T}, \mu\mathcal{E}v_s
\end{aligned}
$$

where $M$ is built from replication indices, variables, function applications, and conditionals and for some $\tilde{M}, \mathcal{I}, \mathcal{F}$, we have $\mathrm{Tr} \vdash [[\mathrm{noleak}(y[\tilde{M}], \mathcal{I}, \mathcal{F})]]$ and $\mathrm{Tr} \vdash \exists \mathcal{I}, (\tilde{M} = \sigma\tilde{i}) \wedge \mathcal{F}$.

* Terms $M_1$ and $M_2$ may differ when $Conf'_s$ (for $s \in \{1, 2\}$) occurs in the derivation of

$$ 
\begin{aligned}
E_s, \sigma, \text{event } e(\tilde{M}_s); M', \mathcal{T}, \mu\mathcal{E}v_s &\xrightarrow{1} E_s, \sigma, \text{event } e(\tilde{M}'_s); M', \mathcal{T}, \mu\mathcal{E}v_s \\
\text{or of } E_s, (\sigma, \text{event } e(\tilde{M}_s); P) &:: St_s, Q_s, \mathcal{O}r, \mathcal{T}, \mu\mathcal{E}v_s \xrightarrow{1} \\
E_s, (\sigma, \text{event } e(\tilde{M}'_s); P) &:: St_s, Q_s, \mathcal{O}r, \mathcal{T}, \mu\mathcal{E}v_s
\end{aligned}
$$

where the terms $M_s$ match and the only rules above this reduction and under $Conf'_s$ are (CtxT) with matching simple contexts any number of times followed by (CtxT) with context event $e(a_{s,1}, \dots, a_{s,k-1}, \dots, N_{k+1}, \dots, N_l)$; $N$ or (Ctx) with context event $e(a_{s,1}, \dots, a_{s,k-1}, \dots, N_{k+1}, \dots, N_l)$; $P$ once, where simple contexts and matching are defined as in the cases $sp = \text{1-ses.secr}(x)$ and $sp = \text{Secrecy}(x)$.

* Terms $M_1$ and $M_2$ (resp. processes $P_1$ and $P_2$) may differ when

$$ 
\begin{aligned}
M_s &= C_1[\dots C_k[\text{event } e(\tilde{M}_s); M']\dots], \\
P_s &= C_0[C_1[\dots C_k[\text{event } e(\tilde{M}_s); M']\dots]], \\
\text{or } P_s &= \text{event } e(\tilde{M}_s); P
\end{aligned}
$$

where $k \in \mathbb{N}$, $C_1, \dots, C_k$ are term contexts defined in Figure 7, $C_0$ is a process context defined in Figure 12, and the terms $\tilde{M}_s$ match, for $s \in \{1, 2\}$.

* Arguments of events in $\mu\mathcal{E}v_1$ and $\mu\mathcal{E}v_2$ may differ.

* The events $S$ and $\bar{S}$ are swapped: when $\mu\mathcal{E}v_1$ contains $S$, $\mu\mathcal{E}v_2$ contains $\bar{S}$, and conversely.

* Some additional configurations corresponding to the execution $Q_{sp}$ differ.

The proof can be sketched as follows.

If the adversary calls $O''_s(b')$, either directly with rule (AttIO) or through the context with rule (OracleCall), then $x$ is defined (since $\mathrm{Tidx}(\mathrm{Tr}) = \{\epsilon\}$) and the result of the test $x = b'$ differs between $\mathrm{Tr}_1$ and $\mathrm{Tr}_2$, since $E_1(x) = E_1(z_\epsilon[\tilde{b}_\epsilon]) = \text{true} \neq E_2(x) = E_2(z_\epsilon[\tilde{b}_\epsilon]) = \text{false}$, so if $\mathrm{Tr}_1$ executes $S$, then $\mathrm{Tr}_2$ executes $\bar{S}$ and conversely. That is why the events $S$ and $\bar{S}$ are swapped.

The value of $E_1(z_\epsilon[\tilde{b}_\epsilon])$ is different from the one of $E_2(z_\epsilon[\tilde{b}_\epsilon])$. Since $\mathrm{Tr} \vdash sp$, we have $\mathrm{Tr} \vdash [[\mathrm{prove}^{\text{1-ses.secr}(x)}(\mu_\epsilon)]]$, so $\mathrm{Tr} \vdash [[\mathrm{noleak}(\theta z_\epsilon[\tilde{M}_\epsilon], \{\theta I_{\mu_\epsilon}\}, \theta \mathcal{F}_{\mu_\epsilon})]]$ where $\theta$ is a renaming of $I_{\mu_\epsilon}$ to fresh replication indices. Here, $I_{\mu_\epsilon}$ is empty since $x$ is defined under no replication. We have $\sigma_{\mathrm{Conf}_\epsilon} = \emptyset$. Let $\rho = \emptyset$. By Corollary 3, $\mathrm{Tr}, \rho \vdash \theta \mathcal{F}_{\mu_\epsilon}$. Moreover, $\mathrm{Tr}, \rho \vdash \theta \tilde{M}_\epsilon = \tilde{b}_\epsilon$. So $\mathrm{Tr} \vdash \exists \theta I_{\mu_\epsilon}, (\theta \tilde{M}_\epsilon = \tilde{b}_\epsilon) \wedge \mathcal{F} \theta \mathcal{F}_{\mu_\epsilon}$. Hence, for $\tilde{M} = \theta \tilde{M}_\epsilon, \mathcal{I} = \{\theta I_{\mu_\epsilon}\}$, and $\mathcal{F} = \theta \mathcal{F}_{\mu_\epsilon}$, we have $\mathrm{Tr} \vdash [[\mathrm{noleak}(z_\epsilon[\tilde{M}], \mathcal{I}, \mathcal{F})]]$ and $\mathrm{Tr} \vdash \exists \mathcal{I}, (\tilde{M} = \tilde{b}_\epsilon) \wedge \mathcal{F}$.
The difference between $E_1(z[\tilde{a}])$ and $E_2(z[\tilde{a}])$ for $z$ and $\tilde{a}$ such that for some $\tilde{M}, \mathcal{I}, \mathcal{F}$, we have $\mathrm{Tr} \vdash \{[\mathrm{noleak}(z[\tilde{M}], \mathcal{I}, \mathcal{F})]\}$ and $\mathrm{Tr} \vdash \exists \mathcal{I}, (\tilde{M} = \tilde{a}) \wedge \mathcal{F}$ has consequences when (Var) evaluates $z[\tilde{a}]$, as in the cases $sp = \mathbf{1-ses.secr.}(x)$ and $sp = \mathbf{Secrecy}(x)$. That concludes the proof that traces $\mathrm{Tr}_1$ and $\mathrm{Tr}_2$ match.

Furthermore, the traces $\mathrm{Tr}_1$ and $\mathrm{Tr}_2$ have the same probability. All full traces of $C[C_{sp}[Q_0]]$ for attacker $\mathcal{A}$ such that Tidx is non-empty and that satisfy $sp$ are $\mathrm{Tr}_1$ or $\mathrm{Tr}_2$ for some $\mathrm{Tr}$ (for instance using the trace in question as $\mathrm{Tr}$). Therefore, $\mathrm{Tr}_1$ and $\mathrm{Tr}_2$ form a partition of the full traces of $C[C_{sp}[Q_0]]$ for attacker $\mathcal{A}$ such that Tidx is non-empty and that satisfy $sp$, and half of these traces execute $\mathcal{S}$, the other half execute $\bar{\mathcal{S}}$. Moreover, the traces of $C[C_{sp}[Q_0]]$ such that Tidx is empty execute neither $\mathcal{S}$ nor $\bar{\mathcal{S}}$. So $\mathrm{Pr}^A[C[C_{sp}[Q_0]] : \mathcal{S} \wedge sp] = \mathrm{Pr}^A[C[C_{sp}[Q_0]] : \bar{\mathcal{S}} \wedge sp]$. $\square$

**Proof of Proposition 1** Let $sp$ be $\mathbf{1-ses.secr.}(x)$, $\mathbf{Secrecy}(x)$, or bit $\mathbf{secr.}(x)$. Let $C$ be an evaluation context acceptable for $C_{sp}[Q_0]$ with public variables $V$ ($x \notin V$) that does not contain $\mathcal{S}$ nor $\bar{\mathcal{S}}$ and $\mathcal{A}$ be an attacker in $\mathcal{BB}$. We have

$$
\begin{align*}
\mathrm{Adv}_{Q_0}^{sp}(\mathcal{A}, C) &= \mathrm{Pr}^A[C[C_{sp}[Q_0]] : \mathcal{S}] - \mathrm{Pr}^A[C[C_{sp}[Q_0]] : \bar{\mathcal{S}}] \\
&= \mathrm{Pr}^A[C[C_{sp}[Q_0]] : \mathcal{S} \wedge sp] + \mathrm{Pr}^A[C[C_{sp}[Q_0]] : \mathcal{S} \wedge \neg sp] \\
&\quad - \mathrm{Pr}^A[C[C_{sp}[Q_0]] : \bar{\mathcal{S}} \wedge sp] - \mathrm{Pr}^A[C[C_{sp}[Q_0]] : \bar{\mathcal{S}} \wedge \neg sp] \\
&= \mathrm{Pr}^A[C[C_{sp}[Q_0]] : \mathcal{S} \wedge \neg sp] - \mathrm{Pr}^A[C[C_{sp}[Q_0]] : \bar{\mathcal{S}} \wedge \neg sp] \quad \text{by Lemma 36} \\
&\le \mathrm{Pr}^A[C[C_{sp}[Q_0]] : \neg sp] \\
&\le \mathrm{Pr}^A[C[C_{sp}[Q_0]] : \neg \{[\mathrm{prove}^{sp}(\{\mu \mid \mu \text{ follows a definition of } x\})]\}] \\
&\quad \text{because, for all } \mathrm{Tr}, \mathrm{Tpp}(\mathrm{Tr}) \subseteq \{\mu \mid \mu \text{ follows a definition of } x\} \\
&\le \mathrm{Pr}^A[C[C_{sp}[Q_0]] : \le \{[\mathrm{prove}^{sp}(\{\mu \mid \mu \text{ follows a definition of } x\})]\}] \quad \text{by Lemma 1} \\
&\le p(\mathcal{A}, C[C_{sp}[]]) = p'(\mathcal{A}, C)
\end{align*}
$$

So $Q_0$ satisfies $sp$ with public variables $V$ up to probability $p'$. Moreover,

$$
\begin{align*}
\mathrm{Adv}_{Q_0}(\mathcal{A}, C[C_{sp}[], sp, D_{\mathrm{false}}]) &= \mathrm{Pr}^A[C[C_{sp}[Q_0]] : \mathcal{S}] - \mathrm{Pr}^A[C[C_{sp}[Q_0]] : \bar{\mathcal{S}} \lor \mathrm{NonUnique}_{Q_0}] \\
&\le \mathrm{Adv}_{Q_0}^{sp}(\mathcal{A}, C) \le p(\mathcal{A}, C[C_{sp}[]])
\end{align*}
$$

so $\mathrm{Bound}_{Q_0}(V \cup \{x\}, sp, D_{\mathrm{false}}, p)$. $\square$

<figure><img src="image_13.png" /></figure>

**Example 5** As we shall see in Example 10, the oracle definition $Q_0$ of Example 1 can be transformed into the following oracle definition $Q_0''$:

$$Q_0'' = \mathrm{Start}() := x_k \stackrel{R}{\leftarrow} T_k; x_{mk} \stackrel{R}{\leftarrow} T_{mk}; \mathrm{return} (); (Q_A'' | Q_B'')$$

$$
\begin{align*}
Q_A'' &= \text{foreach } i \le n \text{ do } O_A[i]() := x_k' \stackrel{R}{\leftarrow} T_k; x_r \stackrel{R}{\leftarrow} T_r; \\
\text{let } x_m &\text{ : bitstring} = \text{enc}'(Z_k, x_k, x_r) \text{ in} \\
&\text{return } (x_m, \text{mac}'(x_m, x_{mk}))
\end{align*}
$$

$$
\begin{align*}
Q_B'' &= \text{foreach } i' \le n \text{ do } O_B[i'](x'_m, x_{ma}) := \\
&\quad \text{find } u \le n \text{ suchthat } \mathrm{defined}(x_m[u], x'_k[u]) \wedge \\
&\quad x'_m = x_m[u] \wedge \mathrm{verify}'(x'_m, x_{mk}, x_{ma}) \text{ then} \\
\text{let } x_k'' &:= T_k = x'_k[u] \text{ in return ()}
\end{align*}
$$
and $Q_0 \stackrel{x_k''}{\approx} Q_0''$. In order to prove the one-session secrecy of $x_k''$, we notice that $x_k''$ is defined by let $x_k'' : T_k = x_k'[u]$, the only variable access to $x_k'$ in $Q_0''$ is let $x_k'' : T_k = x_k'[u]$, and $x_k''$ is not used in $Q_0''$. So by Proposition 1, $Q_0''$ satisfies the one-session secrecy of $x_k''$ without public variables up to probability 0. (We have $\text{defRand}_\mu(x_k'') = x_k'[u]$ and $\text{[noleak}(x_k'[u], \mathcal{I}, \mathcal{F})\text{]} = (\forall \mathcal{I}, \neg \bigwedge \mathcal{F}) \lor ((x_k' \notin V) \land \text{[noleak}(x_k''[\theta_i], \mathcal{I}', \mathcal{F}')\text{]}) = \text{true since } x_k' \notin V, x_k'' \notin V$, and $\text{[noleak}(x_k''[\theta_i], \mathcal{I}', \mathcal{F}')\text{]} = (\forall \mathcal{I}', \neg \bigwedge \mathcal{F}') \lor ((x_k'' \notin V) \land \text{true}) = \text{true. So } \text{Pr}^A[C[Q_0''] \le \neg \text{[prove}^{1-\text{ses.secr.}}(x_k'')(S)\text{]}] = 0.)$ By Lemma 21, the oracle definition $Q_0$ of Example 1 also satisfies the one-session secrecy of $x_k''$ without public variables up to probability $p'(A, C) = 2p(A, C[C_{1-\text{ses.secr.}}(x_k'')][], t_S)$. However, this process does not preserve the secrecy of $x_k''$, because the adversary can force several sessions of $B$ to use the same key $x_k''$, by replaying the message sent by $A$. (Accordingly, $\text{prove}^{\text{Secrecy}}(x)(S)$ is not satisfied.)

The criteria given in this section might seem restrictive, but in fact, they should be sufficient for all protocols, provided the previous transformation steps are powerful enough to transform the protocol into a simpler protocol, on which these criteria can then be applied.

## 4.2 Correspondences

### 4.2.1 Example

We illustrate the proof of correspondences on the following example, inspired by the corrected Woo-Lam public key protocol [73]:

$$ 
\begin{aligned}
B &\to A : (N, B) \\
A &\to B : \{pk_A, B, N\}_{sk_A}
\end{aligned}
 $$

This protocol is a simple nonce challenge: $B$ sends to $A$ a fresh nonce $N$ and its identity. $A$ replies by signing the nonce $N$, $B$'s identity, and $A$'s public key (which we use here instead of $A$'s identity for simplicity: this avoids having to relate identities and keys; CryptoVerif can obviously also handle the version with $A$'s identity). The signatures are assumed to be (existentially) unforgeable under chosen message attacks (UF-CMA) [49], so, when $B$ receives the signature, $B$ is convinced that $A$ is present. The signature cannot be a replay because the nonce $N$ is signed.

In our calculus, this protocol is encoded by the following oracle definition $G_0$, explained below:

$$
\begin{align*}
G_0 = O_0() &:= rk_A \stackrel{R}{\leftarrow} \text{keyseed}; \text{let } pk_A = \text{pkgen}(rk_A) \text{ in} \\
&\text{let } sk_A = \text{skgen}(rk_A) \text{ in return } (pk_A); (Q_A | Q_B) \\
Q_A = \text{foreach } i_A \le n \text{ do } O_A[i_A](x_N : \text{nonce}, x_B : \text{host}) := & \\
&\quad \text{event } e_A(pk_A, x_B, x_N); r \stackrel{R}{\leftarrow} \text{seed}; \\
&\quad \text{return } (\text{sign}(\text{concat}(pk_A, x_B, x_N), sk_A, r)) \\
Q_B = \text{foreach } i_B \le n \text{ do } O_{B1}[i_B](x_{pk_A} : \text{pkey}) := N \stackrel{R}{\leftarrow} \text{nonce}; \\
&\quad \text{return } (N, B); O_{B2}[i_B](s : \text{signature}) :=; \\
&\quad \text{if verify}(\text{concat}(x_{pk_A}, B, N), x_{pk_A}, s) \text{ then} \\
&\quad \text{if } x_{pk_A} = pk_A \text{ then event } e_B(x_{pk_A}, B, N)
\end{align*}
$$

The oracle definition $G_0$ is assumed to run in interaction with an adversary, which also models the network. $G_0$ first receives a call to oracle $O_0$ without argument, from the adversary. Then, it chooses randomly with uniform probability a bitstring $rk_A$ in the type `keyseed`, by the construct
$rk_A \stackrel{R}{\leftarrow} keyseed$. Then, $G_0$ generates the public key $pk_A$ corresponding to the coins $rk_A$, by calling the public-key generation algorithm pkgen. Similarly, $G_0$ generates the secret key $sk_A$ by calling skgen. It then returns the public key $pk_A$, so that the adversary has this public key.

After this return the control passes to the adversary. Several oracles are then made available, which represent the roles of A and B in the protocol: the oracle definition $Q_A | Q_B$ is the parallel composition of $Q_A$ and $Q_B$; it makes simultaneously available the oracles defined in $Q_A$ and $Q_B$. Let $Q'_A$ and $Q'_B$ be such that $Q_A = \text{foreach } i_A \le n \text{ do } Q'_A$ and $Q_B = \text{foreach } i_B \le n \text{ do } Q'_B$. The replication $\text{foreach } i_A \le n \text{ do } Q'_A$ represents $n$ copies of the oracle definition $Q'_A$, indexed by the replication index $i_A$. The oracle definition $Q'_A$ begins with oracle $O_A[i_A]$; the oracle is indexed with $i_A$ so that the adversary can choose which copy of oracle $O_A$ it calls by calling $O_A[i_A]$ for the appropriate value of $i_A$. The situation is similar for $Q'_B$, which expects a call to oracle $O_{B1}[i_B]$. The adversary can then run each copy of $Q'_A$ or $Q'_B$ simply by calling the appropriate oracles $O_A[i_A]$ or $O_{B1}[i_B]$.

The oracle definition $Q'_B$ first expects a call to oracle $O_{B1}[i_B]$ with a message $x_{pk_A}$ in the type $pkey$ of public keys. This message is not really part of the protocol. It serves for starting a new session of the protocol, in which B interacts with the participant of public key $x_{pk_A}$. For starting a session between A and B, this message should be $pk_A$. Then, $Q'_B$ chooses randomly with uniform probability a nonce $N$ in the type $nonce$. The type $nonce$ is large: collisions between independent random numbers chosen uniformly in a large type are eliminated by CryptoVerif. $Q'_B$ returns the message $(N, B)$ to the adversary and gives it back control. The attacker is expected to call oracle $O_A[i_A]$ with this message $(N, B)$, but may proceed differently in order to mount an attack against the protocol.

Upon a call to oracle $O_A[i_A]$ with message $(x_N, x_B)$, where the bitstring $x_N$ is in the type $nonce$ and $x_B$ in the type $host$, the process $Q'_A$ executes the event $e_A(pk_A, x_B, x_N)$. This event does not change the state of the system. Events just record that a certain program point has been reached, with certain values of the arguments of the event. Then, $Q'_A$ chooses randomly with uniform probability a bitstring $r$ in the type $seed$; this random bitstring is next used as coins for the signature algorithm. Finally, $Q'_A$ returns the signed message $\{pk_A, x_B, x_N\}_{sk_A}$. (The function concat concatenates its arguments, with information on the length of these arguments, so that the arguments can be recovered from the concatenation.) The control then passes to the attacker, which should call oracle $O_{B2}[i_B]$ with this message if it wishes to run the protocol correctly.

Upon a call to oracle $O_{B2}[i_B]$ with message $s$, $Q'_B$ verifies that the signature $s$ is correct and, if $x_{pk_A} = pk_A$, that is, if B runs a session with A, it executes the event $e_B(x_{pk_A}, B, N)$. Our goal is to prove that, if event $e_B$ is executed, then event $e_A$ has also been executed. However, when B runs a session with a participant other than A, it is perfectly correct that B terminates without event $e_A$ being executed; that is why event $e_B$ is executed only when B runs a session with A.

By the unforgeability of signatures, the signature verification with $pk_A$ succeeds only for signatures generated with $sk_A$. So, when we verify that the signature is correct, we can furthermore check that it has been generated using $sk_A$. So, after game transformations explained below, we obtain the following final game:

$$ 
\begin{array}{l}
G_1 = O_0() := rk_A \stackrel{R}{\leftarrow} keyseed; \\
\text{let } pk_A = \text{pkgen}(rk_A) \text{ in return } (pk_A); (Q_{1A} | Q_{1B})
\end{array}
$$
$$
\begin{align*}
Q_{1A} = \text{foreach } i_A \le n \text{ do } O_A[i_A](x_N : \text{nonce}, x_B : \text{host}) &:= \\
&\quad \text{event } e_A(pk_A, x_B, x_N); \\
&\quad \text{let } m = \text{concat}(pk_A, x_B, x_N) \text{ in} \\
&\quad r \stackrel{R}{\leftarrow} \text{seed; return } (\text{sign}'(m, \text{skgen}'(rk_A), r))
\end{align*}
$$

$$
\begin{align*}
Q_{1B} = \text{foreach } i_B \le n \text{ do } O_{B1}[i_B](x_{pk_A} : pkey) &:= N \stackrel{R}{\leftarrow} \text{nonce;} \\
\text{return } (N, B); O_{B2}[i_B](s : \text{signature}) &:= \\
\text{find } u \le n \text{ suchthat } \begin{array}[t]{@{}l@{}}
\text{defined}(m[u], x_B[u], x_N[u]) \\
\wedge (x_{pk_A} = pk_A) \wedge (B = x_B[u]) \wedge (N = x_N[u]) \\
\wedge \text{verify}'(\text{concat}(x_{pk_A}, B, N), x_{pk_A}, s) \text{ then}
\end{array} \\
\text{event } e_B(x_{pk_A}, B, N))
\end{align*}
$$

The assignment sk<sub>A</sub> = skgen(rk<sub>A</sub>) has been removed and skgen(rk<sub>A</sub>) has been substituted for
sk<sub>A</sub>, in order to make the term sign(m, skgen(rk<sub>A</sub>), r) appear. This term is needed for the
security of the signature scheme to apply.

In $Q_{1A}$, the signed message is stored in variable $m$, and this variable is used when computing
the signature.

Finally, using the unforgeability of signatures, the signature verification has been replaced with an array lookup: the signature verification can succeed only when concat($x_{pk_A}$, $B$, $N$) has been signed with $sk_A$, so we look for the message concat($x_{pk_A}$, $B$, $N$) in the array $m$ and the event $e_B$ is executed only when this message is found. In other words, we look for an index $u \le n$ such that $m[u]$ is defined and $m[u] = \text{concat}(x_{pk_A}, B, N)$. By definition of $m$, $m[u] = \text{concat}(pk_A, x_B[u], x_N[u])$, so the equality $m[u] = \text{concat}(x_{pk_A}, B, N)$ can be replaced with $(x_{pk_A} = pk_A) \wedge (B = x_B[u]) \wedge (N = x_N[u])$. (Recall that the result of the concat function contains enough information to recover its arguments.) This transformation replaces the function symbols pkgen, skgen, sign, and verify with primed function symbols pkgen', skgen', sign', and verify' respectively, to avoid repeated applications of the unforgeability of signatures with the same key. (The unforgeability of signatures is applied only to unprimed symbols.)

The soundness of the game transformations shows that $G_0 \approx G_1$. We will prove that $G_1$ satisfies the correspondences (4) and (6) with any public variables $V$, in particular with $V = \emptyset$. By Lemma 27, $G_0$ also satisfies these correspondences with public variables $V = \emptyset$. Let us sketch how the proof of correspondence (4) for the game $G_1$ will proceed. Let $Q'_{1A}$ and $Q'_{1B}$ such that $Q_{1A} = \text{foreach } i_A \le n \text{ do } Q'_{1A}$ and $Q_{1B} = \text{foreach } i_B \le n \text{ do } Q'_{1B}$. Assume that event $e_B$ is executed in the copy of $Q'_{1B}$ of index $i_B$, that is, $e_B(x_{pk_A}[i_B], B, N[i_B])$ is executed. (Recall that the variables $x_{pk_A}$, $N$, $u$, ... are implicitly arrays.) Then the condition of the find above $e_B$ holds, that is, $m[u[i_B]]$, $x_B[u[i_B]]$, and $x_N[u[i_B]]$ are defined, $x_{pk_A}[i_B] = pk_A$, $B = x_B[u[i_B]]$, and $N[i_B] = x_N[u[i_B]]$. Moreover, since $m[u[i_B]]$ is defined, the assignment that defines $m$ has been executed in the copy of $Q'_{1A}$ of index $i_A = u[i_B]$. Then the event $e_A(pk_A, x_B, x_N)$, located above the definition of $m$, must have been executed in that copy of $Q'_{1A}$, that is, $e_A(pk_A, x_B[u[i_B]], x_N[u[i_B]])$ has been executed. The equalities in the condition of the find imply that this event is also $e_A(x_{pk_A}[i_B], B, N[i_B])$. To sum up, if $e_B(x_{pk_A}[i_B], B, N[i_B])$ has been executed, then $e_A(x_{pk_A}[i_B], B, N[i_B])$ has been executed, so we have the correspondence (4). This reasoning is typical of the way the prover shows correspondences. In particular, the conditions of array lookups are key in these proofs, because they allow us to relate values in processes that run in parallel (here, the processes that represent $A$ and $B$), and interesting correspondences relate events that occur in such processes. Next, we detail and formalize this reasoning, both for non-injective and injective correspondences.
### 4.2.2 Non-unique Events

The only correspondence that involves a non-unique event $e$ is $\text{event}(e) \Rightarrow$ false, and it is simply proved by noticing that the event $e$ no longer occurs in the game after the transformation **prove_unique** (Section 5.1.4). Therefore, non-unique events are not concerned by the proofs of Sections 4.2.3 and 4.2.4.

### 4.2.3 Non-injective Correspondences

Intuitively, in order to prove that $Q_0$ satisfies a non-injective correspondence $\forall \tilde{x} : \tilde{T}; \psi \Rightarrow \exists \tilde{y} : \tilde{T}'; \phi$, with $\tilde{x} = \text{var}(\psi)$ and $\tilde{y} = \text{var}(\phi) \setminus \text{var}(\psi)$, we collect all facts that hold at events in $\psi$ and show that these facts imply $\phi$ using the equational prover.

When $\text{casesInCorresp} = \text{false}$, CryptoVerif uses $\mathcal{F}_\mu$ to collect these facts. When $\text{casesInCorresp} = \text{true}$ (the default), it uses $\mathcal{F}_{\mu,c}$ for more precision. In this section, we detail the proof with $\mathcal{F}_{\mu,c}$. The usage of $\mathcal{F}_\mu$ can be considered as using a single case $c$, relying on Lemma 31 instead of Lemma 32. Formally, we collect facts that hold when the event $F$ in $\psi$ has been executed, as follows.

**Definition 16 (μ executes F, $\mathcal{F}_{F,\mu,c}$)** When $F = \text{event}(e(M_1, \dots, M_m))$ and $\text{μevent } e(M'_1, \dots, M'_m); \dots$ occurs in $Q_0$ or, for $m = 0$, $\text{μevent_abort e}$ or $\text{μfind}[\text{unique}_e] \dots$ occurs in $Q_0$, we say that $\mu$ executes $F$.

If $\mu$ executes $F$ and for all $\text{μevent } e(M'_1, \dots, M'_m); \dots$ in $Q_0$, $M'_1, \dots, M'_m$ are simple terms, then we define $\mathcal{F}_{F,\mu,c}^0 = \mathcal{F}_{\mu,c} \cup \{M'_j = M_j \mid j \le m\} \cup \{\text{lastdefprogrampoint}(\mu, I_\mu) \text{ if } \text{μevent_abort e} \text{ or } \text{μfind}[\text{unique}_e] \dots \text{ occurs in } Q_0\}$. If additionally $F$ is not a non-unique event, then we define $\mathcal{F}_{F,\mu,c} = \mathcal{F}_{F,\mu,c}^0 \cup \mathcal{F}_\mu^{\text{Fut}}$.

Intuitively, when the event $F$ in $\psi$ has been executed, it has been executed by some subterm or subprocess of $Q_0$, so there exists a subterm or subprocess $\text{μevent } e(M'_1, \dots, M'_m); \dots$ or, for $m = 0$, $\text{μevent_abort e}$ or $\text{μfind}[\text{unique}_e] \dots$ in $Q_0$ such that, the event $e(M'_1, \dots, M'_m)$ has been executed and it is equal to the event $F$, hence $M'_j = M_j$ holds for $j \le m$. Moreover, since the program point $\mu$, which executes $F$, has been reached, $\mathcal{F}_{\mu,c}$ holds for some case $c$ (Lemma 32). Furthermore, when the event aborts, it is the last step of the trace, so $\text{lastdefprogrampoint}(\mu, I_\mu)$ also holds. Hence $\mathcal{F}_{F,\mu,c}^0$ holds for some case $c$. Additionally, assuming we consider traces that do not execute non-unique events, since the adversary cannot stop execution of the process until the next return, **yield**, or **event_abort e**, $\mathcal{F}_\mu^{\text{Fut}}$ also holds (Lemma 33), so $\mathcal{F}_{F,\mu,c}$ holds for some case $c$. This is proved more formally in Lemma 38 below. (The case of $\text{get}[\text{unique}_e]$ is not mentioned in Definition 16 because it is excluded by Property 3.)

We restrict ourselves to the case in which $M'_1, \dots, M'_m$ are simple terms because only simple terms allowed in sets of facts.

Let $\theta$ be a substitution equal to the identity on the variables $\tilde{x}$ of $\psi$. This substitution gives values to existentially quantified variables $\tilde{y}$ of $\phi$. We say that $\mathcal{F} \models_{\theta} \phi$ when we can show that $\mathcal{F}$ implies $\theta\phi$. Formally, we define:

$\mathcal{F} \models_{\theta} M$ if and only if $\mathcal{F} \cup \{\neg \theta M\}$ yields a contradiction

$\mathcal{F} \models_{\theta} \text{event}(e(M_1, \dots, M_m))$ if and only if there exist $M'_0, \dots, M'_m$ such that $M'_0 : \text{event}(e(M'_1, \dots, M'_m)) \in \mathcal{F}$ and $\mathcal{F} \cup \{\bigvee_{j=1}^m \theta M_j \neq M'_j\}$ yields a contradiction

$\mathcal{F} \models_{\theta} \phi_1 \wedge \phi_2$ if and only if $\mathcal{F} \models_{\theta} \phi_1$ and $\mathcal{F} \models_{\theta} \phi_2$

$\mathcal{F} \models_{\theta} \phi_1 \vee \phi_2$ if and only if $\mathcal{F} \models_{\theta} \phi_1$ or $\mathcal{F} \models_{\theta} \phi_2$
Terms $\theta M$ are proved by contradiction, using the equational prover. Events $\theta F$ are proved by looking for some event $F'$ in $\mathcal{F}$ and showing by contradiction that $\theta F = F'$, using the equational prover.

Let $\varphi = [\forall \tilde{x} : \tilde{T}; \psi \Rightarrow \exists \tilde{y} : \tilde{T}'; \phi]$ be a non-injective correspondence that does not use non-unique events, with $\psi = F_1 \wedge \dots \wedge F_m$, $\tilde{x} = \text{var}(\psi)$, and $\tilde{y} = \text{var}(\phi) \setminus \text{var}(\psi)$. Suppose that, in $Q_0$, the arguments of the events that occur in $\psi$ are always simple terms. Suppose that, for all $j \le m$, $\mu_j$ that executes $F_j$ and $c_j$ is a case for $\mathcal{F}_{\mu_j, c_j}$. For $j \le m$, let $\theta_j$ be a renaming of $I_{\mu_j}$ to fresh replication indices. (The renamings $\theta_j$ have pairwise disjoint images.) Let $\theta$ be a family parameterized by $\mu_1, c_1, \dots, \mu_m, c_m$ of substitutions equal to the identity on $\tilde{x}$. We define $\text{prove}^{\varphi}(\theta, \mu_1, c_1, \dots, \mu_m, c_m) = (\theta_1 \mathcal{F}_{F_1, \mu_1, c_1} \cup \dots \cup \theta_m \mathcal{F}_{F_m, \mu_m, c_m} \models_{\theta(\mu_1, c_1, \dots, \mu_m, c_m)} \phi)$. This function defines the algorithm that we use to prove the correspondence $\varphi$ assuming for all $j \le m$, $F_j$ is executed in $\mu_j$ and we are in case $c_j$. We also define $\text{prove}^{\varphi}(\theta, S) = \bigwedge_{(\mu_1, c_1, \dots, \mu_m, c_m) \in S} \text{prove}^{\varphi}(\theta, \mu_1, c_1, \dots, \mu_m, c_m)$.

Non-injective correspondences are proved as follows.

**Proposition 2** Let $\varphi = [\forall \tilde{x} : \tilde{T}; \psi \Rightarrow \exists \tilde{y} : \tilde{T}'; \phi]$ be a non-injective correspondence that does not use non-unique events, with $\psi = F_1 \wedge \dots \wedge F_m$, $\tilde{x} = \text{var}(\psi)$, and $\tilde{y} = \text{var}(\phi) \setminus \text{var}(\psi)$. Let $Q_0$ be a process that satisfies Properties 3 and 4. Suppose that, in $Q_0$, the arguments of the events that occur in $\psi$ are always simple terms. Let $S = \{(\mu_1, c_1, \dots, \mu_m, c_m) \mid \forall j \le m, \mu_j \text{ executes } F_j \text{ and } c_j \text{ is a case for } \mathcal{F}_{\mu_j, c_j}\}$. If there exists a family of substitutions $\theta$ equal to the identity on $\tilde{x}$ such that $\text{prove}^{\varphi}(\theta, S)$ and for all $A \in \mathcal{BB}$ and all evaluation contexts $C$ acceptable for $Q_0$, $\text{Pr}^A[C[Q_0] \preceq \neg [[\text{prove}^{\varphi}(\theta, S)]]] \le p(A, C)$, then $\text{Bound}_{Q_0}(V, \varphi, D_{\text{false}}, p)$ for any $V$.

Intuitively, when $\psi = F_1 \wedge \dots \wedge F_m$ holds, $\theta_1 \mathcal{F}_{F_1, \mu_1, c_1} \cup \dots \cup \theta_m \mathcal{F}_{F_m, \mu_m, c_m}$ holds for some $\mu_1, c_1, \dots, \mu_m, c_m$. For some $\theta$ equal to the identity on $\psi$, $\theta_1 \mathcal{F}_{F_1, \mu_1, c_1} \cup \dots \cup \theta_m \mathcal{F}_{F_m, \mu_m, c_m}$ implies $\theta \phi$, so $\theta \phi$ holds. Hence the correspondence is satisfied. The proof of Proposition 2 relies on the following properties and lemmas. We have

$$ \begin{align*} \{\mathcal{F} \models_{\theta} M\} &= \forall \tilde{z} \in \tilde{T}''', \neg (\bigwedge \mathcal{F} \wedge \neg \theta M) \\ \{\mathcal{F} \models_{\theta} \text{event}(e(M_1, \dots, M_m))\} &= \forall \tilde{z} \in \tilde{T}''', \neg (\bigwedge \mathcal{F} \wedge \bigvee_{j=1}^m \theta M_j \neq M_j') \\ \text{for some } M_0' : \text{event}(e(M_1', \dots, M_m')) \in \mathcal{F} \\ \{\mathcal{F} \models_{\theta} \phi_1 \wedge \phi_2\} &= \{\mathcal{F} \models_{\theta} \phi_1\} \wedge \{\mathcal{F} \models_{\theta} \phi_2\} \\ \{\mathcal{F} \models_{\theta} \phi_1 \vee \phi_2\} &= \begin{cases} \{\mathcal{F} \models_{\theta} \phi_1\} & \text{if } \mathcal{F} \models_{\theta} \phi_1 \\ \{\mathcal{F} \models_{\theta} \phi_2\} & \text{otherwise} \end{cases} \end{align*} $$

where $\tilde{z}$ are the non-process variables in $\mathcal{F}$, in the image of $\theta$, and in $\tilde{x}$, and $\tilde{T}''$ are their types.

**Lemma 37** $\{\mathcal{F} \models_{\theta} \phi\} \Rightarrow \forall \tilde{z} \in \tilde{T}''', \neg (\bigwedge \mathcal{F} \wedge \neg \theta \phi)$, where $\tilde{z}$ are the non-process variables in $\mathcal{F}$, in the image of $\theta$, and in $\tilde{x}$, and $\tilde{T}''$ are their types.

**Proof** By induction on $\phi$. $\square$

<figure><img src="image_14.png" /></figure>

**Lemma 38** Let $Q_0$ be a process that satisfies Properties 3 and 4. Let $\text{Tr}$ be a full trace of $C[Q_0]$ for some attacker $A \in \mathcal{BB}$. Let $\mu \in \mathcal{E}$ be the sequence of events in the last configuration of $\text{Tr}$. Let $F = \text{event}(e(\tilde{M}))$ where $\tilde{M}$ is a tuple of terms and $e$ is an event that does not occur in $C$. Suppose that the arguments of $e$ in $Q_0$ are always simple terms. Let $\rho$ be a mapping of the variables of $\tilde{M}$ and $\tau$ to their values. Suppose that $\text{Tr}, \rho \vdash F @ \tau$.
Then there exist a program point $\mu$ (in $Q_0$) that executes $F$ and a case $c$ such that, for any $\theta'$ renaming of $I_\mu$ to fresh replication indices, there exists a mapping $\sigma$ with domain $\theta' I_\mu$ such that $\mu\mathcal{E}v(\rho(\tau)) = (\mu, \sigma(\theta' I_\mu)) : e(\dots)$ and $\text{Tr}, \sigma \cup \rho \vdash \theta' \mathcal{F}_{F,\mu,c}^0$. If additionally, $\text{Tr}$ does not execute a non-unique event of $Q_0$, then $\text{Tr}, \sigma \cup \rho \vdash \theta' \mathcal{F}_{F,\mu,c}$.

**Proof** Let $E = E_{\text{Tr}}$. Since $\text{Tr}, \rho \vdash F@\tau$ and the variables of $\tilde{M}$ and $\tau$ are defined in $\rho$, there exists $\tilde{a}$ such that $\rho, \tilde{M} \Downarrow \tilde{a}$ and $\mu\mathcal{E}v(\rho(\tau)) = (\mu, \tilde{a}_0) : e(\tilde{a})$ for some $\mu$ and $\tilde{a}_0$. The rule of the semantics that may have added this element to $\mu\mathcal{E}v$ is (Event), (EventAbort), (CtxEvent), (FindE), (Find3), (GetE), (Get3), or (EventT).

* In case (Event), the initial configuration of the rule (Event) is of the form

$$E_1, (\sigma_1, \mu \text{ event } e(\tilde{a}); P) :: St_0, Q_0, Or_0, T_1, \mu \mathcal{E}v_1.$$

By Lemma 8, Property 1 applied to this configuration, we have reductions

$$
\begin{align*}
\text{Conf} = E_0, (\sigma_0, \mu \text{ event } e(\tilde{M}'); P) &:: St_0, Q_0, Or_0, T_0, \mu \mathcal{E}v_0 \\
&\xrightarrow{p_0} t_0 \dots \xrightarrow{p_1} t_1 E_1, (\sigma_1, \mu \text{ event } e(\tilde{a}); P) &:: St_0, Q_0, Or_0, T_1, \mu \mathcal{E}v_1 \\
&\xrightarrow{1} E_1, (\sigma_1, P) &:: St_0, Q_0, Or_0, T_1, (\mu \mathcal{E}v_1, (\mu, \text{Im}(\sigma_1)) : e(\tilde{a}))
\end{align*}
$$

where $\mu \text{ event } e(\tilde{M}'); P$ is a subprocess of $C[Q_0]$ up to renaming of oracles, by any number of applications of (Ctx) and a final application of (Event).

* In case (EventAbort), (Find3), or (Get3), the rules that can conclude with a process $^\mu P$ with $P = \text{event_abort} e, P = \text{find}[\text{unique}_e] \dots$, or $P = \text{get}[\text{unique}_e] \dots$ are (New), (Let), (If1), (If2), (Find1), (Find2), (Insert), (Get1), (Get2), (OracleCall), (Return), (Yield), (AttIO),(AttYield), (Event) and by Corollary 1, their target process is a subprocess of $C[Q_0]$ up to renaming of oracles. So we have a reduction

$$
\begin{align*}
\text{Conf} = E_0, (\sigma_0, \mu P) &:: St_0, Q_0, Or_0, T_0, \mu \mathcal{E}v_0 \\
\xrightarrow{p} E_0, (\sigma_0, \text{abort}) &:: St_0, Q_0, Or_0, T_0, (\mu \mathcal{E}v_0, (\mu, \text{Im}(\sigma_0)) : e)
\end{align*}
$$

where $^\mu P$ is a subprocess of $C[Q_0]$ up to renaming of oracles, by (EventAbort), (Find3), or (Get3).

* In case (EventT), the initial configuration of the rule (EventT) is of the form $E_1, \sigma_1, \mu \text{ event } e(\tilde{a}); N, T_1, \mu \mathcal{E}v_1$. By Lemma 8, Property 4 applied to this configuration with $l = 0$, we have reductions

$$
\begin{align*}
\text{Conf} = E_0, \sigma_0, \mu \text{ event } e(\tilde{M}'); N, T_0, \mu \mathcal{E}v_0 \\
\xrightarrow{p_0} t_0 \dots \xrightarrow{p_1} t_1 E_1, \sigma_1, \mu \text{ event } e(\tilde{a}); N, T_1, \mu \mathcal{E}v_1 \\
\xrightarrow{1} E_1, \sigma_1, N, T_1, (\mu \mathcal{E}v_1, (\mu, \text{Im}(\sigma_1)) : e(\tilde{a}))
\end{align*}
$$

where $\mu \text{ event } e(\tilde{M}'); N$ is a subterm of $C[Q_0]$, by any number of applications of (CtxT) and a final application of (EventT).

* In case (CtxEvent), the only rule that can conclude with a process $C[\text{event_abort} (\mu, \tilde{a}_0) : e]$ is (Ctx). (The rules (New), (Let), (If1), (If2), (Find1), (Find2), (Insert), (Get1), (Get2), (OracleCall), (Return), (Yield), (AttIO),(AttYield), (Event) cannot conclude with
$C[\mathit{event_abort}(\mu, \tilde{a}_0) : e]$ because, by Corollary 1, their target process is a subprocess of $C[Q_0]$ up to renaming of oracles, and the initial process $C[Q_0]$ does not contain the abort event value $\mathit{event_abort}(\mu, \tilde{a}_0) : e$.) Hence, there is a rule that concludes with a term $\mathit{event_abort}(\mu, \tilde{a}_0) : e$.

In cases (FindE) and (GetE), there is also a rule that concludes with a term $\mathit{event_abort}(\mu, \tilde{a}_0) : e$.

The only rules that conclude with a term $\mathit{event_abort}(\mu, \tilde{a}_0) : e$ are (FindTE), (FindT3), (GetTE), (GetT3), (EventAbortT), and (CtxEventT). (It cannot be (NewT), (LetT), (IfT1), (IfT2), (FindT1), (FindT2), (InsertT), (GetT1), (GetT2), (EventT), (DefinedYes) because, by Corollary 1, their target term is a subterm of $C[Q_0]$, and the initial process $C[Q_0]$ does not contain the abort event value $\mathit{event_abort}(\mu, \tilde{a}_0) : e$.) In cases (FindTE) and (GetTE), there is recursively another rule that concludes with $\mathit{event_abort}(\mu, \tilde{a}_0) : e$. In case (CtxEventT), the only rule that can conclude with $C[\mathit{event_abort}(\mu, \tilde{a}_0) : e]$ is (CtxT), so there is recursively another rule that concludes with $\mathit{event_abort}(\mu, \tilde{a}_0) : e$. Therefore, $\mathit{event_abort}(\mu, \tilde{a}_0) : e$ ultimately comes from an application of (EventAbortT), (FindT3), or (GetT3):

$$ \mathit{Conf} = E_0, \sigma_0, {}^{\mu}N, \mathcal{T}_0, \mu\mathcal{E}v_0 \xrightarrow{p} t E_0, \sigma_0, \mathit{event_abort}(\mu, \mathrm{Im}(\sigma_0)) : e, \mathcal{T}_0, \mu\mathcal{E}v_0 $$

where $N = \mathit{event_abort} e$, $N = \mathit{find}[\mathit{unique}_e] \dots$, or $N = \mathit{get}[\mathit{unique}_e] \dots$. Furthermore, the only rules that can conclude with such a term ${}^{\mu}N$ are (NewT), (IfT1), (IfT2), (LetT), (FindT1), (FindT2), (InsertT), (GetT1), (GetT2), (EventT), (DefinedYes) and, by Corollary 1, their target term is a subterm of $C[Q_0]$.

In all cases, since $e$ does not occur in $C$, $\mu$ is in fact a program point of $Q_0$. Therefore, the process or term at program point $\mu$ in $Q_0$ is of the form ${}^{\mu}\mathit{event} e(\tilde{M}'); \dots, {}^{\mu}\mathit{event_abort} e, {}^{\mu}\mathit{find}[\mathit{unique}_e] \dots$, or ${}^{\mu}\mathit{get}[\mathit{unique}_e] \dots$. In cases (Event) and (EventT), we have $\sigma_0 = \sigma_1$ by Lemma 3. In all cases, $\mathrm{Dom}(\sigma_0) = I_\mu$ are the current replication indices at program point $\mu$ by Lemma 2, and $\mathrm{Im}(\sigma_0) = \tilde{a}_0$, so $\sigma_0 = [I_\mu \mapsto \tilde{a}_0]$. Moreover, $\tilde{M}'$ are simple terms, so their evaluation can be written $E_0, \{I_\mu \mapsto \tilde{a}_0\}, \tilde{M}' \downarrow \tilde{a}$. Let $\sigma = \{\theta' I_\mu \mapsto \tilde{a}_0\}$. We have $\mu\mathcal{E}v(\rho(\tau)) = (\mu, \sigma(\theta' I_\mu)) : e(\tilde{a})$.

We have $E_0, \sigma_0, \tilde{M}' \downarrow \tilde{a}$ so $E_0, \sigma, \theta' \tilde{M}' \downarrow \tilde{a}$. The environment $E_{Tr}$ extends $E_0$, so $E_{Tr}, \sigma, \theta' \tilde{M}' \downarrow \tilde{a}$, so $Tr, \sigma \cup \rho \vdash \theta' \tilde{M}' = \tilde{M}$.

The configuration $Conf$ is at program point $\mu$ in $Tr$, so by Corollary 3, we have $Tr, \sigma \vdash \theta' \mathcal{F}_{\mu,c}$.

When the process or term at $\mu$ is ${}^{\mu}\mathit{event_abort} e$, ${}^{\mu}\mathit{find}[\mathit{unique}_e] \dots$, or ${}^{\mu}\mathit{get}[\mathit{unique}_e] \dots$, the environment and replication indices in $Conf$ are the same as at the end of the trace, since the execution after $Conf$ applies (EventAbort), (Find3), or (Get3), which terminate the trace keeping the same environment and replication indices as in $Conf$ or (EventAbortT), (FindT3), or (GetT3) which build an abort event value keeping the same environment and replication indices as in $Conf$, followed by some rules among (FindTE), (GetTE), (CtxT), (CtxEventT), (FindE), (GetE), (Ctx), and (CtxEvent), which preserve the environment and replication indices that come with the abort event value. So $Tr, \sigma \vdash \mathrm{lastdefprogrampoint}(\mu, \theta' I_\mu)$.

Therefore, $\mu$ executes $F$ and $Tr, \sigma \cup \rho \vdash \theta' \mathcal{F}_{F,\mu,c}^0$ for some $c$.

Suppose additionally that $Tr$ does not execute any non-unique event of $Q_0$. Let $Tr''$ be the prefix of $Tr$ that stops at the first evaluated return return (b); $Q$ or yield that follows $Conf$, or $Tr'' = Tr$ if $Tr$ contains no return nor yield after $Conf$. By Lemma 33, we have $Tr'' \vdash \mathcal{F}_{\mu}^{\mathrm{Fut}}$, so $Tr'', \sigma \vdash \theta' \mathcal{F}_{\mu}^{\mathrm{Fut}}$. Moreover, $E$ extends $E_{Tr''}$ and by Lemma 3, $\mu\mathcal{E}v_{Tr}$ extends $\mu\mathcal{E}v_{Tr''}$, so $Tr, \sigma \vdash \theta' \mathcal{F}_{\mu}^{\mathrm{Fut}}$. Therefore, $Tr, \sigma \cup \rho \vdash \theta' \mathcal{F}_{F,\mu,c}$ for some $c$. $\square$
**Lemma 39** Let $\varphi = [\forall \tilde{x} : \tilde{T}; \psi \Rightarrow \exists \tilde{y} : \tilde{T}'; \phi]$ be a non-injective correspondence that does not use non-unique events, with $\psi = F_1 \wedge \dots \wedge F_m$, $\tilde{x} = \text{var}(\psi)$, and $\tilde{y} = \text{var}(\phi) \ \text{var}(\psi)$. Let $Q_0$ be a process that satisfies Properties 3 and 4. Suppose that, in $Q_0$, the arguments of the events that occur in $\psi$ are always simple terms.

Let $S = \{(\mu_1, c_1, \dots, \mu_m, c_m) \mid \forall j \le m, \mu_j \text{ executes } F_j \text{ and } c_j \text{ is a case for } \mathcal{F}_{\mu_j, c_j}\}$. Let $C$ be an evaluation context acceptable for $Q_0$ with public variables $V$ that does not contain events used by $\varphi$ and $A$ be an attacker in $BB$. Let $Tr$ be a full trace of $C[Q_0]$ for $A$ that does not execute any non-unique event of $Q_0$. If $Tr \vdash \neg\varphi$, then for any $\theta$ family of substitutions equal to the identity on $\tilde{x}$, $Tr \vdash \neg\{\text{prove}^\varphi(\theta, S)\}$.

**Proof** Since $Tr \vdash \neg\varphi$, we have $Tr \vdash \exists \tilde{x} \in \tilde{T}, F_1 \wedge \dots \wedge F_m \wedge \forall \tilde{y} \in \tilde{T}', \neg\phi$. So there exists $\rho$ that maps $\tilde{x}$ to elements of $\tilde{T}$ such that $Tr, \rho \vdash F_1 \wedge \dots \wedge F_m \wedge \forall \tilde{y} \in \tilde{T}', \neg\phi$. By Lemma 38, for all $j \le m$, there exists a program point $\mu_j$ (in $Q_0$) that executes $F_j$ and a case $c_j$ such that, for any $\theta_j$ renaming of $I_{\mu_j}$ to fresh replication indices, there exists a mapping $\sigma_j$ with domain $\theta_j I_{\mu_j}$ such that $Tr, \sigma_j \cup \rho \vdash \theta_j \mathcal{F}_{F_j, \mu_j, c_j}$. Since $Tr, \rho \vdash \forall \tilde{y} \in \tilde{T}', \neg\phi$, we have $Tr, \rho \vdash \neg\theta(\mu_1, c_1, \dots, \mu_m, c_m)\phi$. Therefore, $Tr, \sigma_1 \cup \dots \cup \sigma_m \cup \rho \vdash \theta_1 \mathcal{F}_{F_1, \mu_1, c_1} \cup \dots \cup \theta_m \mathcal{F}_{F_m, \mu_m, c_m} \cup \{\neg\theta(\mu_1, c_1, \dots, \mu_m, c_m)\phi\}$, so $Tr \vdash \exists \theta_1 I_{\mu_1}, \dots, \exists \theta_m I_{\mu_m}, \exists \tilde{x} \in \tilde{T}, \bigwedge \mathcal{F}_0(\mu_1, c_1, \dots, \mu_m, c_m) \wedge \neg\theta(\mu_1, c_1, \dots, \mu_m, c_m)\phi$ where $\mathcal{F}_0(\mu_1, c_1, \dots, \mu_m, c_m) = \theta_1 \mathcal{F}_{F_1, \mu_1, c_1} \cup \dots \cup \theta_m \mathcal{F}_{F_m, \mu_m, c_m}$. We have

$$ \{\text{prove}^{\varphi}(\theta, \mu_1, c_1, \dots, \mu_m, c_m)\} \\ \Rightarrow \forall \theta_1 I_{\mu_1}, \dots, \forall \theta_m I_{\mu_m}, \forall \tilde{x} \in \tilde{T}, \neg(\bigwedge \mathcal{F}_0(\mu_1, c_1, \dots, \mu_m, c_m) \wedge \neg\theta(\mu_1, c_1, \dots, \mu_m, c_m)\phi) $$

by Lemma 37. (The non-process variables in $\mathcal{F}_0(\mu_1, c_1, \dots, \mu_m, c_m)$, in the image of $\theta(\mu_1, c_1, \dots, \mu_m, c_m)$, and in $\tilde{x}$ are in $\theta_1 I_{\mu_1}, \dots, \theta_m I_{\mu_m}, \tilde{x}$.) So $Tr \vdash \neg\{\text{prove}^\varphi(\theta, \mu_1, c_1, \dots, \mu_m, c_m)\}$, so $Tr \vdash \neg\{\text{prove}^\varphi(\theta, S)\}$. $\square$

**Proof of Proposition 2** Let $C$ be an evaluation context acceptable for $Q_0$ with public variables $V$ that does not contain events used by $\varphi$ and $A$ be an attacker in $BB$. We have

$$ \begin{align*} \text{Adv}_{Q_0}(A, C, \varphi, D_{\text{false}}) &= \text{Pr}^A[C[Q_0] : \neg\varphi \wedge \neg\text{NonUnique}_{Q_0}] \\ &\le \text{Pr}^A[C[Q_0] : \neg\{\text{prove}^\varphi(\theta, S)\}] \quad \text{by Lemma 39} \\ &\le \text{Pr}^A[C[Q_0 \le \neg\{\text{prove}^\varphi(\theta, S)\}]] \quad \text{by Lemma 1} \\ &\le p(A, C) \end{align*} $$

So $\text{Bound}_{Q_0}(V, \varphi, D_{\text{false}}, p)$. $\square$

**Example 6** Let us prove that the example $G_1$ satisfies (4). We first study the facts $\mathcal{F}_{\mu_B}$ that hold at the program point $\mu_B$ that executes event $e_B$. $\mathcal{F}_{\mu_B}$ contains $\text{defined}(m[u[i_B]])$, $\text{defined}(x_B[u[i_B]])$, $\text{defined}(x_N[u[i_B]])$, $x_{pk_A}[i_B] = pk_A$, $B = x_B[u[i_B]]$, and $N[i_B] = x_N[u[i_B]]$, because the condition of find holds at $\mu_B$. Moreover, we have $\text{defined}(m[u[i_B]]) \in \mathcal{F}_{\mu_B}$, and, when $m[i_A]$ is defined, $(\mu_A, i_A) : \text{event}(e_A(pk_A, x_B[i_A], x_N[i_A]))$ holds, so $(\mu_A, i_A) : \text{event}(e_A(pk_A, x_B[i_A], x_N[i_A]))\{u[i_B]/i_A\} \in \mathcal{F}_{\mu_B}$, that is, $(\mu_A, u[i_B]) : \text{event}(e_A(pk_A, x_B[u[i_B]], x_N[u[i_B]])) \in \mathcal{F}_{\mu_B}$. In other words, since $m$ is defined at index $u[i_B]$, event $e_A$ has been executed in the copy of $Q'_{1A}$ of index $u[i_B]$. ($\mathcal{F}_{\mu_B}$ also contains other facts, which are useless for proving the desired correspondences, so we do not list them.)

For $\psi = F = \text{event}(e_B(x, y, z))$, $\mu_B$ is the only program point that executes $F$, so this event has been executed in some copy of $Q'_{1B}$ of index $i'_B$, with $x_{pk_A}[i'_B] = x, B = y, N[i'_B] = z$. Then, when $\psi$ holds, the facts $\theta' \mathcal{F}_{F, \mu_B} \supset \theta' \mathcal{F}_{\mu_B} \cup \{x_{pk_A}[i'_B] = x, B = y, N[i'_B] = z\}$ hold for some value of $i'_B$, with $\theta' = \{i'_B/i_B\}$. (We consider a single case $c$ here, so we can simply omit the case $c$.)
Furthermore, the substitution $\theta(\mu_B)$ is the identity since all variables of $\phi$ also occur in $\psi$. Then we just have to show that $\theta'\mathcal{F}_{F,\mu_B}$ implies $\phi = \text{event}(e_A(x, y, z))$, that is, $\theta'\mathcal{F}_{F,\mu_B} \models_{\theta(\mu_B)} \text{event}(e_A(x, y, z))$. Since $(\mu_A, u[i_B]) : \text{event}(e_A(pk_A, x_B[u[i_B]]), x_N[u[i_B]]) \in \mathcal{F}_{\mu_B}$, we have $(\mu_A, u[i'_B]) : \text{event}(e_A(pk_A, x_B[u[i'_B]], x_N[u[i'_B]])) \in \theta'\mathcal{F}_{F,\mu_B}$, so the equational prover just has to prove by contradiction that $e_A(pk_A, x_B[u[i'_B]], x_N[u[i'_B]]) = e_A(x, y, z)$, that is, $pk_A = x, x_B[u[i'_B]] = y$, and $x_N[u[i'_B]] = z$. The proof succeeds using the following equalities of $\theta'\mathcal{F}_{F,\mu_B}$: $x_{pk_A}[i'_B] = x$, $B = y$, $N[i'_B] = z$, $x_{pk_A}[i'_B] = pk_A$, $B = x_B[u[i'_B]]$, and $N[i'_B] = x_N[u[i'_B]]$.

Hence, $G_1$ satisfies (4) with any public variables $V$: if $\psi = \text{event}(e_B(x, y, z))$ has been executed, then $\phi = \text{event}(e_A(x, y, z))$ has been executed.

In the implementation, the substitution $\theta$ is initially defined as the identity on $\tilde{x} = \text{var}(\psi)$. It is defined on other variables when checking $\mathcal{F} \models_{\theta} M$ by trying to find $\theta$ such that $\theta M \in \mathcal{F}$, and when checking $\mathcal{F} \models_{\theta} \text{event}(e(M_1, \dots, M_m))$ by trying to find $\theta$ such that $\theta \text{event}(e(M_1, \dots, M_m)) \in \mathcal{F}$. When we do not manage to find the image by $\theta$ of all variables of $M$, resp. $M_1, \dots, M_m$, the check fails. When there are several suitable facts $\theta M \in \mathcal{F}$ or $\theta \text{event}(e(M_1, \dots, M_m)) \in \mathcal{F}$, the system tries all possibilities.

### 4.2.4 Injective Correspondences

Injective correspondences are more difficult to check than non-injective ones, because they require distinguishing between several executions of the same event. We achieve that by relying on the pair (program points, replication indices) that is recorded in the sequence $\mu\mathcal{E}v$ together with each event: distinct executions of events either occur at different program points or have different values of replication indices.

We extend Definition 16 to injective events, with exactly the same definition as for non-injective events.

The proof of injective correspondences extends that for non-injective correspondences: for a correspondence $\forall \tilde{x} : \tilde{T}; \psi \Rightarrow \exists \tilde{y} : \tilde{T}'; \phi$, we additionally prove that distinct executions of the injective events of $\psi$ correspond to distinct executions of each injective event of $\phi$, that is, if the injective events of $\psi$ have different pairs (program point, replication indices), then each injective event of $\phi$ has a different pair (program point, replication indices). In order to achieve this proof, we collect the following information for each injective event of $\phi$:

* the set of facts $\mathcal{F}$ that are known to hold, which will be used to reason on replication indices of events;

* the program point and replication indices of the considered injective event of $\phi$, stored in a pair $M_0$; these program point and indices are computed when we prove that this event is executed;

* the program point and replication indices of the injective events of $\psi$, stored as a mapping $\mathcal{I} = \{j \mapsto (\mu_j, \theta_j I_{\mu_j}) \mid F_j$ is an injective event$\}$, where $\psi = F_1 \wedge \dots \wedge F_m$, $\mu_j$ is the program point that executes $F_j$, and $\theta_j$ is a renaming of $I_{\mu_j}$ to fresh replication indices, for $j \le m$;

* the set $\mathcal{V}$ containing the replication indices in $\mathcal{F}$ and the variables $\tilde{x}$ of $\psi$; these variables will be renamed to fresh variables in order to avoid conflicts of variable names between different events.

This information is stored in a set $\mathcal{S}$, which contains quadruples $(\mathcal{F}, M_0, \mathcal{I}, \mathcal{V})$. We will show that, if the pair (program point, replication indices) of two executions of the injective events of $\psi$ are different, then the pair (program, replication indices) of the corresponding executions of
the considered injective event of $\phi$ are also different. The equality between pairs (program point, replication indices) is obviously defined as the equality between program points and between replication indices. Formally, we consider $(\mathcal{F}, M_0, \mathcal{I}, \mathcal{V})$ and $(\mathcal{F}', M'_0, \mathcal{I}', \mathcal{V}')$ in $\mathcal{S}$. We rename the variables $\mathcal{V}'$ of the second element to fresh variables by a substitution $\theta''$ and show that, if $\mathcal{I} \neq \theta''\mathcal{I}'$, then $M_0 \neq \theta''M'_0$ (knowing $\mathcal{F}$ and $\theta''\mathcal{F}'$). This property implies injectivity.

Since this reasoning is done for each injective event in $\phi$, we collect the associated sets $\mathcal{S}$ in a pseudo-formula $\mathcal{C}$, obtained by replacing each injective event of $\phi$ with a set $\mathcal{S}$ and all other leaves of $\phi$ with $\perp$.

We say that $\vdash \mathcal{C}$ when for all non-bottom leaves $\mathcal{S}$ of $\mathcal{C}$, for all $(\mathcal{F}, M_0, \mathcal{I}, \mathcal{V})$, $(\mathcal{F}', M'_0, \mathcal{I}', \mathcal{V}')$ in $\mathcal{S}$, $\mathcal{F} \cup \theta''\mathcal{F}' \cup \{\bigcup_{j \in \text{Dom}(\mathcal{I})} \mathcal{I}(j) \neq \theta''\mathcal{I}'(j), M_0 = \theta''M'_0\}$ yields a contradiction, where the substitution $\theta''$ is a renaming of variables in $\mathcal{V}'$ to distinct fresh variables. As explained above, the condition $\vdash \mathcal{C}$ guarantees injectivity.

We extend the definition of $\mathcal{F} \models_{\theta} \phi$ used for non-injective correspondences to $\mathcal{F} \models_{\theta}^{\mathcal{I}, \mathcal{V}, \mathcal{C}} \phi$, which means that $\mathcal{F}$ implies $\theta\phi$ and $\mathcal{C}$ correctly collects the tuples $(\mathcal{F}, M_0, \mathcal{I}, \mathcal{V})$ associated to this proof. Formally, we define:

$$ \mathcal{F} \models_{\theta}^{\mathcal{I}, \mathcal{V}, \perp} M \text{ if and only if } \mathcal{F} \cup \{\neg \theta M\} \text{ yields a contradiction} $$

$$ \begin{array}{l} \mathcal{F} \models_{\theta}^{\mathcal{I}, \mathcal{V}, \perp} \text{event}(e(M_1, \dots, M_m)) \text{ if and only if} \\ \quad \text{there exist } M'_0, \dots, M'_m \text{ such that } M'_0 : \text{event}(e(M'_1, \dots, M'_m)) \in \mathcal{F} \text{ and} \\ \quad \mathcal{F} \cup \{\bigcup_{j=1}^m \theta M_j \neq M'_j\} \text{ yields a contradiction} \end{array} $$

$$ \begin{array}{l} \mathcal{F} \models_{\theta}^{\mathcal{I}, \mathcal{V}, \mathcal{S}} \text{inj-event}(e(M_1, \dots, M_m)) \text{ if and only if} \\ \quad \text{there exist } M'_0, \dots, M'_m \text{ such that } M'_0 : \text{event}(e(M'_1, \dots, M'_m)) \in \mathcal{F}, \\ \quad \mathcal{F} \cup \{\bigcup_{j=1}^m \theta M_j \neq M'_j\} \text{ yields a contradiction, and } (\mathcal{F}, M'_0, \mathcal{I}, \mathcal{V}) \in \mathcal{S}. \end{array} $$

$$ \mathcal{F} \models_{\theta}^{\mathcal{I}, \mathcal{V}, \mathcal{C}_1 \wedge \mathcal{C}_2} \phi_1 \wedge \phi_2 \text{ if and only if } \mathcal{F} \models_{\theta}^{\mathcal{I}, \mathcal{V}, \mathcal{C}_1} \phi_1 \text{ and } \mathcal{F} \models_{\theta}^{\mathcal{I}, \mathcal{V}, \mathcal{C}_2} \phi_2 $$

$$ \mathcal{F} \models_{\theta}^{\mathcal{I}, \mathcal{V}, \mathcal{C}_1 \vee \mathcal{C}_2} \phi_1 \vee \phi_2 \text{ if and only if } \mathcal{F} \models_{\theta}^{\mathcal{I}, \mathcal{V}, \mathcal{C}_1} \phi_1 \text{ or } \mathcal{F} \models_{\theta}^{\mathcal{I}, \mathcal{V}, \mathcal{C}_2} \phi_2 $$

These formulas differ from the non-injective case in that we propagate $\mathcal{I}$, $\mathcal{V}$, $\mathcal{C}$ and, in the case of injective events, we make sure that quadruples $(\mathcal{F}, M'_0, \mathcal{I}, \mathcal{V})$ are collected correctly by requiring that $(\mathcal{F}, M'_0, \mathcal{I}, \mathcal{V}) \in \mathcal{S}$.

Let $\varphi = [\forall \tilde{x} : \tilde{T}; \psi \Rightarrow \exists \tilde{y} : \tilde{T}'; \phi]$ be a correspondence that does not use non-unique events, with $\psi = F_1 \wedge \dots \wedge F_m$, $\tilde{x} = \text{var}(\psi)$, and $\tilde{y} = \text{var}(\phi) \setminus \text{var}(\psi)$. Suppose that, in $Q_0$, the arguments of the events that occur in $\psi$ are always simple terms. Suppose that, for all $j \le m$, $\mu_j$ executes $F_j$ and $c_j$ is a case for $\mathcal{F}_{\mu_j c_j}$. For $j \le m$, let $\theta_j$ be a renaming of $I_{\mu_j}$ to fresh replication indices. (The renamings $\theta_j$ have pairwise disjoint images.) Let $\mathcal{C}$ be a pseudo formula and $\theta$ a family parameterized by $\mu_1, c_1, \dots, c_m, \mu_m$ of substitutions equal to the identity on $\tilde{x}$. We define prove$^{\varphi}(\mathcal{C}, \theta, \mu_1, c_1, \dots, \mu_m, c_m) = (\mathcal{F} \models_{\theta(\mu_1, c_1, \dots, \mu_m, c_m)}^{\mathcal{I}, \mathcal{V}, \mathcal{C}} \phi)$ where $\mathcal{F} = \theta_1 \mathcal{F}_{F_1, \mu_1, c_1} \cup \dots \cup \theta_m \mathcal{F}_{F_m, \mu_m, c_m}$, $\mathcal{I} = \{j \mapsto (\mu_j, \theta_j I_{\mu_j}) \mid F_j \text{ is an injective event}\}$, and $\mathcal{V} = \text{var}(\theta_1 I_{\mu_1}) \cup \dots \cup \text{var}(\theta_m I_{\mu_m}) \cup \{\tilde{x}\}$. The algorithm prove$^{\varphi}(\mathcal{C}, \theta, \mu_1, \dots, \mu_m)$ shows that the non-injective version of the correspondence $\varphi$ holds assuming the events in $\psi = F_1 \wedge \dots \wedge F_m$ are executed at program points $\mu_1, \dots, \mu_m$ respectively. Indeed, in this case, the facts $\mathcal{F} = \theta_1 \mathcal{F}_{F_1, \mu_1} \cup \dots \cup \theta_m \mathcal{F}_{F_m, \mu_m}$ hold and the formula $\mathcal{F} \models_{\theta(\mu_1, \dots, \mu_m)}^{\mathcal{I}, \mathcal{V}, \mathcal{C}} \phi$ shows that this implies $\theta(\mu_1, \dots, \mu_m)\phi$. (The substitution $\theta(\mu_1, \dots, \mu_m)\phi$ determines the values of $\tilde{y}$.) Additionally, prove$^{\varphi}(\mathcal{C}, \theta, \mu_1, \dots, \mu_m)$ makes sure that $\mathcal{C}$ correctly collects the information needed to prove injectivity. We also define prove$^{\varphi}(\mathcal{C}, \theta, \mathcal{S}) = (\vdash \mathcal{C}) \wedge \bigwedge_{(\mu_1, c_1, \dots, \mu_m, c_m) \in \mathcal{S}} \text{prove}^{\varphi}(\mathcal{C}, \theta, \mu_1, c_1, \dots, \mu_m, c_m)$. This algorithm proves the correspondence $\varphi$ assuming the events in $\psi$ are executed at program points in $\mathcal{S}$. It verifies injectivity via $\vdash \mathcal{C}$.

The following proposition shows the soundness of the proof of injective correspondences based on this algorithm.
**Proposition 3** Let $\varphi = [[\forall \tilde{x} : \tilde{T}; \psi \Rightarrow \exists \tilde{y} : \tilde{T}'; \phi]]$ be a correspondence that does not use non-unique events, with $\psi = F_1 \wedge \dots \wedge F_m$, $\tilde{x} = \text{var}(\psi)$, and $\tilde{y} = \text{var}(\phi) \setminus \text{var}(\psi)$. Let $Q_0$ be a process that satisfies Properties 3 and 4. Suppose that, in $Q_0$, the arguments of the events that occur in $\psi$ are always simple terms.

Let $S = \{(\mu_1, c_1, \dots, \mu_m, c_m) \mid \forall j \le m, \mu_j \text{ executes } F_j \text{ and } c_j \text{ is a case for } \mathcal{F}_{\mu_j, c_j}\}$. Assume that there exist a pseudo-formula $C$ and a family of substitutions $\theta$ equal to the identity on $\tilde{x}$ such that $\text{prove}^{\varphi}(C, \theta, S)$. Assume that for all $A \in \mathcal{BB}$ and all evaluation contexts $C$ acceptable for $Q_0$, $\text{Pr}^A[C|Q_0] \subseteq \neg[\text{prove}^{\varphi}(C, \theta, S)]] \le p(A, C)$. Then $\text{Bound}_{Q_0}(V, \varphi, D_{\text{false}}, p)$ for any $V$.

In the implementation, the value of $C$ is computed by adding $(\mathcal{F}, M'_0, \mathcal{I}, \mathcal{V})$ to $S$ when handling injective events during the checking of $\text{prove}^{\varphi}(C, \theta, S)$. We check $\vdash C$ incrementally, after each addition of an element to $C$. The proof of Proposition 3 relies on the following definitions and lemmas. We have

$$ 
\begin{align*}
\{\mathcal{F} \models_{\theta}^{\mathcal{I}, \mathcal{V}, \perp} M\} &= \forall \tilde{z} \in \tilde{T}''_{\theta}, \neg (\bigwedge \mathcal{F} \wedge \neg \theta M) \\
\{\mathcal{F} \models_{\theta}^{\mathcal{I}, \mathcal{V}, \perp} \text{event}(e(M_1, \dots, M_m))\} &= \forall \tilde{z} \in \tilde{T}''_{\theta}, \neg (\bigwedge \mathcal{F} \wedge \bigvee_{j=1}^m \theta M_j \neq M'_j) \\
&\quad \text{for some } M'_0 : \text{event}(e(M'_1, \dots, M'_m)) \in \mathcal{F} \\
\{\mathcal{F} \models_{\theta}^{\mathcal{I}, \mathcal{V}, S} \text{inj-event}(e(M_1, \dots, M_m))\} &= \forall \tilde{z} \in \tilde{T}''_{\theta}, \neg (\bigwedge \mathcal{F} \wedge \bigvee_{j=1}^m \theta M_j \neq M'_j) \\
&\quad \text{for some } M'_0 : \text{event}(e(M'_1, \dots, M'_m)) \in \mathcal{F} \text{ and } (\mathcal{F}, M'_0, \mathcal{I}, \mathcal{V}) \in S \\
\{\mathcal{F} \models_{\theta}^{\mathcal{I}, \mathcal{V}, C_1 \wedge C_2} \phi_1 \wedge \phi_2\} &= \{\mathcal{F} \models_{\theta}^{\mathcal{I}, \mathcal{V}, C_1} \phi_1\} \wedge \{\mathcal{F} \models_{\theta}^{\mathcal{I}, \mathcal{V}, C_2} \phi_2\} \\
\{\mathcal{F} \models_{\theta}^{\mathcal{I}, \mathcal{V}, C_1 \vee C_2} \phi_1 \vee \phi_2\} &= \begin{cases} \{\mathcal{F} \models_{\theta}^{\mathcal{I}, \mathcal{V}, C_1} \phi_1\} & \text{if } \mathcal{F} \models_{\theta}^{\mathcal{I}, \mathcal{V}, C_1} \phi_1 \\ \{\mathcal{F} \models_{\theta}^{\mathcal{I}, \mathcal{V}, C_2} \phi_2\} & \text{otherwise} \end{cases}
\end{align*}
$$

where $\tilde{z} = \mathcal{V}$ and $\tilde{T}''$ are the types of these variables. We also have

$$ 
\{\vdash C\} = \bigwedge_{S \neq \perp} \bigwedge_{\text{leaf of } C (\mathcal{F}, M_0, \mathcal{I}, \mathcal{V}) \in S} \bigwedge_{(\mathcal{F}', M'_0, \mathcal{I}', \mathcal{V}') \in S} \forall \tilde{z} \in \tilde{T}''_{\theta}, \\
\quad \neg \left( \bigwedge \mathcal{F} \wedge \bigwedge \theta'' \mathcal{F}' \wedge \left( \bigvee_{j \in \text{Dom}(\mathcal{I})} \mathcal{I}(j) \neq \theta'' \mathcal{I}'(j) \right) \wedge M_0 = \theta'' M'_0 \right)
$$

where the substitution $\theta''$ is a renaming of variables in $\mathcal{V}'$ to distinct fresh variables, $\tilde{z} = \mathcal{V} \cup \theta''\mathcal{V}'$, and $\tilde{T}''$ are the types of these variables.

We define formula_($\mathcal{F} \models_{\theta}^{\mathcal{I}, \mathcal{V}, C} \phi$) as follows:

$$ 
\begin{align*}
\text{formula}(\mathcal{F} \models_{\theta}^{\mathcal{I}, \mathcal{V}, \perp} M) &= \theta M \\
\text{formula}(\mathcal{F} \models_{\theta}^{\mathcal{I}, \mathcal{V}, \perp} \text{event}(e(M_1, \dots, M_m))) &= \theta \text{event}(e(M_1, \dots, M_m)) \\
\text{formula}(\mathcal{F} \models_{\theta}^{\mathcal{I}, \mathcal{V}, S} \text{inj-event}(e(M_1, \dots, M_m))) &= \\
&\quad \bigvee_{(\mathcal{F}, N_0, \mathcal{I}, \mathcal{V}) \in S} \exists \tau \in \mathbb{N}, N_0 : \theta \text{event}(e(M_1, \dots, M_m)) @ \tau \\
\text{formula}(\mathcal{F} \models_{\theta}^{\mathcal{I}, \mathcal{V}, C_1 \wedge C_2} \phi_1 \wedge \phi_2) &= \text{formula}(\mathcal{F} \models_{\theta}^{\mathcal{I}, \mathcal{V}, C_1} \phi_1) \wedge \text{formula}(\mathcal{F} \models_{\theta}^{\mathcal{I}, \mathcal{V}, C_2} \phi_2) \\
\text{formula}(\mathcal{F} \models_{\theta}^{\mathcal{I}, \mathcal{V}, C_1 \vee C_2} \phi_1 \vee \phi_2) &= \begin{cases} \text{formula}(\mathcal{F} \models_{\theta}^{\mathcal{I}, \mathcal{V}, C_1} \phi_1) & \text{if } \mathcal{F} \models_{\theta}^{\mathcal{I}, \mathcal{V}, C_1} \phi_1 \\ \text{formula}(\mathcal{F} \models_{\theta}^{\mathcal{I}, \mathcal{V}, C_2} \phi_2) & \text{otherwise} \end{cases}
\end{align*}
$$

The formula $\text{formula}(\mathcal{F} \models_{\theta}^{\mathcal{I}, \mathcal{V}, C} \phi)$ generalizes $\theta\phi$ to the case of injective events.
**Lemma 40** $\{[\mathcal{F} \models_{\tilde{\theta}}^{\mathcal{I},\mathcal{V},\mathcal{C}} \phi]\} \Rightarrow \forall \tilde{z} \in \tilde{T}''$, $\neg (\bigwedge \mathcal{F} \wedge \neg \text{formula}(\mathcal{F} \models_{\tilde{\theta}}^{\mathcal{I},\mathcal{V},\mathcal{C}} \phi))$ where $\tilde{z} = \mathcal{V}$ and $\tilde{T}''$ are the types of these variables.

**Proof** By induction on $\phi$. This result is similar to Lemma 37. The case of injective events is new. The case of disjunction differs, but is straightforward by induction hypothesis. $\square$

The next lemma shows that, for events $e$ in the considered correspondence, two distinct executions of event $e$ have distinct pairs (program point, replication indices). When the term $M$ contains no array accesses, we define $\sigma(M)$ by $\sigma, M \downarrow \sigma(M)$.

**Lemma 41** Assume that the event $e$ is used in the correspondence $\varphi$. Let $Q_0$ be a process that satisfies Property 3. Let $C$ be an evaluation context acceptable for $Q_0$ with public variables $V$ that does not contain events used by $\varphi$ and $A$ be an attacker in $BB$. If $\text{initConfig}(C[Q_0], A) \xrightarrow{p_1} t_1$ $\dots \xrightarrow{p_{m-1}} t_{m-1}$ $E, St, Q, Or, T, \mu\mathcal{E}v, \mu\mathcal{E}v(\tau) = (\mu, \tilde{a}) : e(a_1, \dots, a_m)$, $\mu\mathcal{E}v(\tau') = (\mu', \tilde{a}') : e(a'_1, \dots, a'_m)$, and $\tau \neq \tau'$, then $(\mu, \tilde{a}) \neq (\mu', \tilde{a}')$.

**Proof** Let us fix the event symbol $e$. We define the multisets $\text{Events}(\tilde{a}, M)$, $\text{Events}(\tilde{a}, P)$, and $\text{Events}(\tilde{a}, Q)$ by

$$ \text{Events}(\tilde{a}, \mu i) = \emptyset $$

$$ \text{Events}(\tilde{a}, \mu x[M_1, \dots, M_m]) = \biguplus_{j \in \{1, \dots, m\}} \text{Events}(\tilde{a}, M_j) $$

$$ \text{Events}(\tilde{a}, \mu f(M_1, \dots, M_m)) = \biguplus_{j \in \{1, \dots, m\}} \text{Events}(\tilde{a}, M_j) $$

$$ \text{Events}(\tilde{a}, \mu x[\tilde{i}] \stackrel{R}{\leftarrow} T; N) = \text{Events}(\tilde{a}, N) $$

$$ \text{Events}(\tilde{a}, \mu \text{let } x[\tilde{i}] : T = M \text{ in } N) = \text{Events}(\tilde{a}, M) \uplus \text{Events}(\tilde{a}, N) $$

$$ \text{Events}(\tilde{a}, \mu \text{if } M \text{ then } N \text{ else } N') = \text{Events}(\tilde{a}, M) \uplus \max(\text{Events}(\tilde{a}, N), \text{Events}(\tilde{a}, N')) $$

$$ \text{Events}(\tilde{a}, \mu \text{find}[\text{unique?}] (\bigoplus_{j=1}^{m} \tilde{u}_j[\tilde{i}] = \tilde{i}_j \le \tilde{n}_j \text{ suchthat } \text{defined}(\tilde{M}_j) \wedge M'_j \text{ then } N_j) \text{ else } N') = \biguplus_{j=1}^{m} \bigcup_{\tilde{a}_j \le \tilde{n}_j} \text{Events}((\tilde{a}, \tilde{a}_j), M'_j) \uplus \max(\max_{j=1}^{m} \text{Events}(\tilde{a}, N_j), \text{Events}(\tilde{a}, N')) $$

$$ \text{Events}(\tilde{a}, \mu \text{event } e'(M_1, \dots, M_m); M) = \biguplus_{j \in \{1, \dots, m\}} \text{Events}(\tilde{a}, M_j) \uplus \text{Events}(\tilde{a}, M) \text{ if } e' \neq e $$

$$ \text{Events}(\tilde{a}, \mu \text{event } e(M_1, \dots, M_m); M) = \{(\mu, \tilde{a})\} \uplus \biguplus_{j \in \{1, \dots, m\}} \text{Events}(\tilde{a}, M_j) \uplus \text{Events}(\tilde{a}, M) $$

$$ \text{Events}(\tilde{a}, \mu \text{event\_abort } e') = \emptyset \text{ if } e' \neq e $$

$$ \text{Events}(\tilde{a}, \mu \text{event\_abort } e) = \{(\mu, \tilde{a})\} $$

$$ \text{Events}(\tilde{a}, \mu 0) = \emptyset $$

$$ \text{Events}(\tilde{a}, \mu(Q_1 | Q_2)) = \text{Events}(\tilde{a}, Q_1) \uplus \text{Events}(\tilde{a}, Q_2) $$

$$ \text{Events}(\tilde{a}, \mu \text{foreach } i \le n \text{ do } Q) = \biguplus_{a \in [1, n]} \text{Events}((\tilde{a}, a), Q) $$

$$ \text{Events}(\tilde{a}, \mu \text{newOracle } O; Q) = \text{Events}(\tilde{a}, Q) $$

$$ \text{Events}(\tilde{a}, \mu O[\tilde{i}](x[\tilde{i}] : T) := P) = \text{Events}(\tilde{a}, P) $$
$$ \mathit{Events}(\tilde{a}, \mu \mathit{return} (N); Q) = \mathit{Events}(\tilde{a}, N) \uplus \mathit{Events}(\tilde{a}, Q) $$

$$ \mathit{Events}(\tilde{a}, \mu x[\tilde{i}] \stackrel{R}{\leftarrow} T; P) = \mathit{Events}(\tilde{a}, P) $$

$$ \mathit{Events}(\tilde{a}, \mu \mathit{let} x[\tilde{i}] : T = M \text{ in } P) = \mathit{Events}(\tilde{a}, M) \uplus \mathit{Events}(\tilde{a}, P) $$

$$ \mathit{Events}(\tilde{a}, \mu \mathit{let} x[\tilde{i}] : T = O[M_1, \dots, M_k, ?u_1[\tilde{i}] \le n_1, \dots, ?u_m[\tilde{i}] \le n_m](M_{k+1}) \text{ in } P_1 \text{ else } P_2) = \\ \bigcup_{i=1}^{k+1} \mathit{Events}(\tilde{a}, M_i) \uplus \max(\mathit{Events}(\tilde{a}, P_1), \mathit{Events}(\tilde{a}, P_2)) $$

$$ \mathit{Events}(\tilde{a}, \mu \text{ if } M \text{ then } P \text{ else } P') = \mathit{Events}(\tilde{a}, M) \uplus \max(\mathit{Events}(\tilde{a}, P), \mathit{Events}(\tilde{a}, P')) $$

$$ \mathit{Events}(\tilde{a}, \mu \mathit{find}[\mathit{unique}?] (\bigoplus_{j=1}^m \tilde{u}_j[\tilde{i}] = \tilde{i}_j \le \tilde{n}_j \text{ suchthat } \mathit{defined}(\tilde{M}_j) \wedge \tilde{M}'_j \text{ then } P_j) \text{ else } P) = \\ \bigcup_{j=1}^m \bigcup_{\tilde{a}_j \le \tilde{n}_j} \mathit{Events}((\tilde{a}, \tilde{a}_j), \tilde{M}'_j) \uplus \max(\max_{j=1}^m \mathit{Events}(\tilde{a}, P_j), \mathit{Events}(\tilde{a}, P)) $$

$$ \mathit{Events}(\tilde{a}, \mu \mathit{event} e'(M_0, \dots, M_m); P) = \bigcup_{j \in \{1, \dots, m\}} \mathit{Events}(\tilde{a}, M_j) \uplus \mathit{Events}(\tilde{a}, P) \text{ if } e' \neq e $$

$$ \mathit{Events}(\tilde{a}, \mu \mathit{event} e(M_0, \dots, M_m); P) = \{ (\mu, \tilde{a}) \} \uplus \bigcup_{j \in \{1, \dots, m\}} \mathit{Events}(\tilde{a}, M_j) \uplus \mathit{Events}(\tilde{a}, P) $$

$$ \mathit{Events}(\tilde{a}, \mu \mathit{event\_abort} e') = \emptyset \text{ if } e' \neq e $$

$$ \mathit{Events}(\tilde{a}, \mu \mathit{event\_abort} e) = \{(\mu, \tilde{a})\} $$

$$ \mathit{Events}(\tilde{a}, \mu \mathit{yield}) = \emptyset $$

(get and insert are omitted because they do not occur in the game by Property 3 and as mentioned in the beginning of Section 3, get and insert in the adversary context can be encoded using find.)

We define the multisets

$$ \mathit{Events}(\mu \mathcal{E}v) = \{(\mu, \tilde{a}) \mid (\mu, \tilde{a}) : e(\dots) \in \mu \mathcal{E}v\} $$

$$ \mathit{Events}(E, \sigma, M, \mathcal{T}, \mu \mathcal{E}v) = \mathit{Events}(\mathrm{Im}(\sigma), M) \uplus \mathit{Events}(\mu \mathcal{E}v) $$

$$ \mathit{Events}(Q, \mathcal{O}r) = \bigcup_{(\sigma', Q') \in Q} \mathit{Events}(\mathrm{Im}(\sigma'), Q') $$

$$ \mathit{Events}(E, St, Q, \mathcal{O}r, \mathcal{T}, \mu \mathcal{E}v) = \bigcup_{(\sigma, P) \in St} \mathit{Events}(\mathrm{Im}(\sigma), P) \uplus $$

$$ \bigcup_{(\sigma', Q') \in Q} \mathit{Events}(\mathrm{Im}(\sigma'), Q') \uplus \mathit{Events}(\mu \mathcal{E}v) $$

The latter multiset contains all pairs $(\mu, \tilde{a})$ (program point, value of replication indices) for events $e(\dots)$ that may be executed in a trace that contains the configuration $E, St, Q, \mathcal{O}r, \mathcal{T}, \mu \mathcal{E}v$.

The multiset $\mathit{Events}(\sigma_0, C[Q_0])$ contains no duplicates. Indeed, we show by induction on $M$ that $\mathit{Events}(\tilde{a}, M)$ is included in the multiset $\{(\mu, \tilde{a}')\}$ where $\mu$ is a program point inside $M$ and $\tilde{a}$ is a prefix of $\tilde{a}'$, and similarly for $P$ and $Q$. That allows to show that all multiset unions in the computation of $\mathit{Events}$ are disjoint unions, since all recursive calls in the computation of $\mathit{Events}$ are either with disjoint processes or terms, or with different extensions of $\tilde{a}$.

Moreover, by induction on the derivations, if $E, \sigma, M, \mathcal{T}, \mu \mathcal{E}v \xrightarrow{p} t E', \sigma', M', \mathcal{T}', \mu \mathcal{E}v'$, then $\mathit{Events}(E, \sigma, M, \mathcal{T}, \mu \mathcal{E}v) \supseteq \mathit{Events}(E', \sigma', M', \mathcal{T}', \mu \mathcal{E}v')$; if $Q, \mathcal{O}r \rightsquigarrow Q', \mathcal{O}r'$, then $\mathit{Events}(Q, \mathcal{O}r) \supseteq \mathit{Events}(Q', \mathcal{O}r')$; and if $\mathit{Conf} \xrightarrow{p} t \mathit{Conf}'$, then $\mathit{Events}(\mathit{Conf}) \supseteq \mathit{Events}(\mathit{Conf}')$.

Therefore, the multiset $\mathit{Events}(\{(\sigma_0, C[Q_0])\}, (\mathrm{fo}(C[Q_0]), \emptyset))$ contains no duplicates, and neither do the multisets $\mathit{Events}(\mathrm{reduce}(\{(\sigma_0, C[Q_0])\}), (\mathrm{fo}(C[Q_0]), \emptyset))$, $\mathit{Events}(\mathrm{initConfig}(C[Q_0], \mathcal{A}))$,
and Events(Conf), where Conf = E, St, Q, Or, T, μEv is the final configuration of the considered trace. Hence, Events(μEv) contains no duplicates, which implies the desired result. □

**Lemma 42** Let $\varphi = [\forall \tilde{x} : \tilde{T}; \psi \Rightarrow \exists \tilde{y} : \tilde{T}'; \phi]$ be a correspondence that does not use non-unique events, with $\psi = F_1 \wedge \dots \wedge F_m$, $\tilde{x} = \text{var}(\psi)$, and $\tilde{y} = \text{var}(\phi) \setminus \text{var}(\psi)$. Let $Q_0$ be a process that satisfies Properties 3 and 4. Suppose that, in $Q_0$, the arguments of the events that occur in $\psi$ are always simple terms.

Let $S = \{(\mu_1, c_1, \dots, \mu_m, c_m) \mid \forall j \le m, \mu_j \text{ executes } F_j \text{ and } c_j \text{ is a case for } \mathcal{F}_{\mu_j, c_j}\}$. Let $C$ be an evaluation context acceptable for $Q_0$ with public variables $V$ that does not contain events used by $\varphi$ and $A$ be an attacker in $BB$. Let $\text{Tr}$ be a full trace of $C[Q_0]$ for $A$ that does not execute any non-unique event of $Q_0$. If $\text{Tr} \vdash \neg \varphi$, then for any family of substitutions $\theta$ equal to the identity on $\tilde{x}$, for any pseudo-formula $C$, $\text{Tr} \vdash \neg[\text{prove}^{\varphi}(C, \theta, S)]$.

**Proof** By contraposition, we suppose that, $\text{Tr} \vdash [\text{prove}^{\varphi}(C, \theta, S)]$, so for every $\mu_1$ that executes $F_1, \dots$, for every $\mu_m$ that executes $F_m$, for every $c_1, \dots, c_m$, $\text{Tr} \vdash [\text{prove}^{\varphi}(C, \theta, \mu_1, c_1, \dots, \mu_m, c_m)]$ and $\text{Tr} \vdash [\vdash C]$, and we show that $\text{Tr} \vdash \varphi$.

Let $\mu Ev$ be the sequence of events in the last configuration of $\text{Tr}$.

We use the notations of Definition 12. We construct the functions $f_1, \dots, f_k$ as follows. Let $\rho$ be a mapping of $\tau_1, \dots, \tau_m$ to elements of $\mathbb{N}$ and of $\tilde{x}$ to elements of $\tilde{T}$. Suppose that $\text{Tr}, \rho \vdash \psi^\tau$. Then, for all $j \le m$, $\text{Tr}, \rho \vdash F_j^\tau$. By Lemma 38, there exists a program point $\mu_j$ (in $Q_0$) that executes $F_j$ and a case $c_j$ such that, for any $\theta_j$ renaming of $I_{\mu_j}$ to fresh replication indices, there exists a mapping $\sigma_j$ with domain $\theta_j I_{\mu_j}$ such that $\mu Ev(\rho(\tau_j)) = (\mu_j, \sigma_j(\theta_j I_{pp_j})) : \dots$ and $\text{Tr}, \sigma_j \vdash \rho \vdash \theta_j \mathcal{F}_{F_j, \mu_j, c_j}$. Let $\rho_1 = \sigma_1 \cup \dots \cup \sigma_m \cup \rho$. We have $\text{Tr}, \rho_1 \vdash \theta_1 \mathcal{F}_{F_1, \mu_1, c_1} \cup \dots \cup \theta_m \mathcal{F}_{F_m, \mu_m, c_m} \cup \{\neg \text{formula}(\text{prove}^{\varphi}(C, \theta, \mu_1, c_1, \dots, \mu_m, c_m))\}$. By Lemma 40, $[\text{prove}^{\varphi}(C, \theta, \mu_1, c_1, \dots, \mu_m, c_m)] \Rightarrow \forall \theta_1 I_{\mu_1}, \dots, \forall \theta_m I_{\mu_m}, \forall \tilde{x} \in \tilde{T}, \neg \bigwedge \mathcal{F}(C, \theta, \mu_1, c_1, \dots, \mu_m, c_m)$. So $\text{Tr} \vdash \forall \theta_1 I_{\mu_1}, \dots, \forall \theta_m I_{\mu_m}, \forall \tilde{x} \in \tilde{T}, \neg \bigwedge \mathcal{F}(C, \theta, \mu_1, c_1, \dots, \mu_m, c_m)$.

Let $\mathcal{F}(C, \theta, \mu_1, c_1, \dots, \mu_m, c_m) = \theta_1 \mathcal{F}_{F_1, \mu_1, c_1} \cup \dots \cup \theta_m \mathcal{F}_{F_m, \mu_m, c_m} \cup \{\neg \text{formula}(\text{prove}^{\varphi}(C, \theta, \mu_1, c_1, \dots, \mu_m, c_m))\}$. By Lemma 40, $[\text{prove}^{\varphi}(C, \theta, \mu_1, c_1, \dots, \mu_m, c_m)] \Rightarrow \forall \theta_1 I_{\mu_1}, \dots, \forall \theta_m I_{\mu_m}, \forall \tilde{x} \in \tilde{T}, \neg \bigwedge \mathcal{F}(C, \theta, \mu_1, c_1, \dots, \mu_m, c_m)$.

Then $\text{Tr}, \rho_1 \vdash \neg \bigwedge \mathcal{F}(C, \theta, \mu_1, c_1, \dots, \mu_m, c_m)$, so $\text{Tr}, \rho_1 \vdash \text{formula}(\text{prove}^{\varphi}(C, \theta, \mu_1, c_1, \dots, \mu_m, c_m))$, that is, $\text{Tr}, \rho_1 \vdash \text{formula}(\mathcal{F} \models_{\theta}^{\mathcal{I}, \mathcal{V}, \mathcal{C}} \phi)$, with $\mathcal{F} = \theta_1 \mathcal{F}_{F_1, \mu_1, c_1} \cup \dots \cup \theta_m \mathcal{F}_{F_m, \mu_m, c_m}$, $\mathcal{I} = \{j \mapsto (\mu_j, \theta_j I_{\mu_j}) \mid F_j \text{ is an injective event}\}$, $\mathcal{V} = \text{var}(\theta_1 I_{\mu_1}) \cup \dots \cup \text{var}(\theta_m I_{\mu_m}) \cup \{\tilde{x}\}$, and $\theta = \theta(\mu_1, c_1, \dots, \mu_m, c_m)$.

Consider an injective event in $\phi$, associated to function $f_l$.

* If that injective event corresponds to

$$ \bigvee_{(\mathcal{F}, N_0, \mathcal{I}, \mathcal{V}) \in \mathcal{S}} \exists \tau \in \mathbb{N}, N_0 : \theta \text{event}(e(M_1, \dots, M_m)) @ \tau $$

in formula $(\mathcal{F} \models_{\theta}^{\mathcal{I}, \mathcal{V}, \mathcal{C}} \phi)$, we have

$$ \text{Tr}, \rho_1 \vdash \bigvee_{(\mathcal{F}, N_0, \mathcal{I}, \mathcal{V}) \in \mathcal{S}} \exists \tau \in \mathbb{N}, N_0 : \theta \text{event}(e(M_1, \dots, M_m)) @ \tau $$

since formula $(\mathcal{F} \models_{\theta}^{\mathcal{I}, \mathcal{V}, \mathcal{C}} \phi)$ is a conjunction. So $\text{Tr}, \rho_1[\tau \mapsto a] \vdash N_0 : \theta \text{event}(e(M_1, \dots, M_m))@\tau$ for some $a \in \mathbb{N}$ and some $N_0$ such that $(\mathcal{F}, N_0, \mathcal{I}, \mathcal{V}) \in \mathcal{S}$. We define $f_l(\rho(\tau_l), \dots, \rho(\tau_m), \rho(\tilde{x})) = a$, so that $\text{Tr}, \rho_1 \vdash N_0 : \theta \text{event}(e(M_1, \dots, M_m))@f_l(\tau_1, \dots, \tau_m, \tilde{x})$.

Moreover, if $j \in I$, then $F_j$ is an injective event, $F_j = \text{inj-event}(e_j(M_{j,1}, \dots, M_{j,m}))$. Moreover, $\text{Tr}, \rho \vdash \psi^\tau$, so $\text{Tr}, \rho \vdash F_j^\tau$, so $\text{Tr}, \rho \vdash \text{event}(e_j(M_{j,1}, \dots, M_{j,m}))@\tau_j$. Since $\mu Ev(\rho(\tau_j)) = (pp_j, \sigma_j(\theta_j I_{\mu_j})) : \dots = (\mu_j, \rho_1(\theta_j I_{\mu_j})) : \dots$ and $\mathcal{I}(j) = (\mu_j, \theta_j I_{\mu_j})$, we have $\text{Tr}, \rho_1 \vdash \mathcal{I}(j) : \text{event}(e_j(M_{j,1}, \dots, M_{j,m}))@\tau_j$.
• If that injective event is in a removed disjunct in formula_36 (F |→<sub>θ</sub><sup>I,V,C</sup> φ), then we define
$f_l(\rho(\tau_1), \dots, \rho(\tau_m), \rho(\tilde{x})) = \perp.$

Then we have $\mathrm{Tr}, \rho_1 \vdash \theta\phi^\tau$, so $\mathrm{Tr}, \rho_1 \vdash \exists\tilde{y} \in \tilde{T}', \phi^\tau$.

Hence, applying this construction for all $\rho$, we obtain $\mathrm{Tr} \vdash \forall \tau_1, \dots, \tau_m \in \mathbb{N}, \forall \tilde{x} \in \tilde{T}, (\psi^\tau \Rightarrow \exists \tilde{y} \in \tilde{T}', \phi^\tau)$. It remains to show $\mathrm{Inj}(I, f_l)$ for each $l \in \{1, \dots, k\}$.

Suppose $f_l(a_1, \dots, a_m, \tilde{a}) = f_l(a'_1, \dots, a'_m, \tilde{a}') \neq \perp$. Let $\rho = \{\tau_1 \mapsto a_1, \dots, \tau_m \mapsto a_m, \tilde{x} \mapsto \tilde{a}\}$. Let $S$ be the leaf of $\mathcal{C}$ corresponding to the event associated to $f_l$. By the construction above, we have $\theta$, $(\mathcal{F}, N_0, \mathcal{I}, \mathcal{V}) \in S$, and an extension $\rho_1$ of $\rho$ such that

$$
\mathrm{Tr}, \rho_1 \vdash N_0 : \theta \mathrm{event}(e(M_1, \dots, M_m)) @ f_l(\tau_1, \dots, \tau_m, \tilde{x}) \quad (24)
$$

$$
\mathrm{Tr}, \rho_1 \vdash \mathcal{F} \tag{25}
$$

$$
\text{for } j \in I, \mathrm{Tr}, \rho_1 \vdash \mathcal{I}(j) : \mathrm{event}(e_j(M_{j,1}, \dots, M_{j,m})) @ \tau_j \quad (26)
$$

Let $\rho' = \{\tau_1 \mapsto a'_1, \dots, \tau_m \mapsto a'_m, \tilde{x} \mapsto \tilde{a}'\}$. In the same way, we have $\theta', (\mathcal{F}', N'_0, \mathcal{I}', \mathcal{V}') \in \mathcal{S}$, and an extension $\rho'_1$ of $\rho'$ such that

$$
\mathrm{Tr}, \rho_1' \vdash N_0' : \theta' \mathrm{event}(e(M_1, \dots, M_m)) @ f_l(\tau_1, \dots, \tau_m, \tilde{x})
$$

$$
\mathrm{Tr}, \rho_1' \vdash \mathcal{F}'
$$

$$
\text{for } j \in I, \mathrm{Tr}, \rho_1' \vdash \mathcal{I}'(j) : \mathrm{event}(e_j(M_{j,1}, \dots, M_{j,m})) @ \tau_j.
$$

Let $\theta''$ be a renaming of the domain of $\rho_1'$ to fresh variables. We have

$$
\mathrm{Tr}, \rho_1' \theta''^{-1} \vdash \theta'' N_0' : \theta'' \theta' \mathrm{event}(e(M_1, \dots, M_m)) @ f_l(\tau_1, \dots, \tau_m, \tilde{x}) \quad (27)
$$

$$
\mathrm{Tr}, \rho_1' \theta''^{-1} \vdash \theta'' \mathcal{F}' \qquad (28)
$$

$$
\text{for } j \in I, \mathrm{Tr}, \rho_1' \theta''^{-1} \vdash \theta'' \mathrm{event}(e_j(\mathcal{I}'(j), M_{j,1}, \dots, M_{j,m})) @ \tau_j . \quad (29)
$$

Therefore, by (24) and (27),

$$
\mathrm{Tr}, \rho_1 \cup \rho_1' \theta''^{-1} \vdash \theta N_0 : \mathrm{event}(e(M_1, \dots, M_m)) @ f_l(a_1, \dots, a_m, \tilde{a})
$$

$$
\mathrm{Tr}, \rho_1 \cup \rho_1' \theta''^{-1} \vdash \theta'' N_0' : \theta'' \theta' \mathrm{event}(e(M_1, \dots, M_m)) @ f_l(a_1, \dots, a'_m, \tilde{a}').
$$

Since $f_l(a_1, \dots, a_m, \tilde{a}) = f_l(a'_1, \dots, a'_m, \tilde{a}')$, the events are the same, so

$$
\mathrm{Tr}, \rho_1 \cup \rho_1' \theta''^{-1} \vdash N_0 = \theta'' N_0'. \quad (30)
$$

We also have by (25) and (28),

$$
\mathrm{Tr}, \rho_1 \cup \rho_1' \theta''^{-1} \vdash \mathcal{F} \cup \theta'' \mathcal{F}'. \quad (31)
$$

Since $\mathrm{Tr} \vdash \{\llcorner \mid \mathcal{C}\}$, we have

$$
\mathrm{Tr}, \rho_1 \cup \rho_1' \theta''^{-1} \vdash \neg \left( \bigwedge \mathcal{F} \wedge \bigwedge \theta'' \mathcal{F}' \wedge \left( \bigvee_{j \in \mathrm{Dom}(\mathcal{I})} \mathcal{I}(j) \neq \theta'' \mathcal{I}'(j) \right) \wedge N_0 = \theta'' N_0' \right)
$$

so using (31) and (30), we conclude that

$$
\mathrm{Tr}, \rho_1 \cup \rho_1' \theta''^{-1} \vdash \bigwedge_{j \in I} \mathcal{I}(j) = \theta'' \mathcal{I}'(j)
$$

since $\mathrm{Dom}(\mathcal{I}) = I$. Let $\mu\mathcal{E}v$ be the sequence of events at the end of $\mathrm{Tr}$. For $j \in I$, let $b_j = \rho_1(\mathcal{I}(j)) = \rho_1'(\mathcal{I}'(j))$. By (26) and (29), we have $\mu\mathcal{E}v(a_j) = b_j : e_j(\dots)$ and $\mu\mathcal{E}v(a'_j) = b_j : e_j(\dots)$. By Lemma 41, we have $a_j = a'_j$. That proves $\mathrm{Inj}(I, f_l)$, and concludes the proof that $\mathrm{Tr} \vdash \varphi$. $\square$
**Proof of Proposition 3** Let $C$ be an evaluation context acceptable for $Q_0$ with public variables $V$ that does not contain events used by $\varphi$ and $A$ be an attacker in $BB$. We have

$$
\begin{align*}
\mathrm{Adv}_{Q_0}(A, C, \varphi, D_{\mathrm{false}}) &= \mathrm{Pr}^A[C[Q_0] : \neg\varphi \wedge \neg\mathrm{NonUnique}_{Q_0}] \\
&\leq \mathrm{Pr}^A[C[Q_0] : \neg\{[\mathrm{prove}^\varphi(C, \theta, S)]\}] \quad \text{by Lemma 42} \\
&\leq \mathrm{Pr}^A[C[Q_0] \leq \neg\{[\mathrm{prove}^\varphi(C, \theta, S)]\}] \quad \text{by Lemma 1} \\
&\leq p(A, C)
\end{align*}
$$

So $\mathrm{Bound}_{Q_0}(V, \varphi, D_{\mathrm{false}}, p)$. $\square$

**Example 7** Let us prove that the example $G_1$ satisfies (6). We prove the correspondence $(\forall \tilde{x} : \tilde{T}; \psi \Rightarrow \exists \tilde{y} : \tilde{T}'; \phi) = (\forall x : pkey, y : host, z : nonce; \mathrm{inj-event}(e_B(x, y, z)) \Rightarrow \mathrm{inj-event}(e_A(x, y, z)))$. The program point $\mu_B$ executes $F = \mathrm{event}(e_B(x, y, z))$ and $\mathcal{F} = \theta' \mathcal{F}_{F, \mu_B} \supseteq \theta' \mathcal{F}_{\mu_B} \{i'_B/i_B\} \cup \{x_{pk_A}[i'_B] = x, B = y, N[i'_B] = z\}$ with $\theta' = \{i'_B/i_B\}$.

As in the proof of $\mathcal{F} \models_{\theta(\mu_B)} \mathrm{event}(e_A(x, y, z))$ in Example 6, we show $\mathcal{F} \models_{\theta(\mu_B)}^{\mathcal{I}, \mathcal{V}, \mathcal{C}} \mathrm{event}(e_A(x, y, z))$ where $\mathcal{I} = \{1 \mapsto (\mu_B, i'_B)\}$ encodes the program points and replication indices of the events of $\psi$, $\mathcal{V} = \{i'_B, x, y, z\}$ contains the replication indices of $\mathcal{F}$ and the variables of $\psi$, $\mathcal{C} = \mathcal{S} = \{(\mathcal{F}, (\mu_A, u[i'_B]), \mathcal{I}, \mathcal{V})\}$. ($\mathcal{C} = \mathcal{S}$ because the formula $\psi$ is reduced to a single event; $M'_0 = (\mu_A, u[i'_B])$ contains the program point and replication indices of the event $e_A$ contained in $\mathcal{F}: (\mu_A, u[i'_B]) : \mathrm{event}(e_A(pk_A, x_B[u[i'_B]], x_N[u[i'_B]])) \in \mathcal{F}$.)

In order to prove injectivity, it remains to show that $\vdash C$. Let $\theta'' = \{i''_B/i'_B, x''/x, y''/y, z''/z\}$. We need to show that $\mathcal{F} \cup \theta''\mathcal{F} \cup \{(\mu_B, i'_B) \neq (\mu_B, i''_B), (\mu_A, u[i'_B]) = (\mu_A, u[i''_B])\}$ yields a contradiction, that is, if the pairs (program point, replication indices) of the event $e_B$ in $\psi$ are distinct ($(\mu_B, i'_B) \neq (\mu_B, i''_B)$), then the pairs (program point, replication indices) of the event $e_A$ in $\phi$ are also distinct ($(\mu_A, u[i'_B]) \neq (\mu_A, u[i''_B])$).

$\mathcal{F}$ contains $N[i'_B] = x_N[u[i'_B]]$, so $\theta''\mathcal{F}$ contains $N[i''_B] = x_N[u[i''_B]]$. These two equalities combined with $u[i'_B] = u[i''_B]$ imply that $N[i'_B] = x_N[u[i'_B]] = x_N[u[i''_B]] = N[i''_B]$. Since $N$ is defined by random choices of the large type *nonce*, $N[i'_B] = N[i''_B]$ implies $i'_B = i''_B$ up to probability $n^2/2|\mathrm{nonce}|$, by eliminating collisions. This equality contradicts $(\mu_B, i'_B) \neq (\mu_B, i''_B)$, so we obtain the desired injectivity. Therefore, the game $G_1$ satisfies (6) with any public variables $V$ up to probability $n^2/2|\mathrm{nonce}|$.

# 5 Game Transformations

## 5.1 Syntactic Game Transformations

### 5.1.1 auto SArename

The transformation `auto SArename` renames all variables defined in conditions of find, so that they have distinct names. This transformation is a particular case of `SArename` (Section 5.1.7) that is particularly simple because these variables do not have array accesses by Invariant 3.

**Lemma 43** The transformation `auto SArename` requires and preserves Properties 1, 2, and 3. It preserves Property 5. If transformation `auto SArename` transforms $G$ into $G'$, then $D, D_{SNU}: G, D, \mathrm{EvUsed} \xrightarrow{V} _0 G', D, \mathrm{EvUsed}$ and $G'$ satisfies Property 4.
### 5.1.2 expand_tables [33]

The transformation **expand_tables** transforms **insert** and **get** into **find**, since the other transformations do not support tables. It proceeds by storing the inserted list elements in fresh array variables, and looking up in these arrays instead of performing **get**. More precisely, when insert Tbl(M₁, ..., Mₖ); P is under the replications **foreach** i₁ ≤ n₁ do ... **foreach** iₗ ≤ nₗ do , it is transformed into

$$ \text{let } y_1[i_1, \dots, i_l] = M_1 \text{ in } \dots \text{let } y_k[i_1, \dots, i_l] = M_k \text{ in } P $$

where y₁, ..., yₖ are fresh array variables, and we add (y₁, ..., yₖ; i₁ ≤ n₁, ..., iₗ ≤ nₗ) in a set S', to remember them. The construct **get[unique?]** Tbl(x₁: T₁, ..., xₖ: Tₖ) suchthat M in P else P' is then transformed into

$$ \text{find}[\text{unique?}] \quad \left( \bigoplus_{(y_1, \dots, y_k; i_1 \le n_1, \dots, i_l \le n_l) \in S'} \left( \begin{array}{l} u_1 = i'_1 \le n_1, \dots, u_l = i'_l \le n_l \text{ suchthat} \\ \text{defined}(y_1[\tilde{i}'], \dots, y_k[\tilde{i}']) \land M\{y_1[\tilde{i}']/x_1, \dots, y_k[\tilde{i}']/x_k\} \\ \text{then let } x_1 = y_1[\tilde{u}] \text{ in } \dots \text{let } x_k = y_k[\tilde{u}] \text{ in } P \end{array} \right) \right) \\ \text{else } P' $$

where [unique?] is either [unique<sub>e</sub>] or empty and has the same value at both occurrences, $\tilde{u}$ stands for $u_1, \dots, u_l$, and $\tilde{i}'$ stands for $i'_1, \dots, i'_l$. This construct looks in all arrays used for translating insertion in table Tbl, for indices $\tilde{i}'$ such that $y_1[\tilde{i}']$, ..., $y_k[\tilde{i}']$ are defined, that is, an element has been inserted at indices $\tilde{i}'$, and $M\{y_1[\tilde{i}']/x_1, \dots, y_k[\tilde{i}']/x_k\}$ is true, that is, that element satisfies M. When it finds such an element, it stores it in $x_1, \dots, x_k$, and runs P. (When it finds several elements, one of them is chosen randomly with uniform probability when [unique?] is empty and the non-unique event e is raised when [unique?] is [unique<sub>e</sub>].) When it finds no element, it executes P'. These transformations are described for processes, but similar transformations are performed for **insert** and **get** terms.

After this transformation, **expand_tables** calls **auto_SArename** to guarantee Property 4.

**Lemma 44** The transformation **expand_tables** requires and preserves Properties 1 and 2. It preserves Property 5. If transformation **expand_tables** transforms G into G', then D, D<sub>SNU</sub>: G, D, EvUsed $\xrightarrow{V}$<sub>p</sub> G', D, EvUsed, where p is $\epsilon_{find}$ times the maximal number of executions of get in G that is not obviously unique (that is, such that the insert in that table may be executed several times), and G' satisfies Properties 3 and 4.

### 5.1.3 expand

The transformation **expand** transforms terms $\stackrel{R}{\rightleftharpoons}$, let, if, find, event, and event_abort into processes, so that Property 5 is guaranteed. It simplifies the generated game on the fly, using many of the rules of **simplify** (Section 5.1.21), to avoid generating branches that can actually not be executed.

After this transformation, **expand** calls **auto_SArename** to guarantee Property 4.

**Lemma 45** The transformation **expand** requires and preserves Properties 1, 2, 3, and 4. If transformation **expand** transforms G into G', then D, D<sub>SNU</sub>: G, D, EvUsed $\xrightarrow{V}$<sub>p</sub> G', D, EvUsed, where p is an upper bound of the probability that the simplification steps modify the execution, and G' satisfies Property 5.
### 5.1.4 prove_unique

The transformation **prove_unique** tries to prove that each find[unique<sub>e</sub>] really has a unique possibility at runtime (up to a small probability), so that event *e* is executed with at most that probability. More precisely, find[unique] are already proved; find[unique<sub>e</sub>] for which no query event(*e*) ⇒ false is active are also considered as already proved (they will be proved elsewhere; with the notations of Definition 6, *e* does not occur in D<sub>1</sub> ∨ D, so *e* occurs in NonUnique<sub>Q,D<sub>1</sub>∩D</sub>), and they are replaced with find[unique]. That corresponds to renaming event *e* to a special non-unique event that is always in NonUnique<sub>Q,D<sub>1</sub>∩D</sub>. It remains to prove find[unique<sub>e</sub>] for which a query event(*e*) ⇒ false is active.

Suppose that $P_0 = \text{find}[\text{unique}_e] (\bigoplus_{j=1}^m \tilde{u}_j[\tilde{i}] = \tilde{i}_j \le \tilde{n}_j \text{ suchthat } \text{defined}(M_{j1}, \dots, M_{jl_j}) \wedge M_j)$
then $P_j$ else $P$ is such a find$[\text{unique}_e]$. (The same transformation is performed for find$[\text{unique}_e]$
terms.) CryptoVerif proves uniqueness by proving

* that we obtain a contradiction if the condition of a certain branch holds for two different values of the indices $\tilde{i}_j$, that is, for all $j \in \{1, \dots, m\}$, $\mathcal{F}_{P_0} \cup \{\text{defined}(M_{j1}), \dots, \text{defined}(M_{jl_j})\}$, $M_j$, $\text{defined}(\theta M_{j1}), \dots, \text{defined}(\theta M_{jl_j}), \theta M_j, \tilde{i}_j \neq \theta \tilde{i}_j$}^{}$ yields a contradiction, where the substitution $\theta$ maps $\tilde{i}_j$ to fresh replication indices;

* and that we obtain a contradiction if the conditions of two different branches hold simultaneously, that is, for all $j, j' \in \{1, \dots, m\}$ with $j < j'$, $\mathcal{F}_{P_0} \cup \{\text{defined}(M_{j1}), \dots, \text{defined}(M_{jl_j})\}$, $M_j$, $\text{defined}(\theta M_{j'1}), \dots, \text{defined}(\theta M_{j'l_j})$, $\theta M_{j'}$}^{}$ yields a contradiction, where the substitution $\theta$ maps $\tilde{i}_{j'}$ to fresh replication indices. (The substitution $\theta$ is useful in case the same replication indices are used in both branches $j$ and $j'$.)

When uniqueness is proved, find[unique<sub>e</sub>] is replaced with find[unique]. A subsequent call to **success** (Section 4) will remove the query event(*e*) ⇒ false when event *e* no longer occurs in the game.

**Lemma 46** *The transformation prove_unique requires and preserves Properties 1, 2, 3, and 4. It preserves Property 5. If transformation prove_unique transforms G into G', then D, D<sub>SNU</sub>: G, D, EvUsed <sup>V</sup>&rarr;p G', D, EvUsed, where p is an upper bound on the probability that a find[unique<sub>e</sub>] proved in the transformation actually executes event e.*

### 5.1.5 remove_assign [26]

The transformation **remove_assign** applied to an assignment let $x[i_1, \dots, i_l] : T = M$ in $P$ replaces $x$ with its value $M$. (The same transformation is performed for assignment terms.) Precisely, the transformation is performed only when $x$ does not occur in $M$ (non-cyclic assignment) and $M$ contains only variables, function applications, and tests (otherwise, copying the definition of $x$ may break the invariant that each variable is assigned at most once). When $x$ has several distinct definitions, we simply replace $x[i_1, \dots, i_l]$ with $M$ in $P$. (For accesses to $x$ guarded by find, we do not know which definition of $x$ is actually used.) When $x$ has a single definition or several identical definitions, we replace everywhere in the game $x[M_1, \dots, M_l]$ with $M\{M_1/i_1, \dots, M_l/i_l\}$. We additionally update the **defined** conditions of **find** to preserve Invariant 2 and to make sure that, if a condition of **find** guarantees that $x[M_1, \dots, M_l]$ is defined in the initial game, then so does the corresponding condition of **find** in the transformed game. (Essentially, when $y[M_1'', \dots, M_l'']$ occurs in $M$, the transformation typically creates new occurrences of $y[M_1'', \dots, M_l'']$ for some $M_1'', \dots, M_l''$, so the condition that $y[M_1'', \dots, M_l'']$ is defined must sometimes be explicitly added to conditions of **find** in order to preserve Invariant 2.) Moreover, we replace as often as possible defined conditions $x[M_1, \dots, M_l]$ with defined conditions
$y[M_1, ..., M_l]$ where $y$ is defined at the same time as $x$. When $x \in V$, its definition is kept unchanged. Otherwise, when $x$ is not referred to at all after the transformation, we remove the definition of $x$. When $x$ is referred to only at the root of **defined** tests, we replace its definition with a constant. (The definition point of $x$ is important, but not its value.)

This removal of assignments is applied to all variables whose value is not used (those are used only at the root of **defined** conditions, or not at all). Depending on the argument of the transformation, it is also applied to other assignments:

* **findcond**: all assignments in conditions of find;

* **useless**: assignments that store a variable or a replication index, when the setting **ex-pandAssignXY** is true; otherwise, no other assignment;

* **binder** $x_1 ... x_n$: the assignments to variables $x_1, ..., x_n$.

After this transformation, **remove_assign** calls **auto_SArename** to guarantee Property 4.

With the arguments **findcond** and **useless**, this is repeated as many times as specified by the setting **maxIterRemoveUselessAssign**. Repetition stops if a fixpoint is reached.

**Lemma 47** *The transformation remove_assign requires and preserves Properties 1, 2, 3, and 4. It preserves Property 5. If transformation remove_assign transforms $G$ into $G'$, then $D, D_{SNU}: G, D, EvUsed \xrightarrow{V} G', D, EvUsed$.*

**Example 8** In the game $G_0$ of Section 4.2.1, the transformation **remove_assign binder sk_A** substitutes skgen($rk_A$) for $sk_A$ in the whole process and removes the assignment let $sk_A = skgen(rk_A)$. After this substitution, sign concat($pk_A, x_B, x_N$), $sk_A, r$) becomes sign concat($pk_A, x_B, x_N$), skgen($rk_A$), r) thus exhibiting a term required to apply the security assumption on signatures in the cryptographic transformation of Section 5.2.

### 5.1.6 **use_variable**

The transformation **use_variable** $x_1 ... x_m$ tries to use variables $x_1, ..., x_n$ instead of recomputing their value. More precisely, at each program point that corresponds to a simple term $M$ and where $x_j[\tilde{M}]$ is guaranteed to be defined (because $x_j$ is defined above that program point or directly or indirectly because of **defined** conditions above that program point), if all definitions of $x_j$ that can be executed before reaching that program point are let $x_j[i] = M_0$ in, then we test whether $M$ is equal to $M_0\{\tilde{M}/i\}$ modulo the built-in equations, and if yes, we replace $M$ with $x_j[\tilde{M}]$.

The **defined** conditions of **find** above the modified program points are updated to make sure that Invariant 2 is preserved. This is needed in particular to make sure that $x_j[\tilde{M}]$ syntactically occurs in the **defined** conditions when it is used.

**Lemma 48** *The transformation use_variable requires and preserves Properties 1, 2, 3, and 4. It preserves Property 5. If transformation use_variable transforms $G$ into $G'$, then $D, D_{SNU}: G, D, EvUsed \xrightarrow{V} G', D, EvUsed$.*

The transformation **use_variable** is a convenient way to perform common subexpression elimination, possibly by first inserting the definition of the desired variable(s) by **insert** (Section 5.1.13). This transformation could also be done by several applications of **replace** (Section 5.1.14). However, **use_variable** is easier to use when it performs the desired replacement.
For performance reasons, the equality tests performed by **use_variable** are considerably less powerful than those performed by **replace**, so if **use_variable** does not replace a term with $x_j[\bar{M}]$ at some occurrence, it is worth trying **replace**.

### 5.1.7 SAname [26]

The transformation **SAname** $x$ (single assignment rename) aims at renaming $x$ so that distinct definitions of $x$ have different names; this is useful for distinguishing cases depending on which definition of $x$ has set $x[i]$. This transformation can be applied only when $x \notin V$. When $x$ has $m > 1$ definitions, we rename each definition of $x$ to a different variable $x_1, \dots, x_m$. Terms $x[i]$ under a definition of $x_j[i]$ are then replaced with $x_j[i]$. Each branch of find $FB = \tilde{u}[i] = \tilde{i}' \le \tilde{n}$ such that defined($M'_1, \dots, M'_{l'}$) AND $M$ then ... where $x[M_1, \dots, M_l]$ is a subterm of some $M'_k$ for $k \le l'$ is replaced with $m$ branches $FB\{x_j[M_1, \dots, M_l]/x[M_1, \dots, M_l]\}$ for $1 \le j \le m$.

Moreover, the implementation takes into account that some variables cannot be simultaneously defined, to reduce the number of branches of find to generate.

After this transformation, **SAname** calls **auto_SAname** to guarantee Property 4.

As a particular case, **SAname random** performs the following transformation: when $y$ is defined by $y \stackrel{R}{\leftarrow} T$ and has $m > 1$ definitions and all variable accesses to $y$ are of the form $y[i_1, \dots, i_l]$ under a definition of $y[i_1, \dots, i_l]$, where $i_1, \dots, i_l$ are the current replication indices at this definition of $y$ (that is, $y$ has no array access using find), it renames $y$ to $y_1, \dots, y_m$ with a different name for each definition of $y$ by $y \stackrel{R}{\leftarrow} T$.

**Lemma 49** The transformation **SAname** requires and preserves Properties 1, 2, 3, and 4. It preserves Property 5. If transformation **SAname** transforms $G$ into $G'$, then $D, D_{SNU} : G, D, EvUsed \xrightarrow{V} P_1 G', D, EvUsed$, where $p$ is $\epsilon_{find}$ times the maximal number of executions of a modified find that is not proved unique.

**Example 9** Consider the following process

$$
\begin{align*}
\text{Start}() &:= k_A \stackrel{R}{\leftarrow} T_k; k_B \stackrel{R}{\leftarrow} T_k; \text{return} (); (Q_K | Q_S) \\
Q_K &= \text{foreach } i \le n \text{ do } O[i](h : T_h, k : T_k) := \\
    &\quad \text{if } h = A \text{ then let } k' : T_k = k_A \text{ in return } () \text{ else} \\
    &\quad \text{if } h = B \text{ then let } k' : T_k = k_B \text{ in return } () \text{ else} \\
    &\quad \text{let } k' : T_k = k \text{ in return } () \\
Q_S &= \text{foreach } i' \le n' \text{ do } O'[i'](h' : T_h) := \\
    &\quad \text{find } u = i'' \le n \text{ such that defined}(h[i''], k'[i'']) \land h' = h[i''] \text{ then } P_1(k'[u]) \text{ else } P_2
\end{align*}
$$

The process $Q_K$ stores in $(h, k')$ a table of pairs (host name, key): the key for $A$ is $k_A$, for $B$, $k_B$, and for any other $h$, the adversary can choose the key $k$. The process $Q_S$ queries this table of keys to find the key $k'[u]$ of host $h'$, then executes $P_1(k'[u])$. If $h'$ is not found, it executes $P_2$.

By the transformation **SAname** $k'$, we can perform a case analysis, to distinguish the cases in which $k' = k_A$, $k' = k_B$, or $k' = k$, by renaming the three definitions of $k'$ to $k'_1$, $k'_2$, and $k'_3$ respectively. After transformation, we obtain the following processes:

$$
\begin{align*}
Q'_{K} &= \text{foreach } i \le n \text{ do } O[i](h : T_h, k : T_k) := \\
&\quad \text{if } h = A \text{ then let } k'_{1} : T_{k} = k_{A} \text{ in return } () \text{ else} \\
&\quad \text{if } h = B \text{ then let } k'_{2} : T_{k} = k_{B} \text{ in return } () \text{ else} \\
&\quad \text{let } k'_{3} : T_{k} = k \text{ in return } ()
\end{align*}
$$
$$
\begin{align*}
Q'_S &= \forall h' \le i' \le n' \text{ do } O'[i'](h' : T_h) := \\
&\quad \text{find } u = i'' \le n \text{ such that } \text{defined}(h[i''], k'_1[i'']) \wedge h' = h[i''] \text{ then } P_1(k'_1[u]) \\
&\quad \oplus u = i'' \le n \text{ such that } \text{defined}(h[i''], k'_2[i'']) \wedge h' = h[i''] \text{ then } P_1(k'_2[u]) \\
&\quad \oplus u = i'' \le n \text{ such that } \text{defined}(h[i''], k'_3[i'']) \wedge h' = h[i''] \text{ then } P_1(k'_3[u]) \text{ else } P_2
\end{align*}
$$

The find in $Q_S$, which looks for elements in array $k'$, is transformed in $Q'_S$ into a find with three branches, one for each new name of $k'$ ($k'_1$, $k'_2$, and $k'_3$ respectively). After the simplification (Section 5.1.21), $Q'_S$ becomes:

$$
\begin{align*}
Q_S'' &= \forall h' \le i' \le n' \text{ do } O'[i'](h' : T_h) := \\
&\quad \text{find } u = i'' \le n \text{ such that } \text{defined}(h[i''], k'_1[i'']) \wedge h' = A \text{ then } P_1(k_A) \\
&\quad \oplus u = i'' \le n \text{ such that } \text{defined}(h[i''], k'_2[i'']) \wedge h' = B \text{ then } P_1(k_B) \\
&\quad \oplus u = i'' \le n \text{ such that } \text{defined}(h[i''], k'_3[i'']) \wedge h' = h[i''] \text{ then } P_1(k[u]) \text{ else } P_2
\end{align*}
$$

since, when $k'_1[u]$ is defined, $k'_1[u] = k_A$ and $h[u] = A$, and similarly for $k'_2[u]$ and $k'_3[u]$.

### 5.1.8 move [26]

The transformation **move** moves random choices and assignments downwards in the code as much as possible. A random choice $x[i] \stackrel{R}{\leftarrow} T$ or assignment let $x[i] : T = M$ cannot be moved under a replication, or under a parallel composition when both sides use $x$, or a let $y[i] : T = M$ in ... or a return return ($M$) when $x$ occurs in $M$, or a find (or if) when the conditions use $x$. It can be moved under the other constructs, duplicating it if necessary, when we move it under a find (or if) that uses $x$ in several branches. Note that when the random choice $x[i] \stackrel{R}{\leftarrow} T$ or assignment let $x[i] : T = M$ cannot be moved under a parallel composition, or a replication, it must be written above the return that is located above the considered parallel composition or replication, so that the syntax of processes is not violated. When there are array accesses to $x$, the random choice $x[i] \stackrel{R}{\leftarrow} T$ or assignment let $x[i] : T = M$ can be moved only inside the same oracle body, without moving it under a return or under a find that makes an array access to $x$.

The conditions above are necessary for the soundness of the move. Furthermore, the move is considered beneficial when it satisfies the following conditions:

* for random choices, when the random choice can be moved under a find (or if). When this transformation duplicates a $x[i] \stackrel{R}{\leftarrow} T$ by moving it under a find that uses $x$ in several branches, a subsequent SArename($x$) enables us to distinguish several cases depending in which branch $x$ is created, which is useful in some proofs.

* for assignments, when there are no array accesses to $x$, the assignment to $x$ can be moved under a find (or if), and $x$ is used in a single branch of that find (or if). In this case, the assignment can be performed only in the branch that uses $x$, so it will be computed in fewer cases thanks to the move.

The performed moves are determined by the argument of the transformation:

* all: moves all random choices and assignments, provided the move is beneficial.

* noarrayref: moves all random choices and assignments that do not have array references, provided the move is beneficial.

* random: moves all random choices, provided the move is beneficial.
* **random_noarrayref**: moves all random choices that do not have array references, provided the move is beneficial.

* **assign**: moves all assignments, provided the move is beneficial.

* **binder** $x_1 \dots x_n$: move the variables $x_1, \dots, x_n$ (even when the move is not beneficial).

In all cases, only random choices and assignments at the process level (not inside terms) are moved.

**Lemma 50** *The transformation move requires and preserves Properties 1, 2, 3, and 4. It preserves Property 5. If transformation move transforms $G$ into $G'$, then $D, D_{SNU} : G, D, EvUsed \xrightarrow{V} G', D, EvUsed$.*

### 5.1.9 move array [27]

The transformation **move array** $X$ delays the generation of a random value $X$ until the point at which it is first used (lazy sampling). This transformation is implemented as a particular case of a cryptographic transformation by the following equivalence:

```pascal
foreach i ≤ n do X ← R T;
(foreach iX ≤ nX do OX() := return(X) | 
  foreach ieq ≤ neq do Oeq(X' : T) := return(X' = X))
≈\#Oeq/|T| [manual]
foreach i ≤ n do
(foreach iX ≤ nX do OX() := 
  find[unique] j ≤ nX suchthat defined(Y[j])
  then return(Y[j]) else Y ← R T; return(Y) |
  foreach ieq ≤ neq do Oeq(X' : T) := 
  find[unique] j ≤ nX suchthat defined(Y[j])
  then return(X' = Y[j]) else return(false))
```

where $T$ is the type of $X$. Two oracles are defined, OX and Oeq. In the left-hand side, OX returns the random $X$ itself. In the right-hand side, OX uses a lookup to test if the random value was already generated; if yes, it returns the previously generated random value $Y[j]$; if no, it generates a fresh random value $Y$. Transforming the left-hand side into the right-hand side therefore moves the generation of the random number $X$ to the first call to OX, that is, the first usage of $X$. The oracle Oeq provides an optimized treatment of equality tests $X' = X$: when the random value $X$ was not already generated, we return false instead of generating a fresh $X$, so we exclude the case that $X'$ is equal to a fresh $X$. This case has probability $1/|T|$ for each call to Oeq, so the probability of distinguishing the two games is $\#Oeq/|T|$. (Notice that there never exist several choices of $j$ that satisfy the conditions of the finds in the right-hand side of this equivalence, so these finds can be marked [unique] without modifying their behavior.)

**Extension:** A generalization of Oeq with other collisions is now supported by CryptoVerif.

### 5.1.10 move up

The transformation **move up** $x_1 \dots x_n$ to $\mu$ moves the random number generations or assignments of $x_1, \dots, x_n$ upwards in the syntax tree, to the program point $\mu$. This program point must be inside an oracle body.
The program point $\mu$ is an integer, which can be determined using the command **show game occ**: this command displays the current game with the corresponding label $\{\mu\}$ at each program point. The command **show game occ** also allows one to inspect the game, for instance to know the names of fresh variables created by CryptoVerif during previous transformations. Program points and variable names may depend on the version of CryptoVerif. Since CryptoVerif version 2.01, program points can also be designated by expressions like **before regexp**, which designates the program point at the beginning of the line that matches the regular expression *regexp*; **after regexp**, which designates the program point just after the line that matches *regexp*; **before nth n regexp**, which designates the program point at the beginning of the *n*-th line that matches the regular expression *regexp*; **after nth n regexp**, which designates the program point at the beginning of the first line that has an occurrence number after the *n*-th line that matches the regular expression *regexp*; **at n' regexp**, which designates the program point at the *n'*-th occurrence number that occurs inside the string that matches the regular expression *regexp* in the displayed game; **at nth n n' regexp**, which designates the program point at the *n'*-th occurrence number that occurs inside the string corresponding to the *n*-th match of the regular expression *regexp* in the displayed game. This way of designating program points is more stable across versions of CryptoVerif.

After the game transformation, a variable $x$ is defined at program point $\mu$, and all other variables $x_k$ are defined by $\text{let } x_k = x \text{ in}$. The variable $x$ is a variable $x_k$ itself when $x_k$ has no array accesses and the current replication indices at the definition of $x_k$ are the same as at $\mu$. Otherwise, the variable $x$ is a fresh variable.

All variables $x_1, \dots, x_n$ must have the same type. They must not be defined syntactically above the program point $\mu$. The definitions of the variables $x_1, \dots, x_n$ must be in distinct branches of if, find, let, so that they cannot be simultaneously defined. Either all variables $x_1, \dots, x_n$ must be defined by random number generations or all of them must be defined by assignments.

* If $x_1, \dots, x_n$ are defined by random number generations, this transformation performs eager sampling of $x_i$. The random number generation of $x_1, \dots, x_n$ must be executed at most once for each execution of program point $\mu$. This is proved by combining that the definitions of the variables $x_1, \dots, x_n$ are in distinct branches of if, find, let with the fact that each of these definitions (at $\mu_j$) is executed at most once for each value of the current replication indices at $\mu$. To show the latter fact, we notice that, since $\mu_j$ is syntactically under $\mu$, the current replication indices at $\mu$ are a prefix of the replication indices at $\mu_j$. If the replication indices at $\mu_j$ are the same as at $\mu$, then the fact is proved. Otherwise, the replication indices at $\mu_j$ are $\tilde{i}, \tilde{i}_j$ while the replication indices at $\mu$ are $\tilde{i}$ and we show that $\mathcal{F}_{\mu_j} \cup \mathcal{F}_{\mu_j} \{\tilde{i}'/\tilde{i}_j\} \cup \{\tilde{i}_j \neq \tilde{i}'\}$ yields a contradiction, where $\tilde{i}'$ are fresh replication indices.

* If $x_1, \dots, x_n$ are defined by assignments of terms $M_j$, then all $M_j$ must consist of variables, function applications, and tests; there must be one $M_j$ defined at program point $\mu$, using all defined variables collected in $\mathcal{F}_{\mu}$ (let $M_{j_0}$ be that $M_j$, which will be used as the definition of $x$: let $x = M_{j_0}$ in); and all terms $M_j$ must be equal: for all $j \neq j_0$, $M_j = M_{j_0}$ knowing the facts $\mathcal{F}_{\mu_j}$ that hold at the program point $\mu_j$ of $M_j$.

The defined conditions of find above $\mu$ are updated to syntactically guarantee the definition of $M_{j_0}$, as required by Invariant 2.

**Lemma 51** *The transformation *move up* requires and preserves Properties 1, 2, 3, and 4. It preserves Property 5. If transformation *move up* transforms $G$ into $G'$, then $D, D_{SNU} : G, D, \text{EvUsed} \xrightarrow{V} p G', D, \text{EvUsed}$, where $p$ is an upper bound of the probability of collisions eliminated*
### 5.1.12 insert_event [27]

The transformation **insert_event** *e* μ inserts **event_abort** *e* at program point μ. (The program point μ is designated as explained in Section 5.1.10.)

The transformation **insert_event** *e* μ also adds to query **event**(e) ⇒ false in order to bound the probability of event *e*.

**Lemma 53** *The transformation insert_event requires and preserves Properties 1, 2, 3, and 4. It preserves Property 5 if the event is inserted at the process level. If transformation insert_event e μ transforms G into G', then D, D<sub>SNU</sub> : G, D, EvUsed V→<sub>0</sub> G', D ∨ e, EvUsed ∪ {e}.*

### 5.1.13 insert [27]

The transformation **insert** μ *ins* adds instruction *ins* at the program point μ. The program point μ is designated as explained in Section 5.1.10. The instruction *ins* can for instance be a test, in which case all branches of the test will be copies of the code that follows program point μ (so that the semantics of the game is unchanged). It can also be an assignment or a random generation of a fresh variable or an **event_abort** instruction. In all cases, CryptoVerif checks that this instruction preserves the semantics of the game except when we execute an inserted Shoup event, and rejects it with an error message if it does not.

After this transformation, **insert** calls **auto_SArename** to guarantee Property 4.

When the user inserts **event_abort** *e*, the transformation **insert** adds a query **event**(e) ⇒ false in order to bound the probability of event *e*.

When the user inserts a **find[unique<sub>e</sub>]** (the user actually types **find[unique]** but CryptoVerif automatically generates a fresh event *e* and inserts **find[unique<sub>e</sub>]** instead, since uniqueness is not proved yet), the transformation **insert** adds a query **event**(e) ⇒ false and calls **prove_unique** (Section 5.1.4) in order to try proving uniqueness.

**Lemma 54** *The transformation insert requires and preserves Properties 1, 2, 3, 4, and 5. If transformation insert transforms G into G', then D, D<sub>SNU</sub> : G, D, EvUsed V→<sub>p</sub> G', D ∨ e<sub>1</sub> ∨ ... ∨ e<sub>m</sub>, EvUsed ∪ {e<sub>1</sub>, ..., e<sub>m</sub>} where e<sub>1</sub>, ..., e<sub>m</sub> are the events in the inserted instruction (**event_abort** e<sub>j</sub>, **find[unique<sub>e</sub>j]**)) and the probability p comes from **prove_unique**.*

### 5.1.14 replace

The transformation **replace** μ *M* replaces the term *M*<sub>0</sub> at program point μ with the term *M*. (*M*<sub>0</sub> and *M* must be simple. The program point μ is designated as explained in Section 5.1.10.) Before performing the replacement, it checks that *M* is equal to *M*<sub>0</sub> at that program point (up to a small probability): first, it collects all facts *F*<sub>μ</sub> that hold at program point μ; second, it tests equality between *M*<sub>0</sub> and *M* using *F*<sub>μ</sub> and built-in equations (it uses equalities inferred from *F*<sub>μ</sub> to replace variables with their values, trying to make the terms equal); third, it simplifies *M*<sub>0</sub> and *M* using user-defined rewrite rules of Section 3.1, and tests equality between the results using *F*<sub>μ</sub> and built-in equations; fourth, it rewrites *M*<sub>0</sub> and *M* at most **maxReplaceDepth** times using equalities inferred from *F*<sub>μ</sub> and user-defined rewrite rules of Section 3.1, until it finds a common term modulo the built-in equations. The transformation is performed as soon as the equality between *M*<sub>0</sub> and *M* is proved.

The **defined** conditions of **find** above the program point μ are updated to make sure that **Invariant 2** is preserved. This is needed in particular when *M* makes array accesses that *M*<sub>0</sub> does not make.
### 5.1.16 merge arrays [27]

The transformation **merge arrays** $x_{11} ... x_{1n}, ..., x_{m1} ... x_{mn}$ merges the variables $x_{j1}, ..., x_{jn}$ into a single variable $x_{j1}$ for each $j \le m$. Each variable $x_{jk}$ must have a single definition. For each $j \le n$, the variables $x_{j1}, ..., x_{jn}$ must have the same type and indices of the same type. They must not be defined for the same value of their indices (that is, $x_{jk}$ and $x_{jk'}$ must be defined in different branches of if or find when $k \neq k'$). The arrays $x_{j1}, ..., x_{jn}$ are merged into a single array $x_{j1}$ for each $j \le m$. The transformation proceeds as follows:

* If, for each $k \le n$, $x_{1k}$ is defined above $x_{jk}$ for all $1 < j < m$, we introduce a fresh variable $b_k$ defined by $b_k \leftarrow$ mark just after the definition of $x_{1k}$. We call $b_k$ a branch variable; it is used to detect that $x_{jk}$ has been defined: $x_{jk}[\tilde{M}]$ is defined before the transformation if and only if $x_{j1}[\tilde{M}]$ and $b_k[\tilde{M}]$ are defined after the transformation, and $x_{j1}[\tilde{M}]$ after the transformation is equal to $x_{jk}[\tilde{M}]$ before the transformation.

* For each find that requires that some variables $x_{jk}$ are defined, we leave the branches that do not require the definition of $x_{jk}$ unchanged and we try to transform the other branches $FB_l = (\tilde{u}_l = \tilde{i}_l \le \tilde{n}_l \text{ suchthat } \text{defined}(\tilde{M}_l) \land M_l \text{ then } P_l)$ as follows.

1. We require that, for each $l$, there exists a distinct $k$ such that the defined condition of $FB_l$ refers to $x_{jk}$ for some $j$ but not to $x_{jk'}$ for any other $k'$. (Otherwise, the transformation fails.) We denote by $l(k)$ the value of $l$ that corresponds to $k$.

2. We choose a "target" branch $FB_T = (\tilde{u} = \tilde{i} \le \tilde{n} \text{ suchthat } \text{defined}(\tilde{M}) \land M \text{ then } P)$: if the defined condition of some branch $FB_l$ refers to $x_{j1}$ for some $j$, we choose that branch $FB_l$. Otherwise, we choose any branch $FB_l$ and rename its variables $x_{jk}$ to $x_{j1}$. We require that the references $x_{j1}[\tilde{M}]$ to the variables $x_{j1}$ in the defined condition of the target branch all have the same indices $\tilde{M}$. If the transformation succeeds, we will replace all branches $FB_l$ with the target branch.

3. The branch $FB_T$ after transformation is equivalent to branches $\bigoplus_{k=1}^n FB_T\{x_{jk}/x_{j1}, j=1, \dots, m\}$ before transformation. We show that these branches are equivalent to the branches $FB_l$.

For each $k \le n$,

- if $l(k)$ exists, then we show that $FB_T\{x_{jk}/x_{j1}, j = 1, \dots, m\}$ is equivalent to $FB_{l(k)}$. Let $l = l(k)$. We first rename the variables $\tilde{u}_l$ of $FB_l$ to the variables $\tilde{u}$ of the target branch. For simplicity, we still denote by $FB_l = (\tilde{u}_l = \tilde{i}_l \le \tilde{n}_l \text{ suchthat } \text{defined}(\tilde{M}_l) \land M_l \text{ then } P_l)$ the obtained branch. Then we show that, if the variables of $\tilde{M}_l$ are defined, then the variables of $\tilde{M}\{x_{jk}/x_{j1}, j = 1, \dots, m\}$ are defined, and conversely; $M_l = M\{x_{jk}/x_{j1}, j = 1, \dots, m\}$ (knowing the equalities that hold at that program point), and $P_l$ and $P\{x_{jk}/x_{j1}, j = 1, \dots, m\}$ execute the same code up to renaming of variables defined in $P_l$ or $P\{x_{jk}/x_{j1}, j = 1, \dots, m\}$ and that do not have array accesses, and up to equality of terms proved using facts $F_\mu$ that hold at the program point $\mu$ of the considered find.

- if $l(k)$ does not exist, then we show that $FB_T\{x_{jk}/x_{j1}, j = 1, \dots, m\}$ can in fact not be executed, because its condition cannot hold: the variables of $\tilde{M}\{x_{jk}/x_{j1}, j = 1, \dots, m\}$ cannot be simultaneously defined or $M\{x_{jk}/x_{j1}, j = 1, \dots, m\}$ cannot hold.

If the transformation above fails and we have introduced branch variables, we replace each condition defined($x_{jk}[\tilde{M}]$) with defined($x_{j1}[\tilde{M}], b_k[\tilde{M}$]).
If the transformation above fails and we have not introduced branch variables, the whole **merge arrays** transformation fails.

* The definition of $x_{jk}$ is renamed to $x_{j1}$ and each reference to $x_{jk}[\tilde{M}]$ is renamed to $x_{j1}[\tilde{M}]$.

**Lemma 57** The transformation **merge arrays** requires and preserves Properties 1, 2, 3, 4, and 5. If transformation **merge arrays** transforms $G$ into $G_{RU}$, by replacing all proved find[unique] with find. Lemma 58 shows the soundness of this preliminary transformation. It may be advantageous for (one-session) secrecy proofs because the removed find[unique] do not need to be proved, while the remaining ones must be reproved after the transformation, as we show below.

### 5.1.17 guess i

When guess**RemoveUnique** = true and some (one-session) secrecy queries are present, the transformation guess i first transforms the game $G$ into $G_{RU}$, by replacing all proved find[unique] with find. Lemma 58 shows the soundness of this preliminary transformation. It may be advantageous for (one-session) secrecy proofs because the removed find[unique] do not need to be proved, while the remaining ones must be reproved after the transformation, as we show below.

**Lemma 58** Let $G_{RU}$ be the game obtained from $G$ by replacing all proved find[unique] with find. Let sp be a security property (sp is 1-ses.secr.(x), Secrecy(x), bit secr.(x), or a correspondence $\varphi$, which does not use $\mathcal{S}$, $\bar{\mathcal{S}}$, nor non-unique events). Let D be a disjunction of Shoup events and a subset of non-unique events $e_i$ corresponding to unproved find[unique$_{e_i}$] in $G$ (D does not contain $\mathcal{S}$ nor $\bar{\mathcal{S}}$). If Bound$_{G_{RU}}(V, sp, D, p)$, then Bound$_G(V, sp, D, p)$.

**Proof** Let $C'$ be an evaluation context acceptable for $C_{sp}[G]$ with public variables $V \setminus V_{sp}$ that does not contain events used by sp or D nor non-unique events in G and A be an attacker in BB. Let $C = C'[C_{sp}[]]$. The context $C'$ is also acceptable for $C_{sp}[G_{RU}]$ with public variables $V \setminus V_{sp}$, and a fortiori does not contain non-unique events in $G_{RU}$. Since Bound$_{G_{RU}}(V, sp, D, p)$, we have $\text{Adv}_{G_{RU}}(A, C, sp, D) \le p(A, C)$.

First case: sp is a correspondence $\varphi$. We have

$$ \begin{aligned} \text{Adv}_G(A, C, sp, D) &= \text{Pr}^A[C[G] : (\neg\varphi \lor D) \land \neg\text{NonUnique}_{G,D}] \\ &\le \text{Pr}^A[C[G_{RU}] : (\neg\varphi \lor D) \land \neg\text{NonUnique}_{G_{RU},D}] = \text{Adv}_{G_{RU}}(A, C, sp, D) \end{aligned} $$

because traces of G that satisfy $(\neg\varphi \lor D) \land \neg\text{NonUnique}_{G,D}$ correspond to similar traces of $G_{RU}$ that satisfy $(\neg\varphi \lor D) \land \neg\text{NonUnique}_{G_{RU},D}$. Only traces that satisfy e for some proved find[unique$_e$] in G are mapped to different traces in $G_{RU}$. These traces satisfy $\text{NonUnique}_{G,D}$.

Second case: sp is 1-ses.secr.(x), Secrecy(x), or bit secr.(x). We have

$$ \text{Pr}^A[C[G] : \mathcal{S} \lor D] \le \text{Pr}^A[C[G_{RU}] : \mathcal{S} \lor D] $$

since the traces of $C[G]$ that execute an event in $\mathcal{S} \lor D$ correspond to similar traces of $C[G_{RU}]$ that also execute an event in $\mathcal{S} \lor D$ ($\mathcal{S} \lor D$ does not contain any proved non-unique event of G), and

$$ \text{Pr}^A[C[G_{RU}] : \bar{\mathcal{S}} \lor \text{NonUnique}_{G_{RU},D}] \le \text{Pr}^A[C[G] : \bar{\mathcal{S}} \lor \text{NonUnique}_{G,D}] $$

since the traces of $C[G_{RU}]$ that execute $\bar{\mathcal{S}}$ or an event in $\text{NonUnique}_{G_{RU},D}$ correspond to either to similar traces of $C[G]$ that execute the same event or to traces that execute a proved non-unique
event in $C[G]$, so an event in $\text{NonUnique}_{G,D}$. Therefore,

$$ \begin{aligned} \text{Adv}_G(\mathcal{A}, C, sp, D) &= \Pr^A[C[G] : S \lor D] - \Pr^A[C[G] : \bar{S} \lor \text{NonUnique}_{G,D}] \\ &\leq \Pr^A[C[G_{RU}] : S \lor D] - \Pr^A[C[G_{RU}] : \bar{S} \lor \text{NonUnique}_{G_{RU},D}] \\ &\leq \text{Adv}_{G_{RU}}(\mathcal{A}, C, sp, D). \end{aligned} $$

In both cases, we obtain $\text{Adv}_G(\mathcal{A}, C, sp, D) \leq p(\mathcal{A}, C)$ and $\text{Bound}_G(V, sp, D, p)$. $\square$

<figure><img src="image_15.png" /></figure>

Next, the main guessing transformation is performed. The transformation **guess** $i$ consists in guessing the tested session of a principal in a protocol, which is a step frequently done in cryptographic proofs. In CryptoVerif, we consider a game $G$ and define a transformed game $G'$ by guessing a replication index $i$: we replace **foreach** $i \leq n$ do $Q$ with **foreach** $i \leq n$ do $Q'$ where $Q'$ is obtained from $Q$ by replacing the processes $P$ under the first inputs with if $i = i_{\text{tested}}$ then $P'$ else $P''$ and $i_{\text{tested}}$ is a constant. The constant $i_{\text{tested}}$ is the index of the tested session. We distinguish the process executed in the tested session, $P'$, on which we are going to prove security properties, from the process $P''$ for other sessions which are executed, but for which we do not prove security properties. (In case **diff\_constants** = true, the constant $i_{\text{tested}}$ must not be considered different from other constants of the same type.) The process $P'$ is obtained from $P$ by

* duplicating all events: event $e(\tilde{M})$ is replaced with event $e(\tilde{M})$; event $e'(\tilde{M})$ and similarly event_abort $e$ is replaced with event $e$; event_abort $e'$. We require that in the game $G$, the same event $e$ cannot occur both under the modified replication **foreach** $i \leq n$ do $Q$ and elsewhere in the game. (Otherwise, queries that use $e$ are left unchanged.)

* duplicating definitions of every variable $x$ used in queries for secrecy and one-session secrecy: let $x' = x$ in is added after each definition of $x$. We require that in the game $G$, the same variable $x$ used in queries for secrecy or one-session secrecy cannot be defined both under the modified replication **foreach** $i \leq n$ do $Q$ and elsewhere in the game. (Otherwise, the considered query is left unchanged.)

The process $P''$ is obtained from $P$ by duplicating definitions of every variable $x$ used in queries for secrecy (not one-session secrecy): let $x'' = x$ in is added after each definition of $x$.

We replace variables $x$ in secrecy and one-session secrecy queries with their duplicated version $x'$. For secrecy queries, the duplicated version $x''$ is added to public variables. In both cases, we prove (one-session) secrecy for the variable $x'$ defined in the tested session. In case of one-session secrecy, that is enough: it shows that $x'$ is indistinguishable from a random value, and that proves one-session secrecy of $x$ for all sessions by symmetry. However, for secrecy, we additionally want to show that the values of $x$ in the various sessions are independent of each other; this is achieved by considering the value of $x$ in sessions other than the tested session (that is, $x''$) as public: if $x'$ is indistinguishable from random even when $x''$ is public, then $x'$ is independent of $x''$.

In non-injective correspondence queries, we replace one non-injective event $e$ before the arrow $\Rightarrow$ with its duplicated version $e'$. Hence, we prove the query for the tested session, which uses event $e'$. The proof is valid for all sessions by symmetry.

The probability of attack must basically be multiplied by $n$ for all modified queries. The proof depends on the considered query and is detailed below.

For queries that are left unchanged, i.e. secrecy and one-session secrecy queries for variables not defined under the modified replication, non-injective correspondence queries with no event before the arrow $\Rightarrow$ under the modified replication (the previous queries prove properties about other roles than the one for which we guess the tested session), bit secrecy queries (because
the secret is defined under no replication, so it is not under the guessed replication), as well as
injective correspondence queries (see details below), the probability is unchanged. It is clear that
these queries are not affected by the transformation.

After this transformation, **guess** calls **auto_SArename** to guarantee Property 4.

**Lemma 59** The transformation guess $i$ requires and preserves Properties 1, 2, 3, and 4. It preserves Property 5.

Suppose the game $G$ is transformed into $G'$ by the transformation **guess** $i$, where $i$ is a
replication index bounded by $n$. Below, we consider only the modified queries.

Let $\varphi$ and $\varphi'$ be respectively the semantics of a non-injective correspondence and its transformed correspondence. If $\text{Bound}_{G'}(V, \varphi', D_{\text{false}}, p)$ and $p$ is independent of the value of $i_{\text{tested}}$, then $\text{Bound}_G(V, \varphi, D_{\text{false}}, np)$.

If $G'$ satisfies the one-session secrecy of $x'$ with public variables $V$ ($x, x', x'' \notin V$) up to probability $p$ and $p$ is independent of the value of $i_{\text{tested}}$, then $G$ satisfies the one-session secrecy of $x$ with public variables $V$ up to probability $np$.

If $G'$ satisfies the secrecy of $x'$ with public variables $V \cup \{x''\}$ ($x, x', x'' \notin V$) up to probability $p$ and $p$ satisfies Property 6, then $G$ satisfies the secrecy of $x$ with public variables $V$ up to probability $n \times p$ (neglecting a small additional runtime of the context).

If $\text{Bound}_{G'}(V \cup \{x'\}, 1\text{-ses.secr}(x'), \text{NonUnique}_{G'}, p)$ and $p$ satisfies Property 6, then we have $\text{Bound}_G(V \cup \{x\}, 1\text{-ses.secr}(x), D_{\text{false}}, np)$.

If $\text{Bound}_{G'}(V \cup \{x', x''\}, \text{Secrecy}(x'), \text{NonUnique}_{G'}, p)$ and $p$ satisfies Property 6, then we have $\text{Bound}_G(V \cup \{x\}, \text{Secrecy}(x), D_{\text{false}}, np)$ (neglecting a small additional runtime of the context).

Property 6 guarantees that $p$ is independent of the value of $i_{\text{tested}}$, as well as other independence conditions needed for secrecy and for the properties on **Bound** because we modify the context in the proof. Since the third argument of **Bound** is always $D_{\text{false}}$ in the conclusion of Lemma 59, we cannot use the optimization of considering the disjunction of several properties simultaneously, as outlined in Section 2.8.4: we must consider each property and event separately. Indeed, if we applied guessing to several properties at once, we might need to guess the tested session for each property, which would introduce several factors $n$. Since the third argument of **Bound** is $\text{NonUnique}_{G'}$ in the hypothesis of Lemma 59 for (one-session) secrecy properties, uniqueness of $\text{find}[\text{unique}_e]$ must be reproved in game $G'$ after the guess transformation (that is, the probability that these $\text{find}[\text{unique}_e]$ have several successful choices must be bounded again in $G'$).

Proof

**Non-injective correspondences** We suppose that the events under the transformed replica-
tion contain as argument the replication index $i$ of that replication. (CryptoVerif implicitly adds
the current program point and replication indices to each event, and uses fresh distinct variables
for the added replication indices in the queries. That does not change the meaning of the query.)

Let $\forall i_0 : [1, n], \tilde{x} : \tilde{T}; \text{event}(e(\tilde{M})) \land \psi \Rightarrow \exists \tilde{y} : \tilde{T}'; \phi$ be the initial query and $\forall i_0 : [1, n], \tilde{x} : \tilde{T}; \text{event}(e'(\tilde{M})) \land \psi \Rightarrow \exists \tilde{y} : \tilde{T}'; \phi$ be the transformed query, where $\{i_0, \tilde{x}\} = \text{var}(\text{event}(e'(\tilde{M})) \land \psi)$, $\tilde{y} = \text{var}(\phi) \setminus \text{var}(\text{event}(e'(\tilde{M})) \land \psi)$, and $i_0$ be the variable for the index of the transformed replication in $\tilde{M}$.

Let $C$ be an evaluation context acceptable for $G$ with public variables $V$ that does not contain
events used by $\varphi$ and $\mathcal{A}$ be an attacker in $\mathcal{B}\mathcal{B}$.

$$
\begin{align*}
\mathrm{Adv}_G(\mathcal{A}, C, \varphi, D_{\mathrm{false}}) &= \mathrm{Pr}^A[C[G] : \neg\varphi \wedge \neg\mathrm{NonUnique}_G] \\
&= \mathrm{Pr}^A \left[ C[G] : (\exists i_0 \in [1, n], \exists \tilde{x} \in \tilde{T}, \mathrm{event}(e(\tilde{M})) \wedge \psi \wedge \neg\exists \tilde{y} \in \tilde{T}', \phi) \wedge \neg\mathrm{NonUnique}_G \right] \\
&= \sum_{i_{\mathrm{val}}=1}^n \mathrm{Pr}^A \left[ C[G] : (\exists i_0 \in [1, n], \exists \tilde{x} \in \tilde{T}, i_0 = i_{\mathrm{val}} \wedge \mathrm{event}(e(\tilde{M})) \wedge \psi \wedge \neg\exists \tilde{y} \in \tilde{T}', \phi) \wedge \neg\mathrm{NonUnique}_G \right] \\
&= \sum_{i_{\mathrm{val}}=1}^n \mathrm{Pr}^A \left[ C[G'] : (\exists i_0 \in [1, n], \exists \tilde{x} \in \tilde{T}, \mathrm{event}(e'(\tilde{M})) \wedge \psi \wedge \neg\exists \tilde{y} \in \tilde{T}', \phi) \wedge \neg\mathrm{NonUnique}_G' \right] \quad \text{for } i_{\mathrm{tested}} = i_{\mathrm{val}} \\
&= \sum_{i_{\mathrm{val}}=1}^n \mathrm{Adv}_{G'}(\mathcal{A}, C, \varphi', D_{\mathrm{false}}) \quad \text{for } i_{\mathrm{tested}} = i_{\mathrm{val}}
\end{align*}
$$

Since $\mathrm{Bound}_{G'}(V, \varphi', D_{\mathrm{false}}, p)$, we have $\mathrm{Adv}_{G'}(\mathcal{A}, C, \varphi', D_{\mathrm{false}}) \le p(\mathcal{A}, C)$ and the probability $p$ is independent of the value of $i_{\mathrm{tested}}$, so we obtain $\mathrm{Adv}_G(\mathcal{A}, C, \varphi, D_{\mathrm{false}}) \le n \times p(\mathcal{A}, C)$. Therefore $\mathrm{Bound}_G(V, \varphi, D_{\mathrm{false}}, np)$.

**One-session secrecy** Let $C$ be an evaluation context acceptable for $C_{1-\mathrm{ses.secr.}(x)}[G]$ with public variables $V$ that does not contain $\mathcal{S}$ nor $\bar{\mathcal{S}}$ and $\mathcal{A}$ be an attacker in $\mathcal{B}\mathcal{B}$. Suppose that the modified replication corresponds to the $j$-th index of variable $x$. We have

$$
\begin{align*}
\mathrm{Adv}_G^{1-\mathrm{ses.secr.}(x)}(\mathcal{A}, C) &= \mathrm{Pr}^A[C[C_{1-\mathrm{ses.secr.}(x)}[G]] : \mathcal{S}] - \mathrm{Pr}^A[C[C_{1-\mathrm{ses.secr.}(x)}[G]] : \bar{\mathcal{S}}] \\
&= \sum_{v=1}^{n} \mathrm{Pr}^A[C[C_{1-\mathrm{ses.secr.}(x)}[G]] : \mathcal{S} \wedge u_j = v] \\
&\quad - \mathrm{Pr}^A[C[C_{1-\mathrm{ses.secr.}(x)}[G]] : \bar{\mathcal{S}} \wedge u_j = v] \\
&= \sum_{v=1}^{n} \mathrm{Pr}^A[C[C_{1-\mathrm{ses.secr.}(x')}[G')] : \mathcal{S} \wedge u_j = v] \\
&\quad - \mathrm{Pr}^A[C[C_{1-\mathrm{ses.secr.}(x')}[G')] : \bar{\mathcal{S}} \wedge u_j = v] \quad \text{for } i_{\mathrm{tested}} = v
\end{align*}
$$

because in $G'$ with $i_{\mathrm{tested}} = v$, $x'[u_1, \dots, u_m] = x[u_1, \dots, u_m]$ when $u_j = v$, so $C_{1-\mathrm{ses.secr.}(x)}[G]$ behaves like $C_{1-\mathrm{ses.secr.}(x')}[G']$ (the events added in $G'$ are not used).

Moreover, $\mathrm{Pr}^A[C[C_{1-\mathrm{ses.secr.}(x')}[G')] : \mathcal{S} \wedge (u_j \text{ not defined} \lor u_j \neq v)] = \mathrm{Pr}^A[C[C_{1-\mathrm{ses.secr.}(x')}[G')] : \bar{\mathcal{S}} \wedge (u_j \text{ not defined} \lor u_j \neq v)]$ when $i_{\mathrm{tested}} = v$. Indeed, when $u_j$ is not defined or $u_j \neq v = i_{\mathrm{tested}}$, the query on $O_s$ either is not executed or always yields, independently of the value of $b$. Hence, changing the value of $b$ just swaps the events $\mathcal{S}$ and $\bar{\mathcal{S}}$. So

$$
\begin{align*}
\mathrm{Pr}^A[C[C_{1-\mathrm{ses.secr.}(x')}[G')] : \mathcal{S} \wedge (u_j \text{ not defined} \lor u_j \neq v) \wedge b = \text{true}] &= \\
\mathrm{Pr}^A[C[C_{1-\mathrm{ses.secr.}(x')}[G')] : \bar{\mathcal{S}} \wedge (u_j \text{ not defined} \lor u_j \neq v) \wedge b = \text{false}] \\
\mathrm{Pr}^A[C[C_{1-\mathrm{ses.secr.}(x')}[G')] : \bar{\mathcal{S}} \wedge (u_j \text{ not defined} \lor u_j \neq v) \wedge b = \text{true}] &= \\
\mathrm{Pr}^A[C[C_{1-\mathrm{ses.secr.}(x')}[G')] : \mathcal{S} \wedge (u_j \text{ not defined} \lor u_j \neq v) \wedge b = \text{false}].
\end{align*}
$$

We obtain the announced result by swapping the two sides of the second equality and adding the first equality to it. (The variable $b$ is always defined when $\mathcal{S}$ or $\bar{\mathcal{S}}$ is executed.)
Therefore,

$$
\begin{align*}
\mathbf{Adv}_G^{1\text{-ses.secr.}(x)}(\mathcal{A}, C) &= \sum_{v=1}^{n} \Pr^{\mathcal{A}}[C[C_{1\text{-ses.secr.}(x')}][G'] : \mathcal{S}] - \Pr^{\mathcal{A}}[C[C_{1\text{-ses.secr.}(x')}][G'] : \bar{\mathcal{S}}] \\
&\quad \text{for } i_{\text{tested}} = v \\
&= \sum_{v=1}^{n} \mathbf{Adv}_{G'}^{1\text{-ses.secr.}(x')}(\mathcal{A}, C) \text{ for } i_{\text{tested}} = v
\end{align*}
$$

Since $G'$ satisfies the one-session secrecy of $x'$ with public variables $V$ up to probability $p$, we
have $\mathbf{Adv}_{G'}^{1\text{-ses.secr.}(x')}(\mathcal{A}, C) \le p(\mathcal{A}, C)$ and the probability $p$ is independent of the value of $i_{\text{tested}}$,
so we obtain $\mathbf{Adv}_{G}^{1\text{-ses.secr.}(x)}(\mathcal{A}, C) \le n \times p(\mathcal{A}, C)$. Therefore, $G$ satisfies the one-session secrecy
of $x$ with public variables $V$ up to probability $np$.

**Secrecy** Let $C$ be an evaluation context acceptable for $C_{\text{Secrecy}(x)}[G]$ with public variables $V$
that does not contain $S$ nor $\bar{S}$ and $\mathcal{A}$ be an attacker in $\mathcal{BB}$. Suppose that the modified replication
corresponds to the $j$-th index of variable $x$. We have

$$
\mathbf{Adv}_G^{\text{Secrecy}(x)}(\mathcal{A}, C) = \frac{1}{2} \left( \begin{array}{@{}l@{}}
\Pr^{\mathcal{A}}[C[G \mid Q_{\text{Secrecy}(x)}] : \mathcal{S} \mid b = \text{true}] + \Pr^{\mathcal{A}}[C[G \mid Q_{\text{Secrecy}(x)}] : \mathcal{S} \mid b = \text{false}] \\
- \Pr^{\mathcal{A}}[C[G \mid Q_{\text{Secrecy}(x)}] : \bar{\mathcal{S}} \mid b = \text{true}] - \Pr^{\mathcal{A}}[C[G \mid Q_{\text{Secrecy}(x)}] : \bar{\mathcal{S}} \mid b = \text{false}]
\end{array} \right)
$$

Let

$$
\begin{align*}
Q_{\text{Secrecy}(x),\text{real}} &= O_{s0}(\O) := \text{return } \O; \\
(\text{foreach } i_s \le n_s \text{ do } O_s[i_s](u_1: [1, n_1], \dots, u_m: [1, n_m]) := & \\
& \quad \text{if defined}(x[u_1, \dots, u_m]) \text{ then} \\
& \quad \text{return } (x[u_1, \dots, u_m]) \\
& \quad | O'_s(b' : \text{bool}) := \text{if } b' \text{ then } \text{event_abort } S \text{ else } \text{event_abort } \bar{S}) \\
Q_{\text{Secrecy}(x),\text{random}} &= O_{s0}(\O) := \text{return } \O; \\
(\text{foreach } i_s \le n_s \text{ do } O_s[i_s](u_1: [1, n_1], \dots, u_m: [1, n_m]) := & \\
& \quad \text{if defined}(x[u_1, \dots, u_m]) \text{ then} \\
& \quad \text{find } u'_s = i'_s \le n_s \text{ suchthat } \text{defined}(y[i'_s], u_1[i'_s], \dots, u_m[i'_s]) \land & \\
& \quad u_1[i'_s] = u_1 \land \dots \land u_m[i'_s] = u_m \\
& \quad \text{then return } (y[u'_s]) \\
& \quad \text{else } y \leftarrow T; \text{ return } \O \\
& \quad | O'_S(b' : \text{bool}) := \text{if } b' \text{ then } \text{event_abort } S \text{ else } \text{event_abort } \bar{S})
\end{align*}
$$

Then

$$
\mathbf{Adv}_G^{\text{Secrecy}(x)}(\mathcal{A}, C) = \frac{1}{2} \left( \begin{array}{@{}l@{}}
\Pr^{\mathcal{A}}[C[G \mid Q_{\text{Secrecy}(x),\text{real}}] : \mathcal{S}] + \Pr^{\mathcal{A}}[C[G \mid Q_{\text{Secrecy}(x),\text{random}}] : \bar{\mathcal{S}}] \\
- \Pr^{\mathcal{A}}[C[G \mid Q_{\text{Secrecy}(x),\text{real}}] : \bar{\mathcal{S}}] - \Pr^{\mathcal{A}}[C[G \mid Q_{\text{Secrecy}(x),\text{random}}] : \mathcal{S}]
\end{array} \right)
$$
Let

$$
\begin{align*}
Q_{\text{Secrecy}(x),v} &= O_{s0}() := \text{return } (); \\
\text{(foreach } i_s \le n_s \text{ do } O_s[i_s](u_1: [1, n_1], \dots, u_m: [1, n_m]) := & \\
& \quad \text{if defined}(x[u_1, \dots, u_m]) \text{ then} \\
& \quad \text{if } u_j \le v \text{ then return } (x[u_1, \dots, u_m]) \text{ else} \\
& \quad \text{find } u'_s = i'_s \le n_s \text{ such that defined}(y[i'_s], u_1[i'_s], \dots, u_m[i'_s]) \land \\
& \quad \qquad u_1[i'_s] = u_1 \land \dots \land u_m[i'_s] = u_m \\
& \quad \text{then return } (y[u'_s]) \\
& \quad \text{else } y \stackrel{R}{\leftarrow} T; \text{ return } (y) \\
& \quad | O'_s(b': \text{bool}) := \text{if } b' \text{ then event_abort S else event_abort } \bar{S})
\end{align*}
$$

The process $Q_{\text{Secrecy}(x),0}$ behaves like $Q_{\text{Secrecy}(x),\text{random}}$ and $Q_{\text{Secrecy}(x),n}$ behaves like $Q_{\text{Secrecy}(x),\text{real}}$ ($n_j = n$). Therefore,

$$
\begin{align*}
\text{Adv}_G^{\text{Secrecy}(x)}(\mathcal{A}, C) &= \frac{1}{2} \left( \begin{array}{@{}l@{}}
    (\text{Pr}^A[C[G \mid Q_{\text{Secrecy}(x),n}] : \mathcal{S}] - \text{Pr}^A[C[G \mid Q_{\text{Secrecy}(x),0}] : \mathcal{S}]) \\
    - (\text{Pr}^A[C[G \mid Q_{\text{Secrecy}(x),n}] : \bar{\mathcal{S}}] - \text{Pr}^A[C[G \mid Q_{\text{Secrecy}(x),0}] : \bar{\mathcal{S}]})
  \end{array} \right) \\
&= \frac{1}{2} \left( \begin{array}{@{}l@{}}
    \sum_{v=1}^n (\text{Pr}^A[C[G \mid Q_{\text{Secrecy}(x),v}] : \mathcal{S}] - \text{Pr}^A[C[G \mid Q_{\text{Secrecy}(x),v-1}] : \mathcal{S}]) \\
    - \sum_{v=1}^n (\text{Pr}^A[C[G \mid Q_{\text{Secrecy}(x),v}] : \bar{\mathcal{S}}] - \text{Pr}^A[C[G \mid Q_{\text{Secrecy}(x),v-1}] : \bar{\mathcal{S}]})
  \end{array} \right)
\end{align*}
$$

We define a context $C'_v$ that returns a random value for $u_j > v$, the real value of $x$ obtained from the public variable $x''$ in $G'$ for $u_j < v$, and calls $Q_{\text{Secrecy}(x'),\text{real}}$ or $Q_{\text{Secrecy}(x'),\text{random}}$ for $u_j = v$.

$$
\begin{align*}
C'_v &= \text{newOracle } O_{s1}; ([\,] | \text{foreach } i_s \le n_s \text{ do } O_s[i_s](u_1: [1, n_1], \dots, u_m: [1, n_m]) := \\
&\quad \text{if } u_j = v \text{ then (let } z : T = O_{s1}[i_s](u_1, \dots, u_m) \text{ in return } (z) \text{) else} \\
&\quad \text{if defined}(x''[u_1, \dots, u_m]) \text{ then} \\
&\quad \text{if } u_j < v \text{ then return } (x''[u_1, \dots, u_m]) \text{ else} \\
&\quad \text{find } u'_s = i'_s \le n_s \text{ such that defined}(y[i'_s], u_1[i'_s], \dots, u_m[i'_s]) \land \\
&\quad \qquad u_1[i'_s] = u_1 \land \dots \land u_m[i'_s] = u_m \\
&\quad \text{then return } (y[u'_s]) \\
&\quad \text{else } y \stackrel{R}{\leftarrow} T; \text{ return } (y))
\end{align*}
$$

where the processes $Q_{\text{Secrecy}(x'),\text{real}}$ and $Q_{\text{Secrecy}(x'),\text{random}}$ use oracle $O_{s1}$ instead of $O_s$. When $u_j = v$, the query on $O_s[i_s]$ is forwarded to $Q_{\text{Secrecy}(x'),\text{real}}$ (resp. $Q_{\text{Secrecy}(x'),\text{random}}$) on oracle $O_{s1}[i_s]$. The values of $x$ for sessions other than $v$ are collected in $x''$ by $G'$; these are the values returned by the query on $O_s[i_s]$ when $u_j < v$. Finally, when $u_j > v$, the query on $O_s[i_s]$ is answered with a random value $y$.

Then

$$
\begin{align*}
\text{Pr}^A[C[G \mid Q_{\text{Secrecy}(x),v}] : \mathcal{S}] &= \text{Pr}^A[C[C'_v[G' \mid Q_{\text{Secrecy}(x'),\text{real}}]] : \mathcal{S}], \\
\text{Pr}^A[C[G \mid Q_{\text{Secrecy}(x),v}] : \bar{\mathcal{S}}] &= \text{Pr}^A[C[C'_v[G' \mid Q_{\text{Secrecy}(x'),\text{real}}]] : \bar{\mathcal{S}}], \\
\text{Pr}^A[C[G \mid Q_{\text{Secrecy}(x),v-1}] : \mathcal{S}] &= \text{Pr}^A[C[C'_v[G' \mid Q_{\text{Secrecy}(x'),\text{random}}]] : \mathcal{S}], \text{ and} \\
\text{Pr}^A[C[G \mid Q_{\text{Secrecy}(x),v-1}] : \bar{\mathcal{S}}] &= \text{Pr}^A[C[C'_v[G' \mid Q_{\text{Secrecy}(x'),\text{random}}]] : \bar{\mathcal{S}}],
\end{align*}
$$
for $i_{\text{tested}} = v$.

Then

$$ \begin{aligned} & \text{Adv}_G^{\text{Secrecy}(x)}(\mathcal{A}, C) \\ &= \sum_{v=1}^{n} \frac{1}{2} \left( \begin{array}{l} \Pr^A[C[C_v'(G'|Q_{\text{Secrecy}(x'),\text{real}}]) : \mathcal{S}] - \Pr^A[C[C_v'(G'|Q_{\text{Secrecy}(x'),\text{random}}]) : \mathcal{S}] \\ - \Pr^A[C[C_v'(G'|Q_{\text{Secrecy}(x'),\text{real}}]) : \bar{\mathcal{S}}] + \Pr^A[C[C_v'(G'|Q_{\text{Secrecy}(x'),\text{random}}]) : \bar{\mathcal{S}}] \end{array} \right) \\ & \text{for } i_{\text{tested}} = v \\ &= \sum_{v=1}^{n} \text{Adv}_{G'}^{\text{Secrecy}(x')}(\mathcal{A}, C[C_v']) \text{ for } i_{\text{tested}} = v \end{aligned} $$

by the link between the advantage for secrecy and $Q_{\text{Secrecy}(x'),\text{real}}$, $Q_{\text{Secrecy}(x'),\text{random}}$ shown above. Since $G'$ satisfies the secrecy of $x'$ with public variables $V \cup \{x''\}$ up to probability $p$ and $C[C_v']$ is an evaluation context acceptable for $G' | Q_{\text{Secrecy}(x')}$ with public variables $V \cup \{x''\}$ that does not contain $\mathcal{S}$ nor $\bar{\mathcal{S}}$, we have $\text{Adv}_{G'}^{\text{Secrecy}(x')}(\mathcal{A}, C[C_v']) \le p(\mathcal{A}, C[C_v'])$. Moreover, by Property 6, the probability $p(\mathcal{A}, C[C_v'])$ is independent of $i_{\text{tested}} = v$ (because the type of $i_{\text{tested}}$ is bounded) and depends only on the runtime of $C$, the number of calls $C$ makes to the various oracles (which determine replication bounds), and the length of bitstrings, so we have $p(\mathcal{A}, C[C_v']) = p(\mathcal{A}, C)$ (the runtime of $C_v'$ can be neglected). Hence, we obtain $\text{Adv}_G^{\text{Secrecy}(x)}(\mathcal{A}, C) \le n \times p(\mathcal{A}, C)$. Therefore, $G$ satisfies the secrecy of $x$ with public variables $V$ up to probability $n \times p$.

**One-session secrecy, secrecy, and bit secrecy** In this lemma, bit secrecy queries do not occur. However, we reuse this proof in Lemmas 60 and 61 where bit secrecy queries occur, so we also handle them here. Let sp be 1-ses.secr.(x), Secrecy(x), or bit secr.(x), and sp' be the same property with $x'$ instead of $x$. Let $V' = V$ when sp is 1-ses.secr.(x) or bit secr.(x), and $V' = V \cup \{x''\}$ when sp is Secrecy(x). Since Bound$_G$(V' $\cup$ $\{x'\}$, sp', NonUnique$_G$, p), then by Lemma 28, Property 1, $G'$ satisfies sp' with public variables $V'$ up to probability $p'$ such that $p'(\mathcal{A}, C) = p(\mathcal{A}, C[C_{sp'}])$. So by the previous result for (one-session or bit) secrecy, $G$ satisfies sp with public variables $V$ up to probability $np'$. Let $C$ be an evaluation context acceptable for $C_{sp}[G]$ with public variables $V$ that does not contain $\mathcal{S}$ nor $\bar{\mathcal{S}}$ and $\mathcal{A}$ be an attacker in BB. Hence

$$ \begin{aligned} & \text{Adv}_G(\mathcal{A}, C[C_{sp}[]], sp, D_{\text{false}}) \\ &= \Pr^A[C[C_{sp}[G]] : \mathcal{S}] - \Pr^A[C[C_{sp}[G]] : \bar{\mathcal{S}} \lor \text{NonUnique}_G] \\ &\le \Pr^A[C[C_{sp}[G]] : \mathcal{S}] - \Pr^A[C[C_{sp}[G]] : \bar{\mathcal{S}}] \\ &= \text{Adv}_G^{sp}(\mathcal{A}, C) \le n \times p'(\mathcal{A}, C) = n \times p(\mathcal{A}, C[C_{sp}[]]) \end{aligned} $$

Indeed, replacing $C_{sp'}$ with $C_{sp}$ in the argument of $p$ does not change its result, by Property 6. Therefore, we have Bound$_G(V \cup \{x\}$, sp, $D_{\text{false}}$, $np$). $\square$

In the guess transformation, we cannot modify injective correspondence queries, because two executions of some injective event $e$ with different indices $i$ could be mapped to the same events in the conclusion of the query. In general, it even does not work for non-injective events inside injective queries. As a counter-example, consider the query: $\forall i : [1, n], x : T'; \text{event}(e_1(i, x)) \land \text{inj-event}(e_2(x)) \Rightarrow \text{inj-event}(e_3())$ with events $e_1(i_1, x_1)$, $e_1(i_2, x_2)$, $e_2(x_1)$, $e_2(x_2)$ and $e_3$ each executed once. This query is false: we have two executions of $e_2$ (with matching executions of $e_1$) for a single execution of $e_3$. That contradicts injectivity. However, it is true if we restrict ourselves to one value of $i$ (the index of the tested session), because we consider $e_1(i_1, x_1)$, $e_2(x_1)$ and $e_3$ for $i = i_1$ and $e_1(i_2, x_2)$, $e_2(x_2)$ and $e_3$ for $i = i_2$. Requiring the same value of $x$ in $e_1$ and
$e_2$ restricts the events $e_2$ that we consider when we guess the session for $e_1$. Therefore, proving the query for the tested session does not allow us to prove it in the initial game.

Hence, for injective correspondence queries $\forall \tilde{x} : \tilde{T}; \psi \Rightarrow \exists \tilde{y} : \tilde{T}'; \phi$, we proceed as follows: we define a non-injective query noninj($\forall \tilde{x} : \tilde{T}; \psi \Rightarrow \exists \tilde{y} : \tilde{T}'; \phi$) simply obtained by replacing injective events with non-injective events, and we try to prove that noninj($\forall \tilde{x} : \tilde{T}; \psi \Rightarrow \exists \tilde{y} : \tilde{T}'; \phi$) implies $\forall \tilde{x} : \tilde{T}; \psi \Rightarrow \exists \tilde{y} : \tilde{T}'; \phi$ in the current game. This proof is a modified version of the proof of injective queries (Section 4.2.4): we define the pseudo-formula $C(\psi, \phi)$ by

$$C(\psi, M) = \perp$$

$$C(\psi, \text{event}(e(\tilde{M}))) = \perp$$

$C(\psi, \text{inj-event}(e(\tilde{M}))) = S$ such that assuming $\psi = F_1 \wedge \dots \wedge F_m$, for every $\mu_1$ that executes $F_1, \dots$, for every $\mu_m$ that executes $F_m$, letting

$$\mathcal{F} = \theta_1 \mathcal{F}_{F_1, \mu_1} \cup \dots \cup \theta_m \mathcal{F}_{F_m, \mu_m},$$

$$\mathcal{I} = \{j \mapsto (\mu_j, \theta_j I_{\mu_j}) \mid F_j \text{ is an injective event}\},$$

$$\mathcal{V} = \text{var}(\theta_1 I_{\mu_1}) \cup \dots \cup \text{var}(\theta_m I_{\mu_m}) \cup \{\tilde{x}, \tilde{y}\},$$

where for $j \le m$, $\theta_j$ is a renaming of $I_{\mu_j}$ to fresh replication indices, we have $(\mathcal{F}, (\tilde{M}), \mathcal{I}, \mathcal{V}) \in S$.

$$C(\psi, \phi_1 \wedge \phi_2) = C(\psi, \phi_1) \wedge C(\psi, \phi_2)$$

$$C(\psi, \phi_1 \vee \phi_2) = C(\psi, \phi_1) \vee C(\psi, \phi_2)$$

Given a pseudo-formula $C$, we define $\vdash C$ as in Section 4.2.4.

**Proposition 4** Let $\forall \tilde{x} : \tilde{T}; \psi \Rightarrow \exists \tilde{y} : \tilde{T}'; \phi$ be a correspondence, with $\tilde{x} = \text{var}(\psi)$ and $\tilde{y} = \text{var}(\phi) \setminus \text{var}(\psi)$. Let $\varphi = [\forall \tilde{x} : \tilde{T}; \psi \Rightarrow \exists \tilde{y} : \tilde{T}'; \phi]$ be the semantics the correspondence $\forall \tilde{x} : \tilde{T}; \psi \Rightarrow \exists \tilde{y} : \tilde{T}'; \phi$ (Definition 12), and $\varphi_{\text{ni}} = [\text{noninj}(\forall \tilde{x} : \tilde{T}; \psi \Rightarrow \exists \tilde{y} : \tilde{T}'; \phi)]$ be the semantics of the correspondence noninj($\forall \tilde{x} : \tilde{T}; \psi \Rightarrow \exists \tilde{y} : \tilde{T}'; \phi$). Let $Q_0$ be a process that satisfies Properties 3 and 4. Suppose that, in $Q_0$, the arguments of the events that occur in $\psi$ are always simple terms.

Assume that $\vdash C(\psi, \phi)$ and for all $A \in \mathcal{BB}$ and all evaluation contexts $C$ acceptable for $Q_0$, $\text{Pr}^A[C[Q_0] \subseteq \neg[\vdash C(\psi, \phi)]] \le p(A, C)$. If $\text{Bound}_{Q_0}(V, \varphi_{\text{ni}}, D_{\text{false}}, p')$, then $\text{Bound}_{Q_0}(V, \varphi, D_{\text{false}}, p' + p)$.

Proposition 4 proves injectivity much like in Section 4.2.4, but using the arguments $\tilde{M}$ of the events in $\phi$ instead of the program points and replication indices at their execution (which we do not have since in $Q_0$ we are not able to prove that these events have been executed; otherwise we would simply prove the correspondence in $Q_0$). Intuitively, $\vdash C(\psi, \phi)$ shows that, if we have different executions of injective events in $\psi$, that is, executions of such events with different pairs (program point, replication indices), then the arguments $\tilde{M}$ of each injective event in $\phi$ must be different, which implies different executions of this event.

**Proof** Let $C$ be an evaluation context acceptable for $Q_0$ with public variables $V$ that does not contain events used by $\varphi$ and $A$ be an attacker in $\mathcal{BB}$. Let $C = C(\psi, \phi)$. Consider a trace $\text{Tr}$ of $C[Q_0]$ for $A$ such that $\text{Tr} \vdash \varphi_{\text{ni}}$, $\text{Tr} \vdash [\vdash C]$, $\text{Tr}$ does not execute a non-unique event of $Q_0$, and the last configuration of $\text{Tr}$ cannot be reduced. Let $\mu \in \mathcal{E}v$ be the sequence of events in the last configuration of $\text{Tr}$. Since $\mu \in \mathcal{E}v \vdash \varphi_{\text{ni}}$,

$$\mu \in \mathcal{E}v \vdash \forall \tau_1, \dots, \tau_m \in \mathbb{N}, \forall \tilde{x} \in \tilde{T}, (\psi^\tau \Rightarrow \exists \tilde{y} \in \tilde{T}', \phi)$$

with the notations of Definition 12. By defining functions $f_j \in \mathbb{N}^m \times \prod \tilde{T} \to \mathbb{N} \cup \{\perp\}$ that map $\tau_1, \dots, \tau_m, \tilde{x}$ to the execution steps of injective events in the proof of $\phi$, and to $\perp$ when the