Simulation based proof for Beaver's multiplication protocol

Question

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

1. 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.
2. 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$.
3. What is the reason that the simulator needs $f_1(x,y)$?

Answer 1

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

What if the distribution of those random variables depends on $y$, which you don't know? In other words, for different choices of $y$, the random variables will be distributed differently.

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

If you are constructing a simulator for $P_1$ then you are considering the case where $P_1$ is corrupt and $P_2$ is honest. An honest $P_2$ is not going to make the mistake that you mention. Instead, they will sample $y_1$ uniformly from $\mathbb{Z}_q$.

You are right that it would not be secure for $P_2$ to consistently choose $y_1 = y$. That is why the protocol doesn't instruct honest parties to do that.

3. What is the reason that the simulator needs $f_1(x,y)$?

If $P_1$ is corrupt and runs the protocol honestly on input $x$, and the protocol is correct, then $P_1$ can correctly output $f_1(x,y)$ at the end of the protocol. If a corrupt $P_1$ can output $f_1(x,y)$ in the real interaction, then the simulator must be able to output $f_1(x,y)$ in the ideal interaction too.

I don't know what you propose as an alternative to the simulator getting $f_1(x,y)$. But if you propose that the simulator gets no information about $y$, then simulation will be impossible because of the reason I just stated (unless $f_1(x,\cdot)$ completely ignores $y$ too).