# Disjunction of several instances of sigma protocol

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?

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.