In the last few years, so-called interactive zero-knowledge proof systems (ZKPSs) have been invented and successfully applied for both theoretical and practical (mainly cryptographic) purposes. Such systems check whether a word w belongs to a language L (for instance, to the set L of all theorems in some formal theory T ). They are called “zero knowledge” because they do not use standard proof techniques. Instead, two programs, called “prover” and “verifier,” are interacting. The verifier asks the prover a question and then checks the answer. If it is satisfied with this answer, it may ask another question. After several successful iterations, the verifier reaches a conclusion as to whether a statement is true or false (or, in general, whether w ∈ L). The prover can work as long as it wants, but the verifier must be feasible (polynomial time in terms of the length | w | of w ). This one-sided restriction reflects a real-life situation in which a mathematician is proving a theorem and a referee is checking the proof: we have no reason to impose time limitations on the prover, but the verifier must work fast. For many interesting problems and for an arbitrary &egr; > 0, prover-verifier pairs have been designed that solve these problems with probability greater than 1 - &egr;, and that are sound in the sense that for this or for any other prover, the probability that a verifier will accept a wrong statement as a theorem is less than &egr;.

Since the verifier is limited by time restrictions, it can only apply a few tests to the prover’s answers. Why can the prover not cheat by supplying it with an answer that is tailored to these few tests? The main reason such cheating is impossible is that the verifier can generate random numbers that the prover does not know beforehand. Therefore, the prover does not know what questions will be asked or exactly how its answer is to be checked; hence, it has to submit the answers that will survive all possible tests, that is, correct answers. Judging by this argument, it appears to be essential to allow the verifier to toss coins.

The surprising result of this paper is that this coin tossing ability is not necessary. The authors define a noninteractive ZKPS in which the same results are obtained without a dialogue: given w, a prover generates a long text t ( w ), and then the verifier uses t ( w ) to check whether w ∈ L. The only randomness that the verifier is allowed to use is a random sequence &rgr; whose length is polynomial in | w |, and this &rgr; is known beforehand to the power.

The authors assume that some number-theoretic problem (related to quadratic residues) for which no efficient algorithm is known has no efficient algorithm. Based on this reasonable assumption, they prove their main result: a noninteractive ZKPS exists for an NP-complete 3-SAT problem. The proof is essentially based on related number-theoretic techniques.

In the last sections, the authors discuss the possibility of using other assumptions instead of the above-mentioned number-theoretic assumption, and formulated related open problems.