Score:1

Detailed Proof of Knowledge for Discrete Log

gb flag

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?

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.