One-Message Protocols and Circuit Polarization Sample Clauses

One-Message Protocols and Circuit Polarization. Let two circuits be given, which on uniform random input yield output distributions PW0 and PW1 over the same set. For two given parameters α and β with α > β, the distributions are guaranteed to satisfy either PW0 — PW1 ≥ α, (4.7) or PW0 — PW1 ≤ β. (4.8) In this section we look for an efficient method to polarize the circuits: if (4.7) holds, the method should output two new circuits which produce near disjoint output distributions. If (4.8) holds, then the method should output two circuits which produce near identical distributions.4 This problem arises in the study of statistical zero knowledge (for hon- est verifiers). Assume that Vic (the verifier) has given two circuits for which the corresponding distributions satisfies (4.7) or (4.8). Xxxxx, a powerful prover who has also given the circuits, would like to convince Xxx that (4.7) holds. The following protocol achieves this (but is not zero knowledge): Xxx chooses a random sample of either PW0 or PW1 and sends it to Xxxxx. Xxxxx replies with a guess which distribution was chosen. By — ≥ repeating this, Xxx can check that Xxxxx succeeds with probability 1+α , which is only possible if PW0 PW1 α. The protocol is not zero knowledge, even if Xxx does not deviate from the protocol, because Xxx learns on which instances Xxxxx xxxx. If an efficient polarization method can be applied before the protocol, Xxx will always be able to anticipate the answer of Xxxxx which implies that the protocol is zero knowledge (in case Xxx does not deviate from the protocol). 4Deciding which of (4.7) or (4.8) holds is believed to be a computationally hard problem (an example where it seems difficult for α = 1 and β = 0 can be constructed based on the conjectured difficulty of deciding whether two given graphs are isomorphic). This means that we cannot polarize by first measuring the statistical distance.