2
$\begingroup$

The UC framework [Can00 (version of 2020-02-11)] defines security (defn 9) as for all adversaries there exists a simulator such that for all environments the environment output is indistinguishable in the ideal and real model. $\forall A \exists S \forall E$: $$EXEC_{\varphi,S,E} \approx EXEC_{\pi,A,E}$$ where $EXEC_{\pi,A,E} = \{EXEC_{\pi,A,E}(k,z)\}_{k \in \mathbb{N},z\in\{0,1\}^*}$. This means that a simulator must "fool" all environments on any input.

Claim 14 considers specialized simulators that can depend on the environment and states that the resulting definition for security is equivalent. $\forall A \forall E \exists S$: $$EXEC_{\phi,S,E} \approx EXEC_{\pi,A,E}$$ I am not following the proof.

assume that $π$ UC-emulates $φ$ with respect to specialized simulators. That is, for any PPT adversary $A$ and PPT environment $E$ there exists a PPT simulator $S$ such that $EXEC_{φ,S,E} ≈ EXEC_{π,A,E}$. Consider the “universal environment” $E_u$ which expects its input to consist of $(\langle E \rangle, z, t)$, where $\langle E \rangle$ is an encoding of an ITM $E$, $z$ is an input to $E$, and $t$ is a bound on the running time of $E$. ($t$ is also the import of the input.) Then, $E_u$ runs $E$ on input $z$ for up to $t$ steps, outputs whatever $E$ outputs, and halts. Clearly, machine $E_u$ is PPT. (In fact, it runs in linear time in its input length.) We are thus guaranteed that there exists a simulator $S$ such that $EXEC_{φ,S,E_u} ≈ EXEC_{π,A,E_u}$.

(emphasis mine)

I do not see why that last line holds. Concretely, consider two environments $E'$ and $E''$, and let $S'$ be a specialized simulator for $E'$: $$EXEC_{\varphi,S',E'} \approx EXEC_{\pi,A,E'}$$ but $S'$ is not a valid simulator for $E''$: $$EXEC_{\varphi,S',E''} \not\approx EXEC_{\pi,A,E''}.$$ Then $S'$ "fools" $E_u$ on input $E'$: $$EXEC_{\varphi,S',E_u}(k, (\langle E' \rangle, z, t)) \approx EXEC_{\pi,A,E_u}(k, (\langle E' \rangle, z, t))$$ but not on input $E''$: $$EXEC_{\varphi,S',E_u}(k, (\langle E'' \rangle, z, t)) \not\approx EXEC_{\pi,A,E_u}(k, (\langle E'' \rangle, z, t))$$ and thus $$EXEC_{\varphi,S',E_u} \not\approx EXEC_{\pi,A,E_u}$$ because it has to fool the environment on all inputs. Did I find a mistake or am I misunderstanding something?

$\endgroup$
3
$\begingroup$

The point that you are missing is as follows. If a protocol is UC secure for specialized simulators, then $\forall A \forall E\exists S$. In particular, this is true for the universal environment $E_u$. Denote this simulator by $S_u$. The argument is that $S_u$ is a simulator for all environments. In particular, $S_u$ working with $E_u$ on input $(\langle E\rangle,z,t)$ is exactly the same as $S_u$ working directly with the environment $E$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.