用户:Traveling Saleswoman/sigma protocol

$\Sigma$-Protocol

Relation

A relation ${\mathcal {R}}$ is a set of tuples $\left\{(x,w)\right\}\subseteq \left\{0,1\right\}^{*}\times \left\{0,1\right\}^{*}$.

Two Parties

• Prover P is a probabilistic polynomial time Turing machine, which has input for the problem $x$ and the solution $w$ such that $(x,w)\in {\mathcal {R}}$.

• Verifier V is also a probabilistic polynomial time Turing machine, which only has input for the problem $x$.

Definition

A protocol ${\mathcal {P}}$ is said to be a ∑-protocol for relation ${\mathcal {R}}$ if:

• ${\mathcal {P}}$ is of the following form:

  1. P sends a message a 
  2. V sends a random challenge $e\in \mathbb {Z} _{2^{t}}$
  3. P sends a reply z, and V checks the data $x,a,e,z$ to decide wither accept or reject.

• (Completeness) If two parties does exactly as stated in the scheme, then V will always output accept.
• (Soundness) If P can answer two different queries, i.e., there exists $(a,e_{1},z_{1})$ and $(a,e_{2},z_{2})$ such that $e_{1}\not =e_{2}$, then there exists a probabilistic polynomial time Turing machine M (which is called an extractor) computing w from these two tuples.
• (Honest Verifier Zero Knowledge) There exists a probabilistic polynomial time Turing machine Sim such that given a query e, Sim can output $(a,e,z)$ such that a honest verifier will output accept on this tuple and the distribution of output of Sim is the same as that between a honest prover and a honest verifier.