Proofs of knowledge

A pair of papers which investigate the notions of proof of knowledge and proof of computational ability.


On defining proofs of knowledge

Authors: M. Bellare and O. Goldreich

Abstract: The notion of a ``proof of knowledge,'' suggested by Goldwasser, Micali and Rackoff, has been used in many works as a tool for the construction of cryptographic protocols and other schemes. Yet the commonly cited formalizations of this notion are unsatisfactory and in particular inadequate for some of the applications in which they are used. Consequently, new researchers keep getting misled by existing literature. The purpose of this paper is to indicate the source of these problems and suggest a definition which resolves them.

Ref: Extended abstract in Advances in Cryptology - Crypto 92 Proceedings, Lecture Notes in Computer Science Vol. 740, E. Brickell ed, Springer-Verlag, 1993. Full paper available below.

Full paper: Available as compressed postscript, postscript, or pdf. ( Help if this doesn't work).


Proving computational ability

Authors: M. Bellare and O. Goldreich

Abstract: We investigate extending the notion of a proof of knowledge to a proof of the ability to perform some computational task. We provide some definitions and protocols for this purpose.

Ref: Manuscript, August 1992. Available below.

Full paper: Available as compressed postscript, postscript, or pdf. ( Help if this doesn't work).