In "On Defining Proofs of Knowledge" by Mihir Bellare and Oded Goldreich, the definition of knowledge soundness (KS) is (See Definition 3.1):

  • Validity (with error $\kappa$): Let $p(x)>\kappa(x)$ be the verifier accept probability. The expected number of steps of extractor bounded by: $$T1=\frac{|x|^c}{p(x)-\kappa(x)}$$

In "Incrementally Verifiable Computation" by Paul Valiant, Definition 6 (Noninteractive CS proof of knowledge), after rewrite the notation $\kappa(x)=\frac{1}{K'(|x|)}$:

  • (Kownledge extraction): Let $time_{P'}(M,x,r)\leq K'(|x|)$ and let $p(x)=\alpha>\kappa(x)$ be verifier accept probability, the expected running time is at most: $$T2=\frac{|x|^{c_2}}{p(x)}*\text{expected runtime of P'}$$

Since the expected runtime of P' is: $E_r[time_{P'}(M,x,r)]\leq K'$, we have: $$T2\leq \frac{|x|^{c_2}}{p(x)}*\frac{1}{\kappa(x)}$$

How do I prove these two definitions are equivalent?



Your Answer

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

Browse other questions tagged or ask your own question.