\(\Sigma\) Protocols

Definitions

let \(R\) be a binary relation, i.e., \(R\) is a subset of \(\{0, 1\}^∗ \times \{0, 1\}^∗\) , where the only restriction is that if \((x, w) ∈ R\), then the length of \(w\) is at most \(p(|x|)\), for some polynomial \(p()\).

For some \((x, w) ∈ R\), we may think of \(x\) as an instance of some computational problem, and \(w\) as the solution to that instance. We call \(w\) a witness for \(x\).

We will be concerned with protocols of the following form, where \(x\) is common input to \(P, V\) and a w such that \((x, w)\in R\) is private input to \(P\):

  1. \(P\) sends a message a.

  2. \(V\) sends a random \(t-bit\) sting \(e\)

  3. \(P\) sendss reply \(z\), and \(V\) decides to accept or reject based on the data has be seen, i.e. \(x, a, e,z\)

We will assume throughout that both \(P, V\) are probabilistic polynomial time machines, so \(P\)’s only advantage over \(V\) is that he knows \(w\).

Definition \(\Sigma\)-protocol.

A protocol \(P\) is said to be a \(\Sigma\)-protocol for relation \(R\) if:

  • \(P\) is of the above 3-move form, and we have completeness: if \(P, V\) follow the protocol on input \(x\) and private input \(w\) to \(P\) where \((x, w) ∈ R\), the verifier always accepts.

  • From any \(x\) and any pair of accepting conversations on input \(x\), \((a,e,z),(a,e',z')\) where \(e\neq e'\), one can efficiently compute \(w\) such that \((x,w)\in R\). This is sometimes called the special soundness property.

  • There exists a polynomial-time simulator \(M\), which on input \(x\) and a random \(e\) outputs an accepting conversation of the form \((a, e, z)\), with the same probability distribution as conversations between the honest \(P, V\) on input \(x\). This is sometimes called special honest-verifier zero-nowledge (sHVZK).

Define \(L_R\) to be the set of \(x’s\) for which there exist \(w\) such that \((x, w) ∈ L\). Then the special soundness property implies that a \(\sigma\)-protocol for \(R\) is always an interactive proof system for \(L_R\) with error probability \(2^t\) .

Lemma 1.

The properties of \(\sigma\)-protocols are invariant under parallel composition, for instance repeating a Σ-protocol for \(R\) twice in parallel produces a new \(Σ\)-protocol for \(R\) with challenge length \(2t\).

Lemma 2

If a Σ-protocol for \(R\) exists, then for any \(t\), there exists a Σ-protocol for \(R\) with challenge length \(t\).

  • Proof.

Let \(t'\) be the challenge length for the given protocol \(P\). Then any challenge length \(t\) shorter than \(t'\) can be implemented as follows:

\(P\) sends the first message a as in \(P\). \(V\) sends a random \(t\)-bit string \(e\).

\(P\) appends \(t' − t\) zeros to \(e\), calls the result \(e'\) and computes the answer \(z\) to \(e'\) as in \(P\).

\(V\) checks \(z\) as in \(P\), as if the challenge was \(e'\) .

Any challenge length \(t > t'\) can be implemented by first repeating the given protocol in parallel \(j\) times, such that \(jt' ≥ t\), and then possibly adjusting down to \(t\) as above.

Definition Proofs of Knowledge

Let \(κ()\) be a function from bit strings to the interval \([0..1]\). The protocol \((P, V)\) is said to be a proof of knowledge for the relation \(R\) with knowledge error \(κ\), if the following are satisfied:

  • Completeness

On common input \(x\), if the honest prover \(P\) gets as private input \(w\) such that \((x, w) ∈ R\), then the verifier \(V\) always accepts.

  • Knowledge soundness

There exists a probabilistic algorithm \(M\) called the knowledge extractor.

This \(M\) gets input \(x\) and rewindable black-box access to the prover and attempts to compute \(w\) such that \((x, w) ∈ R\).

We require that the following holds: For any prover \(P∗\) , let \(\epsilon(x)\) be the probability that \(V\) accepts on input \(x\). There exists a constant \(c\) such that whenever \(\epsilon(x) > κ(x)\), \(M\) will output a correct \(w\) in expected time at most

\[\frac{|x|}{\epsilon(x)-k(x)}\]

where access to \(P∗\) counts as one step only.