Score:2

Specialized simulators in Universal composability

in flag

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?

Score:4
us flag

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$.

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.