Paper 1998/015

More on Proofs of Knowledge

Shai Halevi and Silvio Micali

Abstract

The notion of proofs of knowledge is central to cryptographic protocols, and many definitions for it have been proposed. In this work we explore a different facet of this notion, not addressed by prior definitions. Specifically, prior definitions concentrate on capturing the properties of the verifier, and do not pay much attention to the properties of the prover. Our new definition is strictly stronger than previous ones, and captures new and desirable properties. In particular, it guarantees prover feasibility, that is, it guarantees that the time spent by the prover in a proof of knowledge is comparable to that it spends in an "extraction" of this knowledge. Our definition also enables one to consider meaningfully the case of a single, specific prover.

Metadata
Available format(s)
PS
Publication info
Published elsewhere. Appeared in the THEORY OF CRYPTOGRAPHY LIBRARY and has been included in the ePrint Archive.
Keywords
Proofs of knowledgeknowledge extractorprover feasibility.
Contact author(s)
shaih @ watson ibm com
History
1998-05-04: received
Short URL
https://ia.cr/1998/015
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:1998/015,
      author = {Shai Halevi and Silvio Micali},
      title = {More on Proofs of Knowledge},
      howpublished = {Cryptology ePrint Archive, Paper 1998/015},
      year = {1998},
      note = {\url{https://eprint.iacr.org/1998/015}},
      url = {https://eprint.iacr.org/1998/015}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.