Assume there exists zero-knowledge interactive protocol for a language $L \in NP$ i.e., if an instance $x \in L$ then prover can convince the verifier, that $x \in L$ with high probability without any other information. A zero-knowledge interactive protocol is said to sigma protocol if it satisfies following conditions

  • Three move protocol: In the protocol, prover first sends a message $m_1$ to verifier, verifier upon receiving $m_1$ send a $t \in \{0,1\}^k$ to prover. Prover based on $t$, compute and send message $m_2$ to verifier. Verifier outputs valid ot invalid based on input $x$ and the transcript $(m_1,t,m_2)$

  • Completeness: If $x \in L$, verifier returns valid

  • Special Soundness: For any $x$, if there are two accepting transcript $(m_1,t,m_2)$ and $(m_1,t^\prime,m_2^\prime)$ where $t \neq t^\prime$, one can extract witness for $x$.

  • Zero-knowledgeness: There exists a polynomial-time simulator $M$, which on input $x$ and a random $t$, outputs an accepting conversation of the form $(m_1,t,m_2)$, with the same probability distribution as conversations between the honest $(P,V)$ on input $x$

Assume, there exists a sigma protocol for language $L$ and consider $n$ instances $(x_1,x_2,x_3,.....x_n) \in L$. Consider, prover has $n$ instances of $(x_1,x_2,x_3,.....x_n) \in L$ and witness $w_i$ for only one $x_i \in L$. Can we construct a sigma protocol to prove that that atleast one $x_i \in L$ out of $n$ instances?


1 Answer 1


There is a truly elegant solution to this problem by Cramer, Damgard and Schoenmakers from CRYPTO'94. You can also read about it in Section 4 of the survey on $\Sigma$ protocols by Damgard.

  • $\begingroup$ If a protocol satisfy zero-knowledge property, does it mean simulator produces accepting transcript? $\endgroup$
    – preethi
    Commented May 25, 2018 at 6:59
  • $\begingroup$ This is a by-product. On statements in the language, yes. $\endgroup$ Commented May 27, 2018 at 4:57

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.