3
$\begingroup$

The security of the multi-party computation protocol can be given by real/ideal world paradigm. The simulator based proof considers the joint distribution of adversary's output and honest parties output.

Why is there a need to take the joint distribution in this case? Why can't we just take adversary's output to prove the security?

$\endgroup$

1 Answer 1

2
$\begingroup$

The adversary's output/view captures only what the adversary learns about the honest party's input. But "learning too much about the inputs" is not the only thing that can go wrong in an MPC protocol. Suppose the adversary causes the honest party to produce an "impossible" output. This is surely an attack, even if the adversary doesn't learn anything about the honest party's input. Thus, we have to compare real vs ideal with respect to both the adversary's view and the honest party's output.

Example of an "impossible" output: Alice has $x$, Bob has $y$, and they use MPC to compute $\text{max}(x,y)$. Corrupt Alice behaves in a way such that Bob outputs $y-1$. But there is no $x$ such that $\text{max}(x,y) = y-1$, this is an impossible output.


I should also say that these comments do not apply for semi-honest security, computing a deterministic function. Under semi-honest corruption, we already know (from the correctness property) that honest parties will output the correct thing. An adversary has no power to deviate from the protocol, so it has no power to adversely affect the honest party's outputs. In this security model, indeed you can define security only in terms of the adversary's view, resulting in an equivalent definition.

$\endgroup$
2
  • $\begingroup$ Doesn't that also apply to the semi-honest setting when the functionality is randomized? $\endgroup$ Commented Mar 15 at 10:46
  • $\begingroup$ Yes, that is true, let me re-phrase my response. $\endgroup$
    – Mikero
    Commented Mar 15 at 14:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.