zero-knowledge proof of disjunctive statements (OR proofs)

Question

I know there are standard ways to prove disjunctive statements about discrete logs, e.g. OR proof. But are there similar approaches for other class of language? For example, how can one go about proving either $G_1$ or $G_2$ has a Hamiltonian path (without leaking which one)?

Answer 1

You can use the CDS94-technique for that. Suppose you have two zero-knowledge proof systems $\sigma_1$ and $\sigma_2$, both of which consist of three messages: a commitment $com$, a (public-coin) challenge $ch$, and a response $r$. And suppose you want to prove the OR of both claims, meaning that you can generate a valid proof for (wlog.) $\sigma_1$ for any challenge even after generating the commitment, but in order to generate a valid proof for $\sigma_2$ you must get the challenge first and compute the commitment from there. So you have essentially one degree of freedom in the choice of $(ch_1, ch_2)$, i.e., one is fixed beforehand but you want to hide which one. The clue is to get a new challenge $ch'$ from the verifier and guarantee that $(ch_1, ch_2, ch')$ satisfies a suitable relation, for instance sum-to-zero. So the proof system for $\sigma_1$-OR-$\sigma_2$ looks like this:

• preprocessing by the prover: compute $com_2, ch_2, rsp_2$ for a random $ch_2$
• prover sends commitment: $com_1, com_2$
• verifier sends challenge: $ch'$
• prover computes $ch_1 \leftarrow ch' - ch_2$ and uses this to complete $\sigma_1$
• prover sends response: $(ch_1, rsp_1), (ch_2, rsp_2)$
• verifier verifies that $(com_1, ch_1, rsp_1)$ is valid, that $(com_2, ch_2, rsp_2)$ is valid, and that $ch_1 + ch_2 + ch' = 0$

You can use $\sum_i ch_i = ch'$ for OR-proofs consisting of any number of claims. However, in some cases you want to prove more specific facts such as "$t$ out of these $n$ claims are true". In this case, you want to use Shamir's secret sharing and exchange the sum-to-zero relation for a polynomial of degree $n+1-t$: this guarantees that all $n-t$ degrees of freedom for choosing $ch_i$ must be used up by the false claims.

The CDS-94 technique applies to any zero-knowledge proof system that follows this three-pass public coin structure. Schnorr's protocol for proving discrete logarithm knowledge is just one particular case of that structure.

CDS94: Cramer, Ronald, Ivan Damgård, and Berry Schoenmakers. "Proofs of partial knowledge and simplified design of witness hiding protocols." CRYPTO 1994.