Cheating verifier

A cheating verifier is represented by a probabilistic interactive algorithm V. In addition to the inputs and outputs that V has, it may have both an additional input aitxy and an additional output The execution of P, V, and... 

For all probabilistic polynomial-time interactive algorithms V (the cheating verifier),... 

The most important case where auXy actually occurs is if several zero-knowledge proofs for the same value K are executed Then auxy( is the information that cheating verifiers may have gathered in previous executions, i.e., it consists of old values auXy 108 Completeness is the usual name for such properties in the literature, but effectiveness of proofs fits better with the terminology in Chapter 5. The same holds for the two names of the following property. 

Recall that Sim works on inputs of the form (par, K, auXyi ), like V. For simplicity, Sim is required to output triples (acc, acc observed, auxyg f) like ZKPp y, although this means that Sim simulates both V and Obs, instead of V only. This does not make the definition stricter, because any combination of V and Obs is another admissible cheating verifier V. ... 

Oren87 Yair Oren On the cunning power of cheating verifiers some observations about zero-knowledge proofs 28th Symposium on Foundations of Computer Science (FOCS) 1987, IEEE Computer Society, 1987, 462-471. 

Dispute. External verifiability of the output acc of the court in a dispute corresponds to the informal requirement made in Section 1.3, Assessment by the Public . It means If the court is honest, the observing public obtains the same result as the court. Otherwise, each of them either catches the court cheating within the dispute transaction or knows that the output acc of the court s correct entity (which they cannot see, and which a dishonest court may have manipulated) must be equal to her own observed value. Thus, if the court announces a different decision, the observers also know that the court is cheating. 

Proof sketch. The correct entities are those of the court that applies verify and, if special risk bearers are considered, one risk bearer. By the assumed structure of standard fail-stop signature schemes, the court s entity only applies the deterministic algorithms res, test, and verify to information that is known to the attacker. Hence an attacker can simulate all the actions of the court s entity on his own and does not need active attacks on it. (More formally, this could be written as a reduction, as in the previous proof sketch.) The risk bearer s entity only carries out initializations. By the precondition about correct use of initialization, cheating does not count if it involves more than one initialization for the same signer s identity id. Initializations for other identities are completely independent, hence an attacker can simulate them on his own. ... 

External verifiability requirement of the prover. For all probabilistic interactive functions V, all parameters par = ( 1 1 , and all values (K, aux) e [gen(par )] and auxy i The observer s output acc observed in all executions of ZKPp yipar, K, aux, auxyj ) is either TRUE or cheating , i.e., the observer either thinks that the verifier should be convinced or catches the verifier cheating. 

---