I'm having difficulty finding a detailed proof for one of the most basic protocols in cryptography, that is the Schnorr protocol, or the sigma protocol for proving knowledge of a discrete log.

Most proofs I can find gloss over the running time of the extractor, or just assume the prover works with probability 1. But the prover could succeed with any probability $\epsilon > 1/2^\lambda$ and the extractor must operate in expected time $poly(\lambda)/(\epsilon-1/2^\lambda)$. Furthermore, the extractor has no control over the prover except what challenges it feeds to the prover (e.g. the prover's randomness is independent of the extractor). These criteria come from what I understand to be the commonly accepted definition of 'proof of knowledge' from On Defining Proofs of Knowledge.

Where can I find an acceptable proof that abides by these criteria?



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.