1
$\begingroup$

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?

$\endgroup$

0

Your Answer

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