TANGLED INTERACTIVE PROOFS Academic Article uri icon


  • We present a formalism to distribute an interactive proof between multiple interacting verifiers. Each verifier has a belief as to whether the claim to be proven is true or false, and verifiers convince one another based on input from a prover/oracle subject to a deformation parameter δ∈(0, 1) which introduces 'noise'into the system. Usual interactive proofs are recovered at the limit δ→ 1. The utility of our theory is demonstrated by a network of nonadaptive 3-bit query PCP verifiers whose resulting soundness improves over the best known result for a single verifier of this class. There is a natural equivalence relation on such 'tangled interactive proofs' stemming from their analogy with low-dimensional topological objects. Two such proofs are considered equivalent if, roughly, one can be completely reconstructed from the other. This induces a notion of zero knowledge for our tangled …

publication date

  • January 1, 2014