50 %
50 %
Information about InteractiveProof

Published on January 16, 2008

Author: Stentore


Back to NP:  Back to NP LNP iff members have short, efficiently checkable, certificates of membership. Is  satisfiable?  Interactive Protocols:  Interactive Protocols Two new ingredients: Several rounds Randomness Interactive Proofs Formally:  Interactive Proofs Formally Interactive Proof System for L is a game: Completeness: There is a prover strategy P, s.t for xL, P convinces V with probability  ⅔. Soundness: For xL, any prover strategy P* convinces V with probability  ⅓. probabilistic polynomial-time verifier unlimited prover Vs. The Players:  The Players A verifier is a polynomial function: input  random-string  past-interaction  reply A prover is a function: input  past-interaction  reply all previous prover and verifier replies Example: Graph Non-Isomorphism:  Example: Graph Non-Isomorphism Input: Two graphs G=(V,E), G’=(V’,E’). Question: Does for every 1-1 map f of V onto V’ exist v,uV s.t (v,u)E but (f(v),f(u))E’ (or (v,u)E, but (f(v),f(u))E’ )? Are They Isomorphic?:  Are They Isomorphic? IP for Non-Isomorphism:  IP for Non-Isomorphism common input chooses one of the graphs at random. send P an isomorphic graph. answers which graph was chosen. 2 OK! 1 2 Correctness:  Correctness Completeness: non-isomorphic graphs  P can check which is isomorphic to the sent one. Soundness: isomorphic graphs  both isomorphic to the sent one. P succeeds with probability ½. IP:  IP Definition: IP is the class of all languages having interactive protocols with polynomial number of rounds. Easy Claims:  Easy Claims Claim: NPIP. Proof’s Idea: Every NP proof is also an IP proof. Claim: If LIP, and it has a verifier that does not flip coins, then LNP. Proof’s Idea: P would provide the answers for all V’s questions in advance. Amplification:  Amplification Observation: The constants ⅓ and ⅔ in the definition can be amplified to probabilities 1-2-p(.) and 2-p(.), for any polynomial p(.). Proof’s Sketch: Given a protocol which is correct with probability ⅔, repeat it p(.) times independently. Apply Chernoff’s inequality. Arthur-Merlin Games:  Arthur-Merlin Games … The prover (M for Merlin) is a function of the random string of the verifier (A for Arthur) as well. Define AM/MA – according to who gets to start. Easy Claim:  Easy Claim Claim: AMIP. Proof’s Idea: If A is convinced when he assumes M is that powerful, he is surely convinced when M is only less powerful. The Graph Non-Isomorphism Example Revisited:  The Graph Non-Isomorphism Example Revisited Is the graph non-isomorphism protocol, also an AM protocol? No! M knows which graph was chosen! Is there an AM protocol for this language? IP and AM:  IP and AM Theorem (without proof): IP=AM i.e, knowing the random string essentially does not increase M’s power. IP=PSPACE [Shamir90]:  IP=PSPACE [Shamir90]   given a verifier, construct an optimal prover using poly-space show the PSPACE-complete TQBF is in IP Optimal Prover:  Optimal Prover . . . possible verifier coin tosses [defines verifier’s reply] . . . . . . . . . rounds best prover reply ? ? ? ? ? ? find recursively prover reply most probable to result in acceptance Poly-Space Is Sufficient for the Prover:  Poly-Space Is Sufficient for the Prover Claim: IPPSPACE Proof: Given a verifier, the optimal strategy for the prover may be computed in poly-space. [as described above] TQBF:  TQBF Instance: A quantified Boolean formula =x1x2…xm[(x1,…,xm)] Goal: Is  true? x1x2x3 (x10  (x2>0  (|x3|<x2  |sinx3/x3-1|<x1)) TQBF and PSPACE:  TQBF and PSPACE Claim (without proof): TQBF is PSPACE-Complete. The Proof: Evaluation Tree:  The Proof: Evaluation Tree . . . . . . x1=0 x1=1  x1=0 x1=1  x1x2 … (x1,x2,…) x2 … (0,x2,…) x2 … (1,x2,…) …(0,0,…) …(0,1,…) (0,0,..,0) (0,0,..,1) (0,0,...,1,0) (0,0,...,1,1) I can’t scan the entire tree! IP for TQBF:  IP for TQBF We’ll show the verifier may be convinced (with reasonable confidence) even without scanning the entire (exponential) proof specified by the prover. First Idea:  First Idea Represent the QBF by a polynomial. Arithmization:  Arithmization  xi   1-  xi 1-(1-)(1-) F 0 T 1 x (x) x (x) (0)(1) (0)(1) Polynomials: Basic Facts:  Polynomials: Basic Facts Claim: A polynomial of degree ≤ r on d variables over a field F may have ≤ r|F|d-1 roots, unless it is identically zero. Corollary: Two polynomials of degree ≤ r on d variables over a field F may agree on ≤ r|F|d-1 places, unless they agree everywhere. Polynomials: Basic Facts:  Polynomials: Basic Facts Corollary: Two different polynomials of degree ≤ r over a field F agree on a random point with probability ≤ r/|F|. Low Degree Extension:  Low Degree Extension . . . . . . P1() P2(x1) P3(x1,x2) Pm(x1,…,xm) . . . . . . We can evaluate on a larger field! . . . . . . . . . How To Convince?:  How To Convince? Check a random path! P1() P2(x1) P3(x1,x2) Pm(x1,…,xm) . . . . . . . . . . . . . . . . . . . . . How To Convince?:  How To Convince? P1() P2(x1) P3(x1,x2) Pm(x1,…,xm) . . . . . . . . . . . . . . . . . . . . . verify this is 1 verify P2(x1) could have resulted P1(). verify P3(r1,x2) could have resulted P2(r1). verify Pm(r1,…,rm-1,xm) could have resulted Pm-1(r1,…,rm-1). r1 r2 check Pm(r1,…,rm). Example:  Example What would an honest prover do, given the formula:x1x2 (x1x2) ? x1x2 1- (1-x1∙0)(1-x1∙1) = x1 0∙1 = 0 verify this is 1  . . . . . . . . . Example:  Example What would a (dishonest) prover might do, given the formula:x1x2 (x1x2) ? x1x2 1 1 verify this is 1  verify P2(x1)=1 could have resulted P1().  1∙1 = 1 . . . . . . . . . 1 verify P3(1,x2)=x2 could have resulted P2(1). 5 1-(1-0)(1-1) = 1  check P3(1,5).  Correctness:  Correctness Completeness: If the formula is true, the prover may compute the true polynomials, and the verifier will always accept. Soundness: What if the formula is not true? If The Formula Is False…:  If The Formula Is False… P1() P2(x1) P3(x1,x2) Pm(x1,…,xm) . . . . . . . . . . . . . . . . . . . . . if this is not 1, we immediately reject if this is not the real Pm(x1,…,xm), we also immediately reject If we nevertheless accept, we get fooled somewhere! Soundness:  Soundness The probability we get fooled at some specific level is ≤ r/|F|, where r bounds the polynomials’ degrees. The probability we get fooled somewhere down the path is ≤ mr/|F| [union-bound] |F| can be made polynomially large in m. the two different polynomials agree on a random point Bound The Degrees:  Bound The Degrees Alas, the degree of the polynomials might be exponential in m, as each stage up might double it! To solve this problem, we’ll somewhat lengthen the tree, but make sure the degrees are kept small. Auxiliary Quantifier:  Auxiliary Quantifier Suppose now we have a QBF =Q1x1...Qmxm[]. ’=Q1x1R1x1Q2x2R1x1R2x2...QmxmR1x1...Rmxm[]. R is an auxiliary quantifier, designed to keep the degree of the polynomials small. We’ll arithmetize it as follows: Rx (x)  (1-x)∙(0) + x∙(1) The degree of x is made 1. The value remains the same for 0-1 variables Summing Up:  Summing Up Now we can apply the former analysis, and get that PSAPCEIP, Hence IP=PSPACE. Multi-Prover Interactive Protocol:  Multi-Prover Interactive Protocol poly many provers What is MIP?:  What is MIP? Theorem (without proof): MIP=NEXP Scaling-Down:  Scaling-Down Similarly, one can show NP is contained in MIP with O(1) provers and O(logn) random bits. Interestingly, this has implications to hardness of approximation TO BE CONTINUED…

Add a comment

Related presentations

Related pages

Interactive proof system - Wikipedia, the free encyclopedia

In computational complexity theory, an interactive proof system is an abstract machine that models computation as the exchange of messages between two parties.
Read more

Interactive proof - Wikipedia, the free encyclopedia

Interactive proof can refer to: The abstract concept of an Interactive proof system; Interactive theorem proving software
Read more

An Interactive Proof of Pythagoras' theorem

Home page of the grand prize winner in Sun Microsystem's Java programming contest in 1995.
Read more

Pythagorean Theorem - Interactive Proof -

Look at this magic proof to convince you that the Pythagorean theorem works for every right triangle. Move your mouse over the purple square to change the ...
Read more

Interaktives Beweissystem – Wikipedia

Formal. Ein interaktives Beweissystem (IBS) ist ein Protokoll zwischen einem Beweisführer (Prover) und einem Prüfer (Verifier). Dabei ist eine PSPACE ...
Read more

Shafrira Goldwasser – Wikipedia

... zweimal der Gödel-Preis in Theoretischer Informatik verliehen: Zuerst 1993 (für „The knowledge complexity of interactive proof systems ...
Read more

Interactive Proof Systems :: MPG.PuRe

Author: Radhakrishnan, Jaikumar et al.; Genre: Report; Published in Print: 1995; Open Access; Title: Interactive Proof Systems
Read more

Interactive Proofs

,Interactive Proofs,interactive proof,Interactions proof. Interactive Proofs. Publications: 545 | Citation Count: 10,571
Read more

Interactive Proof - Springer

Goldwasser S, Micali S, Rackoff C (1989) The knowledge complexity of interactive proof systems. SIAM J Comput 18:186–208. Preliminary version in 17th ACM ...
Read more

CiteSeerX — Interactive Proof: Applications to Semantics

Abstract. Abstract. Building on a previous lecture in the summer school, the introduction to interactive proof, this lecture demonstrates a specific ...
Read more