Two threads of concrete cost sit outside the main line and are collected here: the cost of a system in itself, read off its members, and the cost the composition results of Section 4.5 charge, arithmetic on the budgets of Definition 4.31.
Budgeted member by member, a system also has a cost as a whole, and it is a functionality’s cost read one level up.
Definition 8.1 (Cost of a system). An invocation of a system \(\pi \) is a call reaching one of its members from outside \(\pi \); \(\pi \) services it by a cascade of internal activations before control returns outside. The cost of \(\pi \) is the pair \((T_\pi , R_\pi )\): the per-invocation time \(T_\pi \), the largest total number of steps in one such cascade — summed over the activations it triggers, one machine running at a time — and the invocation count \(R_\pi \), the number of invocations \(\pi \) answers. So \(\pi \) runs in at most \(T_\pi R_\pi \) steps.
Proposition 8.2 (System cost from member costs). Let \(\pi = \{\F _1,\dots ,\F _n\}\) with each \(\F _i\) of cost \((t_i, r_i)\), and let \(k_i\) bound the activations of \(\F _i\) within one invocation of \(\pi \). Then
and \(\pi \) runs in at most \(\sum _i t_i r_i\) steps. If every invocation activates each member at most once — \(\pi \) subroutine-respecting, \(k_i \le 1\) — then \(T_\pi \le \sum _i t_i\); if moreover each invocation drives all members, \(R_\pi \le \min _i r_i\).
Proof. An invocation activates \(\F _i\) at most \(k_i\) times, each for at most \(t_i\) steps, so it spends at most \(\sum _i k_i t_i\). The activations of \(\F _i\) over the whole execution number at most \(r_i\), and every invocation is at least one activation, so the invocations number at most \(\sum _i r_i\); the total steps are \(\sum _i (\text {activations of }\F _i)\, t_i \le \sum _i r_i t_i\). When each invocation drives all members, \(R_\pi \) invocations activate each \(\F _i\) exactly \(R_\pi \) times, so \(R_\pi \le r_i\) for every \(i\). □
Corollary 8.3 (Cost of a union). Let \(\pi _1\) and \(\pi _2\) be systems with disjoint process ids and costs \((T_1,R_1)\) and \((T_2,R_2)\). If no member of one invokes a member of the other, then
If instead each invocation of \(\pi _1\) makes at most \(k\) calls into \(\pi _2\) and the cross-call graph is acyclic, then \(T_{\pi _1 \cup \pi _2} \le T_1 + k\,T_2\) from a \(\pi _1\) entry, and symmetrically, with \(R_{\pi _1 \cup \pi _2} \le R_1 + R_2\); with the cross-calls unbounded the summary costs no longer determine the union’s.
Proof. With no cross-calls a call from outside \(\pi _1 \cup \pi _2\) enters \(\pi _1\) or \(\pi _2\) and its cascade stays there, costing at most \(T_1\) or \(T_2\) and belonging to that subsystem’s invocation count; so the per-invocation time is \(\max (T_1,T_2)\) and the counts add. A cross-call from \(\pi _1\) into \(\pi _2\) is internal to the union and extends the cascade by one invocation of \(\pi _2\), at most \(T_2\) steps; at most \(k\) of them, acyclically, give \(T_1 + k T_2\), while a call once external to \(\pi _2\) but placed from \(\pi _1\) is no longer counted, so the invocations still number at most \(R_1 + R_2\). □
The subroutine-respecting proviso is not idle: without it one call can be driven around the system without end, and \(T_\pi \) degenerates towards the whole of \(\sum _i t_i r_i\) — the same discipline that keeps a private member’s callers pinned in Remark 6.5. This system cost is dual to the \(\oplus \) of Definition 4.30: hosting a system as a bundle, one member per activation, combines its members by \(\oplus \) into \((\max _i t_i,\, \sum _i r_i)\), the cost \(\bd {c}_{\rho \setminus \varphi }\) pays in the composition costs below; calling it as a subsystem sums the times over a cascade and counts external calls, \((\sum _i t_i,\, \min _i r_i)\) in the synchronous case. Both bound the same total \(\sum _i t_i r_i\), the second more tightly when every invocation is a full pass. And \(\oplus \) recurs at the system level itself: by Corollary 8.3 non-interacting subsystems compose by it, one operator at both scales.
When the members of \(\pi \) call one another the per-invocation time turns on the shape of that calling, and one case is clean.
Proposition 8.4 (DAG systems). Suppose the call graph of \(\pi = \{\F _1,\dots ,\F _n\}\) is acyclic and every invocation activates each internal member \(\F _i\) at most \(\max _{j:\,\F _j \to \F _i} t_j\) times — the largest per-invocation time among the members that call it. Then
a per-invocation time independent of the depth of the graph.
Proof. An invocation entering a source activates each \(\F _i\) some \(a_i\) times and spends \(\sum _i a_i t_i\) steps. A source runs once and each internal \(\F _i\) at most \(\max _{j \to i} t_j\) times by hypothesis, so \(a_i \le \max _i t_i\) throughout, whence \(T_\pi \le \sum _i (\max _{j\to i} t_j)\, t_i \le (\max _i t_i) \sum _i t_i\). □
The hypothesis earns its place, for acyclicity alone does not bound \(T_\pi \). Writing \(n_{ji}\) for the calls \(\F _j\) makes to \(\F _i\) in one activation, the per-invocation activation counts solve \(a_i = \sum _{j \to i} n_{ji}\, a_j\), so \(a_i\) counts the weighted source-to-\(\F _i\) paths, and a reconvergent graph multiplies them: a chain of \(N\) diamonds — \(s \to \{A_k, B_k\} \to C_k \to \{A_{k+1}, B_{k+1}\} \to \dotsb \) — doubles the count at each level, so \(a\) at the foot is \(2^N\) and the per-invocation time is exponential in the depth. Capping each node by the maximum over its callers rather than by their sum is exactly what stops the paths accumulating — the \(\oplus \)-over-summation theme once more, and the DAG counterpart of the subroutine-respecting case \(k_i \le 1\) of Proposition 8.2, one activation relaxed to \(\max _{j\to i} t_j\). The invocation caps bound \(a_i \le r_i\) in any case; the point here is a bound in the times alone, independent of the caps and of the depth.
That last remark is the whole of the general statement: the caps alone already close the cost class, with no condition on the call structure.
Corollary 8.5 (Cost composition). A system \(\pi = \{\F _1,\dots ,\F _n\}\) whose members have costs \((t_i, r_i)\) runs in at most \(\sum _i t_i r_i\) steps over at most \(\sum _i r_i\) invocations, so \(T_\pi \le \sum _i t_i r_i\) and \(R_\pi \le \sum _i r_i\) whatever its call structure. Hence if each \(t_i\) and \(r_i\) is polynomial in a parameter \(\lambda \) and \(n\) is polynomially bounded, \((T_\pi , R_\pi )\) is polynomial: the polynomially bounded systems are closed under formation.
Proof. The step and invocation bounds are Proposition 8.2, and one invocation’s cascade is part of the whole execution, so \(T_\pi \le \sum _i t_i r_i\) too. A sum of polynomially many polynomials is a polynomial. □
No condition on the call graph is needed here, unlike the depth-free time bound of Proposition 8.4, because the caps carry it. A reconvergent cascade that would activate a member \(2^N\) times can do so only if that member answers \(2^N\) calls, so \(r_i \ge 2^N\) — a member already outside the polynomial class; within the class the cap refuses the excess and truncates the cascade at \(\sum _i r_i\) activations. This is the efficiency counterpart of Theorem 4.20: where composition preserves security — \(\rho [\pi /\varphi ]\) emulates \(\rho \) once \(\pi \) emulates \(\varphi \) — cost composition preserves efficiency, so a protocol assembled from polynomial-time functionalities is itself polynomial-time. Together the two are what the concrete apparatus is for: polynomial-time UC-secure protocols compose into polynomial-time UC-secure protocols, which is what lets the asymptotic reading below be a corollary rather than a theory of its own.
The same closure survives the operation the composition theorem runs.
Proof. The members of \(\rho [\pi /\varphi ] = (\rho \setminus \varphi ) \cup \pi \) (Definition 4.1) are those of \(\rho \) outside \(\varphi \), each polynomial as a member of \(\rho \), together with those of \(\pi \), again polynomial; they number at most \(\lvert \rho \rvert + \lvert \pi \rvert \), polynomially many. Corollary 8.5 applies. □
So the system that runs after a replacement is efficient whenever the specification \(\rho \) and the realization \(\pi \) are — Theorem 4.20 read for cost rather than security, and on the same operation.
Composition, numerically. In Theorem 4.20 the adversaries and the simulators carry over unchanged, so their budgets do. The environments are the one place something is computed, and what absorption costs is the cost of hosting. Systems are budgeted member by member, so the cost can be looked up: write \(\bd {c}_{\rho \setminus \varphi }\) for the \(\oplus \)-combination of the budgets of the members of \(\rho \setminus \varphi \) — the largest of their per-invocation times, the sum of their invocation counts, the hosted-bundle cost dual to the called-subsystem cost of Proposition 8.2 — which bounds them in any execution, whoever is driving them. The absorbed environment of Definition 4.15 runs \(\Zenv \) and those functionalities and nothing else, so
the containment in \(\ZenvSet _{\pi ,\varphi }\) being Proposition 4.16. Feeding this into the theorem, the conclusion is
Composition is free in the adversary and in the simulator, and costs the surrounding system once, on the environment side.
Transitivity, numerically. Proposition 4.12 asks that the first step’s simulator class be the second step’s adversary class, which becomes an inequality between budgets: \(\SimSet (\bd {s}) \subseteq \Aset (\bd {a}')\) holds as soon as \(\bd {s} \leq \bd {a}'\). A simulator one is willing to build must be an adversary the next step is willing to face. The proposition also asks for one class admissible for both steps, and that hypothesis must be carried here: for \(\ZenvSet \subseteq \ZenvSet _{\pi ,\varphi } \cap \ZenvSet _{\varphi ,\psi }\), which by the proof of Proposition 4.12 lies in \(\ZenvSet _{\pi ,\psi }\) as well,
Budgets alone will not do here. Written with \(\bd {z}\) in all three places the brackets would range over \(\ZenvSet _{\pi ,\psi }(\bd {z})\), \(\ZenvSet _{\pi ,\varphi }(\bd {z})\) and \(\ZenvSet _{\varphi ,\psi }(\bd {z})\), and the first is contained in neither of the others — an environment admissible for the outer pair is told nothing about \(\IDs (\varphi )\) — so no hypothesis would cover the middle probability that the triangle inequality cancels. The composition display above has no such trouble: absorption maps its one class into the other. Corollary 4.21 is the two displays put together. Along the chain of Theorem 4.24 the same two effects accumulate: the errors add, each hop widens the environment budget by the cost of hosting what it absorbs at that step, and the class relations of Remark 4.25 become the inequalities \(\bd {s}_{k+1} \leq \bd {a}_k\).
Nesting, and whether the simulator blows up. Say that an emulation statement has overhead \(f\) if it holds against \(\bigl (\Aset (\bd {a}),\SimSet (f(\bd {a})),\cdot \bigr )\) for every adversary budget \(\bd {a}\): whatever the adversary is given, the simulator one builds costs \(f\) of it. In the per-invocation budget the two components behave differently,
the query count affine — \(\gamma \) the calls the simulator places for each call of the adversary it runs, \(\delta \) its own — and the per-invocation time a maximum, \(\tau \) the simulator’s own per-activation work, since one machine runs per activation and the simulator adds only bounded work to each.
Theorem 4.20 does not touch \(f\) at all. Its adversary and simulator classes are those of the hypothesis, so a single replacement returns the very machine the hypothesis supplied and the whole price is paid on the environment side. Overheads compose in one place only: where a simulator is re-read as an adversary, which is Proposition 4.12. There \(\Sim '\) is built from \(\Sim \), itself built from \(\Adv \), so the composite has overhead \(f_2 \circ f_1\). Applying the results \(k\) times, the query budget obeys \(r_j = \gamma \, r_{j-1} + \delta \), that is
while the per-invocation time saturates, \(t_k = \max (t_0, \tau _1, \dots , \tau _k)\), bounded by the largest level’s own work and constant in depth.
The blow-up therefore lives entirely in the query count, a dichotomy turning on \(\gamma \) alone. A simulator that must place more than one call for some call of the adversary it runs has \(\gamma > 1\), and \(k\) applications cost \(\gamma ^k\): genuinely exponential, and at \(\gamma = 2\) a depth of \(20\) already costs a factor of \(2^{20}\), about a million, on the query count. A simulator that relays each call once and adds bounded traffic of its own has \(\gamma = 1\), and \(k\) applications cost \(r_0 + k\delta \): linear, \(\delta \) paid once per level. This is the property to check when a simulator is built; nothing proved here implies it. It is also why straight-line simulators matter beyond the usual reasons, rewinding being the standard way to acquire \(\gamma > 1\): one rewinding simulator anywhere in the tower puts a factor \(\gamma \) on every level below it.
The same formula governs breadth as well as depth. Theorem 4.24 builds \(\Sim _n,\dots ,\Sim _1\) by handing each simulator to the next step as its adversary, so \(n\) parallel instances compose \(n\) overheads exactly as an \(n\)-deep tower does, and Remark 4.25 read with budgets asks \(\bd {a}_k \geq f_{k+1}(\bd {a}_{k+1})\) at every link. Composing \(n\) instances of a \(\gamma = 1\) protocol costs \(n\delta \) extra queries; composing \(n\) instances of a \(\gamma = 2\) one is hopeless for even moderate \(n\).
Nothing comparable happens on the environment side, or in the per-invocation time. Each level adds the cost of hosting the shell it absorbs, and a tower’s shells are disjoint, so a depth-\(k\) nesting reaches the innermost statement at budget \(\bd {z} \oplus \bigoplus _{i \leq k} \bd {c}_i\) — its invocation count that of running the ambient system once, its per-invocation time the largest shell’s, however deep the tower. The errors behave likewise, \(k\) applications of Proposition 4.12 giving \(\sum _i \varepsilon _i\). Where a security claim degrades exponentially under nesting, the simulator’s query overhead \(\gamma > 1\) is the only possible source: one machine runs per activation, so neither the per-invocation time nor the environment budget can multiply.
Recovering the asymptotic reading. Nothing above mentions a security parameter. To get the familiar statement, index everything by \(\lambda \), let the budgets be polynomials in \(\lambda \), and ask that the advantage be negligible in it; the classes then become the polynomially bounded machines and Definition 4.11 the usual definition of UC emulation. The concrete form is the one the composition results are proved in, and the asymptotic form is a corollary of it, not the other way round — the ordering practice-oriented provable security has long argued for [2].