The Knowledge Complexity of Interactive Proof Systems

The Knowledge Complexity Of Interactive Proof Systems-Free PDF

  • Date:31 Jul 2020
  • Views:0
  • Downloads:0
  • Pages:14
  • Size:1.32 MB

Share Pdf : The Knowledge Complexity Of Interactive Proof Systems

Download and Preview : The Knowledge Complexity Of Interactive Proof Systems


Report CopyRight/DMCA Form For : The Knowledge Complexity Of Interactive Proof Systems


Transcription:

input a string Y belongingto an NP language provingprocedure Howcvcr NP only capturesa par. L A computesa string y whose length is ticular way of communicatinga proof It dealswith. bounded by a polynomial in the lcngtb of X those proofs that can be written down in a book. and writesy on a specialtape that B can read In this paper we introduce interactiveproof systems. B then checksthat fLib x where f is a to capture a more gcncral way of communicatinga. polynomial timecomputablefunction relativeto proof We deal with those proofs that can be. the language1 and if so halts and accepts explained in class Informally in a classroom the. This processis illusuatcdin figure 1 lecturer can take full advantageof the possibilityof. interacting with the recipients of the proof They, may ask questionsat crucial points of the argument. and receive answers This makes life much easier,Writing down a proof that can be checkedby every. body without interaction is a much harder task In,somesense becauseone hasto answerin advanceah. possiblequestions Let us now formally set up the,propercomputationalmodel. 2 1 InteractiveTuring machinesand interactivepairs. Fig 1 The Nf proof system of Turing machines,What is intuitively required From a theorem.
proving procedure First that it is possible to,prove a true theorem Sccomd that it is impossible. to prove a false theorem Third that communicat, ing a proof shouldbe cfhcient in the following sense. It doesnot matter how long must the provercompute, during the proving process but it is essentialthat the. computationrcquircd from tbc verifier is easy,Theorem proving procedures differ in the. underlying definition of a proof The notion of a, proof like the notion of a computation is an intuitive Fig 2 an interactivepair f Turing machines.
one Intuition however may alndmust be formalized An interactiveTuring machine ZTIIf is a Tur. Computability by detcrminist ic Turing machinesis ing machinewith a read onlyinput tape a work tape. an elegantexampleof formalizationof thc intuitive and a random tape The random tape containsan. conceptof a computation Each formalization how infinite sequenceof random bits The random tape. ever cannotentirely captureour original and intuitive can be scannedonly from left to right When we say. notions exactlybecausethey are intuitive Following that an interactivemachineflips a coin we meanthat. our intuition probabilistic algorithms R SS are it readsnext bit in its own randomtape This tape is. meansof computing though they arc not in the pre the only sourceof randomnessfor the machine In. vious formal model Similarly NP is an elegantfor addition an interactivemachinehas a read onlycom. malization of the intuitive notion of a theorem munication tape and B write only communication. tape The head writing on the latter tape movesonly. 9 By we denote ii read write head by, R a read only head and by M from left to right writesonly on a blank cell and can. a write only head not moveto the right without writing. Two ITM s A and B form an brterucrivepair of, Turirrg rtmhiws l J by I 13 Condition 1 csscntially says that if xEL there. 1 letting A and B share the same input tape and exist a way to easily prove this fact to B that succeeds. with ovcrwhclming probability This way is A s algo. 2 letting n s write only communication tape bc rithm In other words it is possible to prove a true. A s read only communication tape and vice, thcorcm so that the proofs arc easily verified B is. versa polyllomial tilnc Condition 2 says that if x not in. The interactive pair A B is ordered and machine 8 L thcrc exist no strategy for convincing B of the. starts rhc computation The machines take turns in contrary that succeeds with non negligible probabil. being active When say A is active it can perform ity In other words no one can prove a false theorem. internal computation mad and write on the proper In fact B needs not to trust or to know the machine. tapes and send a mcssagc to B by writing on the with which it is interacting It is enough for B to. appropriate communication tape The ith messageof trust the randomness of its own coin tosses Notice. A is the entire string that A writes on the communi that as for NP the emphasis is on the yes. cation tape during its ith turn The ith mcssagcof B instances if a string is in the language we want to. is similarly defined Either machine can during its show it if it is not WCdo not care Let us consider an. turn terminate the computation of the pair Consider example of an interactive proof system. a computation of A B on input x Let the compu Example 1 Let Zl dcnotc the set of integers. tation consist of II turns and let a be A s ith message bctwccn 1 and Tutthat arc relatively prime with m. and b be B s ith message Thea the lext of rhe com An elcmcnt afZi is a quadruhc residue mod n if. pulalion is defined to be the scqucncc a x2 mod tn for some x CZi clsc it is a quadruric. b l Ul b b u a is empty if it is 13 that halts the nonresidue Now let I 7 x l x EZZ is a quadratic. computation of A B in its n th turn The text of all nonrcsiduc Notice that IAENP a prover needs only. possible computations of A and B on input x will be to compute the factorization of 1 and send it to the. of re cvance to our analysis and it will bc dcnotcd by verifier without any further interaction nut looking. A B x This set has the structure of a probability ahead to zero knowledge proof systems WCwill con. space in the natural way The probability of each sider a more interesting interactive proof system for. computation in A B x is taken over the coin tosses L The vcrificr B begins by choosing n lnr 1 ran. of both machines dom mcmbcrs of Zi rl r2 r For each. i l isn hc flips a coin and if it comes up heads, 2 2 lntcractivc proof systems hc forms r r mod tn and if it comes up tails he. Let I ClO l be a language and A B an forms x r mod m Then B sends fl fz r to A. interactive pair of Turing machmes We say that The prover having unrcstrictcd computing power. A B is an inreraclive proofsysrem for L if A the finds which of the r arc quadratic rcsiducs and uses. prover has infinite power B the ver er is polyno this information to tell B the results of his last n coin. mial time and they satisfy the following properties tosses If this information is correct B accepts. 1 For any x EL given as input to A B B halts Why dots this work If m x EL then A. and accepts with probability at least 1 s for correctly predicts all last II coin tossesof B who will. dcfinitcly accept If m x not in L then the Ii are, each k and sufficiently large n just random quadratic rcsiducs and the prover will.
2 For any ITM A and for any rx not in L given respond correctly in the last part of the computation. as input to A B B accepts with probability at with probability In fact for each of the last n. most L for each k and sufficiently large n,coin tosses of B A has probability exactly l 2 of. Here 11denotes the length of the input and the pro guessing it correctly. babilitics arc taken only over B s own coin tosses. A more complex intcractivc prloof system for L that that the inclusion is a strict one We also believe that. releases essentially 0 additional knowlcdgc can be our intcractivc hierarchy dots not collapse i e that. found in section 4 2 Il k is strictly contained in fl k l In any case. intcractivc proof systems arc the right proof model to. 2 3 Intcractivc Complrxity Classes both analyze and rcducc the knowlcdgc complexity of. We dcfinc IP Interactive Pol totttial ritt e to be a language Next section is dcvotcd to the discussion. the class of languages possessingan intcractivc proof of this more subtlc notion Let us also mention Papa. system In this case we may also say that I is intcrac dimitriou P games against nature This is an. tively provable To cmphasizc that the prover has elegant characterization of PSPACE though not an. unlimited power we may write IP for If To closer efficient method of communicating a proof. analyze the role of the prover we dcfmc If to be, the class of languages having an interactive proof 3 K owledge. Complexity, system whose prover runs in time T n To focus on Communication is a tool for transferring or. the role of mtcmction we Ict fPLf n denote the exchanging knowledge Knowlcdgc has received a lot. class of languages having a proof system that on of attention in a model theoretic framework FHV. input a string x of length tl halts within f n turns HM In this context roughly speaking. Here f is a non decreasing function from natural 1 All parricipanrs are considered to have i ire. numbers to natural numbers cotqxuing power E g each participant knows. Interactive proof systems should be contrasted all logical conscqucnccsof the information in his. with the Arthur Merlin games of Babai B In hands and. those games Merlin plays the role of n and Arthur 2 The objecr Ihey rty lo know berfer is not an. the role of R The big difference is that Merlin sees availablepublic input Rather some event occurs. all results of Arthur s coin tosses This allows Babai to that is witnessed or noticed by w but not 4. prove that arbitrary interaction lis not necessaryin his participants To give an elementary example. framework it is suficicnt to al low Arthur to talk to one participant flips a coin and tells the outcome. Merlin and have Merlin respo nd at least as long to a few others who now know it The. they alternate a constant number of times Actually remaining participants do not know what the. Arthur s message to Merlin consists exactly of the outcome was and they have to decide between. sequence of its own coin tosses See figure 3 two possible worlds one in which heads came. 1N Pu r up and one in which tails came up, This scenario may not bc realistic in many practical. contexts In physics for example scientists have,bourtded resourcesand the object they try to know.
better is a public ittpur nature Our point of view is. 1 Knowledge is a norion relafive IO a spectftcmodel. of cotnputa iotJ wirh specifiedcottlpuring resources. fig 3 The Arthur Merlin proof system 2 One studies and gains knowledge about available. If membership in a language L can bc proved by an objecrs. Arthur Merlin game LfAN then for any random In this paper WCmcasurc the amount of knowledge. oracle 0 I GNP0 with probability 1 It is apparent that can be gained from a communication by a parti. that AMCIP actually AMcf P l and we bclicvc cipant with polynomially bounded resources and. invcstigatc how much knowledge must bc communi whose total probability dots not exceed 24 l 1. catcd for proving a thcorcm Our computational, complexity measure of knowlcdgc is howcvcr of some constant d bctwccn 0 and 1 Such strong indis. wider applicability For example as skctchcd in scc tir guishability is a luxury not always available and in. tion 6 ir constitutes a powerful tool for dcvcloping a any case is ot ncccssaryto dcvclop our theory. mathematical theory of cryptographic protocols The Notice that our distinguishcrs are Fed with a sin. following concept will be crucial to our analysis gle I x I bit string at a time One may consider dis. tinguishcrs that arc fed with more strings of length. 3 1 Degreesof distinguishabilityfor probabilitydistri I x I c at the same time In this case if two ensemble. butions are O distinguishable they will remain undistinguish. Let I be an infinite set of strings and c a posi able as long more poly I x I If the two ensem. tive constant For each x EI with length n Ict lI be bles arc at most p distinguishable they may remain at. a probability distribution over the II bit strings most p distinguishable or the probability of distin. Then w Bay ti i tr IT 1u E8 is a I c ensemble guishing them may become much higher This. By saying that l I is an erlsembleor a I eruemble we plays a role for deciding whether a certain crypto. mean respectively that there exist I and c or simply graphic protocol may be played securely more than. c such that iI is a I c ensemble once using the same secret key. A disrillguishet is a probabilistic polynomial time Related notions of indistinguishability have. algorithm D that on input a string s outputs a bit b been previously considered in GM in the context of. Let II Il IxE1 and l12 lI xIxEZ bc two probabilistic encryption and then in y and GGMJ in. I c ensembles Let p denote the probability that D the context of pseudo random number generation. outputs 1 on input a 1x 1 bit long string randomly. selected with probability distribution lI X Symmetri 3 2 The knowledgecomputablefrom a communica. cally pf denotes the probability that D outputs 1 on tion. input a Ix bit long string randomly selected with Which communications convey knowledge. probability distribution II Let p N O l We say Informally those that transmit the output of an. that the ensembles II and n2 arc al most p unfeasible computation a computation that we cannot. disrirlguishable if for all distinguishers D perform ourselves For example if A sends to B n. 1 p I p I x I for all k and suf fi random bits this will be 11 bits of information We. would say this contains no knowledge however, ciently long X because B could generate random bits by himself. Of particular interest will be the notion of at Similarly the result of any probabilistic polynomial. most O distinguishability or indistinguishability In time computation will not contain any knowledge. this case the two ensembles are equal with respect With this in mind we would like to derive an upper. The interactive pair A B is ordered and machine 8 starts rhc computation The machines take turns in being active When say A is active it can perform internal computation mad and write on the proper tapes and send a mcssagc to B by writing on the appropriate communication tape The ith message of A is the entire string that A writes on communi cation tape during its ith turn The ith

Related Books