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.
Category / Keywords: Proofs of knowledge, knowledge extractor, prover feasibility. Publication Info: Appeared in the THEORY OF CRYPTOGRAPHY LIBRARY and has been included in the ePrint Archive. Date: received May 4, 1998. Contact author: shaih at watson ibm com Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | BibTeX Citation Short URL: ia.cr/1998/015 Discussion forum: Show discussion | Start new discussion