While reading tutorials on two-party computation I encountered two (at least formally) different definitions of security (with semi-honest adversaries).
What I want to know is whether these definitions are actually different or can be shown to be equivalent.
I suspect that they are different, but I might be missing something, considering that I have not read anywhere about different definitions.
In Lindell (2016), secure two-party computation is defined like this:
For each party, the joint distribution of the simulation and the ideal result must be computationally indistinguishable from the joint distribution of the adversarial view and the computed output.
Formally, for each $i \in \{1, 2\}$, there must exist p.p.t. algorithms $S_i$ such that
$$
{\lbrace (S_i(1^n, x, f_1(x, y)), f(x, y)) \rbrace}_{x, y, n}
\stackrel{c}{\equiv}
{\lbrace (\operatorname{view}^\pi_i(x, y, n), \operatorname{output}^\pi_i(x, y, n)) \rbrace}_{x, y, n}
\,\text{.}
$$
This definition makes sense to me, since the author defines computational indistinguishability over probability ensembles indexed by both the security parameter and the input:
Two probability ensembles $X = \{X(a, n)\}_{a \in {\{0, 1\}}^*; n \in \mathbb{N}}$ and $Y = \{Y(a, n)\}_{a \in {\{0, 1\}}^*; n \in \mathbb{N}}$ are said to be computationally indistinguishable, denoted by $X \stackrel{c}{\equiv} Y$, if for every non-uniform polynomial-time algorithm $D$ there exists a negligible function $\mu(\cdot)$ such that for every $a \in \{0, 1\}^*$ and every $n \in \mathbb{N}$,
$$
\lvert \Pr[D(X(a, n)) = 1] - \Pr[D(Y(a, n)) = 1] \rvert \leq \mu(n)
\,\text{.}
$$
This means that there must be a single negligible function $\mu$ for all inputs governing the security.
In contrast, Evans et al. (2018) define computational indistinguishability for probability ensembles only indexed by the security parameter.
I have also seen definitions of computational indistinguishability like this elsewhere.
Then, when defining the security they require that the joint distributions are computationally indistinguishable for all inputs.
At least formally this suggests to me that here, the negligible function may depend on the input.
Answers to the following questions would be very much appreciated:
- Am I missing something or misunderstanding the definitions? Can the definitions shown to be equivalent exploiting the non-uniformity of the adversary?
- If not, is it the case that in the latter definition, it is not required that there is a single negligible function that "works" for all inputs?
If I am not mistaken that would imply that the two definitions are in fact different?
- In case they are different: Which of the definitions should be preferred?
