Demonstrating that a public predicate can be satisfied without revealing any information about how

Reviewer: Catherine Ann Meadows

An interactive proof authentication protocol is a conversation between a verifier and a prover in which the verifier's goal is to determine whether the prover knows the result of a given computation, and the prover's goal is to convince the verifier that it knows the result without giving the verifier further assistance in determining it. In most cases the prover is assumed to have unlimited computational power, while the verifier's power is limited. The verifier's assurance that its goals have been obtained is probabilistic, while the prover's assurance usually results from a proof that a third party could construct a set of conversations having the same probability distribution as the set of possible conversations between a verifier and an honest prover. Chaum shows in this paper that these assumptions about the relative computational power of the verifier and the prover are not necessary by constructing a protocol in which the assumptions are reversed. In this protocol, the prover convinces the verifier that it knows a particular value S satisfying a predicate P without providing any other information about S. An interesting result of this reversal of capabilities is that Chaum is able to provide a more constructive proof of assurance than those used when the opposite assumptions hold. He provides an information-theoretic proof that the verifier gains no further information about S other than that it satisfies P. He also gives a constructive proof, based on the assumed intractability of factorization, that the odds are overwhelmingly against a prover convincing a verifier that it knows an S that satisfies P, when in fact it does not.