I was reading the original BGW paper. Great paper. I'm confused about Theorem 2, though.

The Theorem states, "There are functions for which there are no n/2-private protocols."

The proof is simply that two players cannot compute an OR without one of them leaking information.

But the way I see it, that isn't an MPC problem, that's a problem with the function being evaluated. Normally, the security of MPC is evaluated on the basis of whether it accurately simulates a trusted third party who receives inputs, evaluates the function and distributes outputs. Even with a trusted third party, evaluating an OR would always leak information about one of the inputs to the other party.

Similarly, couldn't you just argue by the same logic that if you evaluate the function $f(x_1, ... x_n)=x_1$ for arbitrarily high number of players $n$, then this leaks information about player 1's input?

So you could argue, by the same argument that "There are functions for which there are no 1-private protocols."

Or am I misunderstanding their proof?

  • $\begingroup$ They do not provide the proof of Theorem 2 in the paper (but it is quite straightforward). However, you misunderstood what it claims: it claims that two players cannot securely compute the OR of their bit inputs. This means that additional information (other than the output) can always leak from the protocol, not that the protocol will "leak its output". $\endgroup$ Commented Mar 30, 2018 at 20:59
  • $\begingroup$ @GeoffroyCouteau Could you talk me through why they cannot compute the OR? I can't think of an information-theoretic way for them to compute it, but I also can't think of how to prove that there isn't one. $\endgroup$ Commented Apr 1, 2018 at 0:35

1 Answer 1


As Geoffroy Couteau already pointed out, this is not about the output of the OR-function revealing information about the other player's input (as indeed it also does in the trusted third party setting).

The setting is that of 2 players Alice and Bob having access to a bidirectional secure (and noiseless) channel. For simplicity, consider the asynchronous setting, so where we players alternate sending messages to each other. (The argument extends to the synchronous setting.)

Since both players have access to all information on the channel, we can essentially view their communication as one after the other appending information to a publicly visible transcript (e.g. picture both players in a room, one after the other writing a message on a blackboard).

Suppose we could compute the OR-function privately, and consider an execution of this protocol where both player's input bits are 0. At some point during this protocol, one player, say Alice, is first to learn the computed output of the function. Consider the transcript $T$ up to this point. A few observations:

  1. Since Alice's input bit is 0, the output of the function will be equal to Bob's input bit. Thus, Alice is able to learn Bob's input bit from $T$ and her own input and random tape.

  2. $T$ should not give Bob any information about Alice's input bit, since Alice was the first to learn the other player's input bit.

  3. Therefore, $T$ could also have occurred (from Bob's perspective) if Alice's input bit had been 1, otherwise he is able to distinguish based on the transcript and learn Alice's input bit.

  4. If Alice's input bit had been 1, she should not have learned Bob's input bit from $T$.

Points 1 and 4 are clearly inconsistent given observation 3, hence such a protocol cannot exist.


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.