BGW Theorem 2- Does this proof work?

Question

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?

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.