Input Delayed Sigma-Protocol

cn flag

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?

cn flag

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.

I sit in a Tesla and translated this thread with Ai:


Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.