Minimum disclosure proofs of knowledge (Q1110348)

Suppose you have some information which is verifiable, i.e. there exists an efficient (deterministic or probabilistic) procedure capable of certifying its validity. Then, using a so called minimum disclosure proof, you can convince someone else of the fact you have this information in a way that does not help him to determine this information. That is, if your information is the proof of some theorem, this other person will not learn anything about the proof of this theorem except that you know it. This paper offers precise but rather informal presentation (neither theorems nor lemmas) of two interactive protocols for minimum disclosure proofs. This article unifies and extends previous works on this topic. It consists of the following parts: introduction; the basic protocol for the deterministically verifiable information together with its proof; some complexity-theoretic considerations; the protocol for the probabilistically verifiable information; examples of the implementation of ``blob'', which is the basic primitive used in both protocols; discussion on cheating. It should be noted that most implementations suggested here yield the proof which is a minimum disclosure one only under some plausible but still unproven assumptions. In addition to the references given in the paper, nice introduction to the topic can be found in [\textit{M. Blum}, ``How to prove a theorem so no one else can claim it.'' Proc. Int. Congr. Math., Berkeley/Calif. 1986, Vol. 2, 1444--1451 (1987; Zbl 0672.94005)].