Patent ID: 7536551

Claim:
A system for evaluating a proof system comprising a prover supplied with a first random tape and a verifier supplied with a second random tape, wherein the prover communicates with the verifier to prove that the prover has a witness, comprising: a generator supplied with a third random tape, for generating a common input and a witness from the third random tape based on a predetermined function, wherein it is difficult to use the predetermined function to calculate a witness from a common input; a simulator supplied with a fourth random tape; and a distinguisher supplied with a fifth random tape, wherein the generator supplies the common input to the prover, the verifier, the simulator and the distinguisher, and supplies the witness to the prover and the distinguisher; a proof history is generated with involving the prover; a simulated proof history is generated by the simulator without involving the prover; and the distinguisher evaluates the proof system depending on whether a difference in distribution between the proof history and the simulated proof history is computationally indistinguishable for a great majority of possible common inputs and computationally distinguishable for at least one of the possible common inputs.