Simulating a joint distribution of an *almost* deterministic function

Question

The following is in the context of secure MPC.

Suppose that there is a functionality $f(x,y)$ which outputs 'answer' with probability $1-\textrm{negl}(n)$ for some security parameter $n$, and 'other answer' with negligible probability. Consider a Simulator $\mathcal{S}_1$. Now wlog, if I show that $\textrm{view}_1(\Pi)$ is computationally indistinguishable from $\mathcal{S}_1(x, f_1(x,y))$, can I conclude that the joint distribution $[\mathcal{S}_1(x, f_1(x,y)), f(x,y)]$ is computationally indistinguishable from $[\textrm{view}_1(\Pi), \textrm{output}(\Pi)]$?

The reasoning would be that the joint distribution is only affected by a negligible factor of the uncertainty of the output.

Answer 1

Lets first state the definitions. Consider a two party computation, where $i\in(1,2)$

Definition 1 Let $f$ be a functionality, and $f_i$ be it's view from Party $P_i$. Let $\mathcal{S}_i$ be a simulator executing a probabilistic polynomial time algorithm for Party $P_i$. We say that $\pi$ securely realizes $f$ if there exist some $\mathcal{S}$ exists that satisfies the following property:

$$[\mathcal{S}_i(x, f_i(x,y)), f(x,y)]\overset{c}\equiv [\text{view}_i(x,y), \text{output}(\pi)]$$

Definition 2 Let $f$ be a functionality, and $f_i$ be it's view from Party $P_i$. Let $\mathcal{S}_i$ be a simulator executing a deterministic algorithm for Party $P_i$. We say that $\pi$ securely realizes $f$ if there exist some $\mathcal{S}$ exists that satisfies the following property:

$$\mathcal{S}_i(x, f_i(x,y))\overset{c}\equiv \text{view}_i(x,y)$$

Definition 3 Probability distributions A(x,n) and B(x, n) are said to be Computational indistinguishably, denoted by $A\overset{c}\equiv B$ if $\exists$ a distinguisher D and negligible function $negl(.)$ s.t $$\text{Pr}(D(A(x,n)) - Pr(D(B(x,n))) \leq negl(n)$$

---

Now notice the difference in the above definitions. The first definition talks about a probabilistic algorithm, while the second talks about a deterministic one. We're not talking about the $negl(n)$ difference in the output of the distinguisher, since that is already taken care of by the definition of Computational Indistinguishablity.

A functionality that has randomness is modeled by a probabilistic algorithm. In such a case, the functionality would present different output to both the parties. So, the security definition for such a protocol would have to ensure that the joint distribution of simulator output and the functionality output are indistinguishable from the real world. If it was not indistinguishable, the simulator would be able to tell you the output for other party. Which would eventually mean that your protocol is insecure.

If the functionality presents the same outputs for the parties, the wouldn't be truly random. We call this functionality a deterministic functionality and we use Definition 2 to prove the security of the protocol that realizes it. Functionality $f(x,y)$ produces the same output for both the parties, so we don't need to care for whether it's joint distribution with the output of the simulator is indistinguishable from the real world.

Coming back to your question,you can certainly apply Definition 1 in your case (where the functionality is deterministic) since definition 1 is stronger notion than definition 2. However, you should go for Definition 2 since the presence of $negl(n)$ does not make your functionality probabalistic.

You can also refer to $\S$4.2 of https://eprint.iacr.org/2016/046.pdf by Lindell