Proving Without Knowing: On Oblivious, Agnostic and Blindfolded Provers

We introduce oblivious decision proofs and agnostic decision proofs. In the former, the prover does not have to know whether the instance is in the language proven or not in order to be able to perform the decision proof; in the latter, the prover cannot even find out this information from interacting in the protocol. The proofs are minimum-knowledge, limiting the knowledge exposed to the verifier as well. We demonstrate an easily distributable oblivious computational minimum-knowledge decision proof protocol for proving validity/invalidity of undeniable signatures. This method, using obliviousness, solves an open problem [6] of practical value: the distributed verification of undeniable signatures. We also present an agnostic proof for the same language; an agnostic prover reduces the dissemination of trust in the system; in fact, a prover can be blindfolded and not get to learn the input. As part of the agnostic protocol, and perhaps of independent interest, we exhibit an efficient zero-knowledge proof of knowledge (possession) of both a base and an exponent of an element of a finite group (and similar algebraic structures). Finally, we show a perfect agnostic minimum-knowledge decision proof protocol for quadratic residuosity modulo Blum integers.