|
1.
Let be a set of such that .
2.
Let be an event that yields .
3.
Apply the Binary Decomposition to . This yields two protocols, each of which computes .
•
where and
•
where and
4a.
The protocol is obtained as follows.
Upon finishing , Alice determines the more-likely bit among the posterior distribution ~π_0(f^⊕n/2(X_0,Y_0) ∣X_0, ~M_0).
Alice sends to Bob, and both players declare as the answer.
Equivalently, distribution-wise we can write .
4b.
The protocol is obtained as follows.
Upon finishing , Bob determines the more-likely bit among the posterior distribution ~π_1(f^⊕n/2(X_1,Y_1) ∣Y_1, ~M_1).
Bob sends to Alice, and both players declare as the answer.
Equivalently, distribution-wise we can write .
|