7
$\begingroup$

In Definition of secure computation in m-party case with respect to semi-honest adversary (Definition 7.5.1 in Foundations of Cryptography: Volume 2, Basic Applications by Oded Goldriech) we say protocol $\Pi$ is secure if there exists simulator $S$, such that for every $I\subset [m] = \{1,2,...,m\}$ output of simulation and $VIEW^\Pi_I$ be indistinguishable.

I don't understand why it is not enough to construct a simulator only for every party $p\in{1,2,...,m}$ (instead of any subset of parties). Besides order of quantifiers seems confusing to me too. It is mentioned in the footnote that (page 697):

Note that for a fixed $m$, it may make as much sense to reverse the order of quantifiers (i.e., require that “for every $I$ there exists an algorithm $S_I$ ”).

What does "may make as much sense" mean? The original order of quantifiers doesn't make sense to me, but the reverse does. (Reverse order just seems like definition of two-party case.)

I would appreciate:

1) explanation (maybe including simple example) that give me the intuition about why security is defined this way.

2) Suggestion of good reference (almost as good as Yehuda Lindell's tutorial) as an example of security proof in multiparty case.

$\endgroup$
3
$\begingroup$

It is not enough to be able to simulate the view of a single party, because corrupted parties may cooperate. As mentioned in the book, it may be easier to view all the corrupted parties as a single entity. It is the view of this single entity that we must simulate.

If $m$ is fixed, the order of quantifiers does not matter, because the number of subsets $I$ is fixed and so a single simulator $S$ can of course incorporate the code of the simulator $S_I$ for each $I$ (since $S$ is given $I$, it knows which of the $S_I$ to run as a subroutine).

(Edited after a comment.) If $m$ is not fixed, this may not be possible (for example if $m$ grows polynomially with the security parameter, the number of subsets grows exponentially), so you get two possibly different definitions depending on the order of the quantifiers. The one with a single simulator is stronger (if there is a single simulator that can generate a valid view, there trivially is a family of simulators that can, but not the other way around), so it is the one that was used. In practice, no protocol is known which is secure for the first definition and not the second.

$\endgroup$
  • 2
    $\begingroup$ The problem isn't that we do not know what the $I$s are, since we always assume that the simulator receives the identities of the corrupted parties. Rather, if hypothetically, there is a different simulator for every subset, and the number of parties is $n$ where $n$ is the security parameter, then you would need to record $2^n$ different simulators in your single one, which is not possible. (Even in the non-uniform model, this is just too long.) The reverse order of quantifiers seems enough conceptually, but we don't know of any protocol where it matters, so Oded went with the stronger one. $\endgroup$ – Yehuda Lindell Jul 13 '16 at 5:06
  • $\begingroup$ Thanks, do you have any suggestion as good example of multiparty proof? $\endgroup$ – Mhy Jul 13 '16 at 7:23
  • $\begingroup$ @Yehuda Lindell my understanding is "if $m$ is fixed, the order of quantifiers does not matter".(According to the book and fkraiem post). But what I understand from the book is that when $m$ is not fixed only the definition with single simulator is valid but your hypothetical situation (If I understand it right) gave me the intuition that it is not possible to provide single simulator in this case! $\endgroup$ – Mhy Jul 13 '16 at 8:01
  • 2
    $\begingroup$ @Mhy Both definitions are valid, but they are different (or at least, we can't prove that they are equivalent). The decision of which one to use is somewhat arbitrary, but in cases where several valid definitions are available, it is common to choose the potentially stronger one, since it provides the stronger security guarantee. $\endgroup$ – fkraiem Jul 13 '16 at 8:05
  • $\begingroup$ "If $m$ is not fixed, this may not be possible" what does "this" refer to? sorry, I am a little bit confused. $\endgroup$ – Mhy Jul 13 '16 at 8:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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