notesum.ai

Published at November 20

cs.CC

math.IT

Released Date: November 20, 2024

Authors: Pachara Sawettamalya¹, Huacheng Yu¹

Aff.: ¹Not specified

Conditional Decomposition of

\pi=(X,Y,\emph{{M}})

into

\pi_{0}

and

\pi_{1}

1. Let

\mathcal{G}

be a set of

(X_{0},Y_{1},\emph{{M}})

such that

\textnormal{adv}^{\pi}(f^{\oplus n}(X,Y)\mid X_{0},Y_{1},\emph{{M}})\geq\alpha

. 2. Let

W:=\left[(X_{0},Y_{1},M)\in\mathcal{G}\right]

be an event that

(X_{0},Y_{1},\emph{{M}})

yields

\textnormal{adv}^{\pi}(f^{\oplus n}(X,Y)\mid X_{0},Y_{1},\emph{{M}})\geq\alpha

. 3. Apply the Binary Decomposition to

\pi\mid W

. This yields two protocols, each of which computes

f^{\oplus n/2}

. •

\widetilde{\pi}_{0}=(X_{0},Y_{0},\widetilde{\emph{{M}}}_{0})

where

\widetilde{\emph{{M}}}^{0}_{0}=M^{0}

and

\widetilde{\emph{{M}}}^{+}_{0}=(Y_{1}\circ M^{1},M^{2},...,M^{r})

•

\widetilde{\pi}_{1}=(X_{1},Y_{1},\widetilde{\emph{{M}}}_{1})

where

\widetilde{\emph{{M}}}^{0}_{1}=M^{0}\circ X_{0}

and

\widetilde{\emph{{M}}}^{+}_{1}=(Y_{1}\circ M^{1},M^{2},...,M^{r})

4a. The protocol

\pi_{0}=(X_{0},Y_{0},\emph{{M}}_{0})

is obtained as follows.

(i)

Upon finishing

\widetilde{\pi}_{0}

, Alice determines the more-likely bit

B_{0}

among the posterior distribution ~π_0(f^⊕n/2(X_0,Y_0) ∣X_0, ~M_0).

(ii)

Alice sends

B_{0}

to Bob, and both players declare

B_{0}

as the answer. Equivalently, distribution-wise we can write

\pi_{0}:=\widetilde{\pi}_{0}\odot B_{0}

. 4b. The protocol

\pi_{1}=(X_{1},Y_{1},\emph{{M}}_{1})

is obtained as follows.

(i)

Upon finishing

\widetilde{\pi}_{1}

, Bob determines the more-likely bit

B_{1}

among the posterior distribution ~π_1(f^⊕n/2(X_1,Y_1) ∣Y_1, ~M_1).

(ii)

Bob sends

B_{1}

to Alice, and both players declare

B_{1}

as the answer. Equivalently, distribution-wise we can write

\pi_{1}:=\widetilde{\pi}_{1}\odot B_{1}