Setup
Recently, I became interested in simulation based proofs in the context of secure two party computation. I read some book chapters (from Secure MPC and Secret Sharing and Foundations on cryptography volume 2), papers (most importantly How To Simulate It), and posts from cryptography stack exchange, but I still do not feel confident in the application of simulation based proof techniques. As a first step, I considered a simple additive secret sharing protocol with semi-honest parties. There, the parties want to multiply their secrets and use Beaver triples for that, such that the protocol involves some interaction. I share it here because it might be useful for other beginners and I would greatly appreciate corrections, criticism, and comments.
Multiplication protocol
Assume two non-colluding parties and suppose the inputs $x,y$ belong to the parties $P_1,P_2$, respectively. Then, $P_1$ computes the shares $x_1\leftarrow \mathbb{Z}_q$, $x_2 = x-x_1\,\mathrm{mod}\,q$, where $\leftarrow \mathbb{Z}_q$ denotes uniformly random sampling from $\mathbb{Z}_q$, and sends $x_2$ to $P_2$. The same happens analogously with $y_1,y_2$ at $P_2$ such that $P_1$ has access to $x_1,y_1$ and $P_2$ has access to $x_2,y_2$ after this step. In order to compute $xy$, the parties use Beaver triples as follows. Before the protocol's execution, we sample $(\alpha,\beta)\leftarrow \mathbb{Z}_q^2$, compute $\alpha \beta \,\mathrm{mod}\,q = \gamma$ as well as the shares $\alpha_i,\beta_i,\gamma_i$ with $i\in\{1,2\}$, and distribute them to the corresponding party. Then, the $i$-th party computes
\begin{align*}
\delta_i=x_i-\alpha_i\,\mathrm{mod}\,q \quad \text{and} \quad \epsilon_i=y_i-\beta_i\,\mathrm{mod}\,q
\end{align*}
and sends $\delta_i$ as well as $\epsilon_i$ to the other party. As a result, both parties can compute
$$
\delta=\delta_1+\delta_2\,\mathrm{mod}\,q=x-\alpha\,\mathrm{mod}\,q \quad \text{and} \quad \epsilon=\epsilon_1+\epsilon_2\,\mathrm{mod}\,q=y-\beta\,\mathrm{mod}\,q.
$$
With these at hand, one finally obtains shares of $z:=z_1+z_2\,\mathrm{mod}\,q$ by means of
\begin{align*}
z_1=\gamma_1+\delta \beta_1 +\epsilon \alpha_1+\delta\epsilon\,\mathrm{mod}\,q \quad \text{and} \quad
z_2=\gamma_2+\delta \beta_2+\epsilon \alpha_2\,\mathrm{mod}\,q.
\end{align*}
We do not reveal $z_1$ or $z_2$ (even though the protocol seems useless this way).
Note that $x_2,y_1,\delta_1,\delta_2,\epsilon_1,\epsilon_2$ were exchanged and all of these quantities are uniformly random numbers in $\mathbb{Z}_q$. All other computations are local. From this, I conclude that the protocol should be perfectly secure.
Simulation based proof (attempt)
As far as I understand, simulation based proofs are especially attractive for protocols, where additionally to encryption also computations and exchange of data may reveal something. Hence, it should be suitable for the protocol specified above.
Let's try to prove the aforementioned intuition (that the protocol is perfectly secure) more formally by applying what can be found in How To Simulate It and Secure MPC and Secret Sharing. First, we observe that the protocol is (almost) symmetric. Hence, it should be sufficient if we consider only $P_1$ to be semi-honest. Next, the functionality $f(x,y):=z$ of the protocol $\pi$ is deterministic and satisfies correctness (evaluate $z_1+z_2\,\mathrm{mod}\,q$ for verification). Furthermore, the first component of $f(x,y)$ is $f_1(x,y):=z_1$ and we introduce the view of $P_1$ by
\begin{align*}
\mathrm{view}_1^{\pi}(x,y):=\left(x,r_1,m_1,m_2,\dots,m_t\right)\in \mathbb{Z}_q^{1\times p},
\end{align*}
where $r_1$ is the content of $P_1$'s internal random tape, and $m_1,m_2,\dots,m_t$ denote the received messages.
Then, a simulation based proof for perfect security requires that there exists a probabilistic-polynomial time simulator $S_1$ such that
\begin{align*}
\{S_1\left(x,f_1(x,y)\right)\}_{x,y\in\{0,1\}^*} \stackrel{\mathrm{perf}}{\equiv} \{\mathrm{view}_1^{\pi}\left(x,y\right)\}_{x,y\in\{0,1\}^*}.
\end{align*}
Perfect indistinguishability between these probability ensembles should be reached if for all possible $x,y\in\{0,1\}^*$ the statistical distance
\begin{equation}
\label{eq:dist}
\Delta(\mathrm{view}_1^\pi(x,y),S_1(x,f_1(x,y)):=\frac{1}{2} \sum_{\boldsymbol{w}\in\mathbb{Z}_q^{1\times p}} |\mathrm{Pr}(\mathrm{view}_1^{\pi}(x,y)=\boldsymbol{w})-\mathrm{Pr}(S_1(x,f_1(x,y)=\boldsymbol{w})|
\end{equation}
vanishes. We start by running $\pi$ and, according to the definition from before, find
$$
\mathrm{view}_1^{\pi}\left(x,y\right)=\left(x,x_1,y_1,\alpha_1,\beta_1,\gamma_1,\delta_2,\epsilon_2\right),
$$
where $x_1$ stems from $P_1$'s internal source of randomness (the random tape), $\alpha_1,\beta_1,\gamma_1$ stem from an auxiliary offline source of randomness (but may be considered as messages as well?), and $y_1,\delta_2,\epsilon_2$ are messages received from $P_2$. Note that apart from $x$ all of these quantities are uniformly random in $\mathbb{Z}_q$. Moreover, from $\mathrm{view}_1^{\pi}(x,y)$ all other quantities, that $P_1$ has access to, can be computed. Hence, $\mathrm{view}_1^{\pi}(x,y)$ contains all of $P_1$'s information.
It remains to find a suitable $S_1$. To this end, we choose
$$
S_1(x,f_1(x,y))=\left(x,\tilde{x}_1,\tilde{y_1},\tilde{\alpha}_1,\tilde{\beta}_1,\tilde{\gamma}_1,\tilde{\delta}_2,\tilde{\epsilon}_2\right)
$$
such that each component in $(\tilde{x}_1,\tilde{y_1},\tilde{\alpha}_1,\tilde{\beta}_1,\tilde{\gamma}_1,\tilde{\delta}_2,\tilde{\epsilon}_2)$ is uniformly random in $\mathbb{Z}_q$ (it seems that we do not need the output $f_1(x,y)$). Finally, since $S_1$ can exactly mimick the distributions of each component in $\mathrm{view}_1^\pi$, it is easy to see that $\Delta(\mathrm{view}_1^\pi(x,y),S_1(x,f_1(x,y))=0$ for all $x,y$. In other words, everything apart from $x$ (which is granted to $P_1$) is indistinguishable from random garbage. Thus, we conclude that the protocol is perfectly secure.
Some observations/questions
- In the context of secure two-party computations, it seems that whenever $\mathrm{view}_1^\pi$ contains only random variables (except $x$), we can construct a simulator by simply choosing variables with the same distributions as the random variables. This makes the simulator construction trivial.
- In case, one variable in $\mathrm{view}_1^\pi$ acts non-random, we must construct it from $x,f_1(x,y)$ in order to obtain a valid simulator. To this end, suppose $y_1=y$ because $P_2$ made a mistake. Clearly, this is not secure since $P_1$ has now access to $x,y$. However, only from $x,f_1(x,y)$ we cannot possibly construct $y$ because $x$ has nothing to do with $y$ and $f_1(x,y)$ is uniformly random in $\mathbb{Z}_q$ by construction. Thus, this protocol is insecure due to $\Delta(\mathrm{view}_1^\pi(x,y),S_1(x,f_1(x,y))\neq 0$.
- What is the reason that the simulator needs $f_1(x,y)$?
