Input Delayed Sigma-Protocol

Question

In a Sigma-protocol, the steps are (1) commitment, (2) challenge, and (3) response. In general, the prover has a statement and witness that they can use to compute the commitment step. But in some cases (like Schnorr or equality of two discrete logarithms) the prover doesn't use the statement or witness in the first step.

Are there more general Sigma-protocols that have this delayed input property, not just ones based on discrete log or other algebraic problems? What about, e.g., Graph Hamiltonicity?

Answer 1

The answer to Graph Hamiltonicity is indeed yes. The prover commits to a random cycle to begin with and only needs to know the Hamiltonian cycle at the end.

The steps are as follows (I just copied it from other question) The prover (proving graph hamiltonicity of graph G) picks a random cycle graph C, and sends its commitment to verifier.

Verifier picks a random bit b and sends it to sender.

If b = 0, then prover decommits all the edges of graph, and verifier verifies if its a cycle graph.

If b = 1, then prover computes isomporphism between hamiltonian cycle of G and cycle graph C. It then decommits all the edges in C that are not present in the isomporphism of G.