Notes based on Chapter 10 of Justin Thaler’s textbook and (Cramer et al.,
1994)
Schnorr Sigma Protocol
Can I use some HTML/CSS magic to express this
better?
Given group \mathbb{G}_q of prime
order q, a generator g and an element h
\in \mathbb{G}_q, Paul (the prover) wants to convince Victor (the
verifier), that he knows a witness w \in
\mathbb{Z}_q such that g^w = h
while revealing no other information apart from this statement that Paul
knows such a witness. In order to do so,
Paul picks a random value r \in
Z_q and sends to Victor a =
g^r.
Victor sends Paul a challenge e
\textcolor{Salmon}{\xleftarrow{\char"1F4B0}}\Z_q
Paul sends back u = r + ew to
Victor who then checks, g^u =ah^e. Note
that there are two sources of randomness here. One picked by Paul to
mask r and one used by Victor to bind
the prover to using the witness w.
Completeness
It is easy to see that
g^u = g^{r + ew} = g^rg^{ew} =
ah^e
Special Soundness/Proof Of
Knowledge
To prove proof of knowledge we need to come up with an algorithm
K, called the knowledge extractor, such
that if Victor accepts the transcript, then K able to interact with the prover and
extract the witness. For 3 message sigma protocols like the one
described above, this is equivalent K
extracting the witness given two sets of transcripts (a, e, u) and (a,
e^\prime, u^\prime) where e \neq
e^\prime. Note this in the traditional setting, this is
equivalent to the extractor rewinding Paul once. Let w be the actual witness to the problem. Given
(a, e, u) and (a, e^\prime, u^\prime), K sets w^\star=
(u^\prime - u)(e - e^\prime)^{-1}. As q is a prime, we can find the inverse for any
element with an extended euclidean algorithm.
Victor accepts both transcripts: so we have
g^{u^\prime} = g^{r + e^\prime w}
g^{u} = g^{r + e w}
We have w = (u^\prime - u)(e -
e^\prime)^{-1} = w^\star. Therefore, K was able to extract the witness
successfully with zero error.
Honest Verifier
Zero-Knowledge
To prove that the protocol is zero-knowledge, we
must find a simulator ( a PPT algorithm) that is able to interact
internally with an honest verifier and produce a transcript that is
perfectly indistinguishable from the transcript of the protocol with an
actual prover in it.
The messages the verifier receives is a random message a \in \mathbb{G}_q and another random message
u \in \Z_q such that ah^e = g^u where e
\xleftarrow{R} \Z_q.
So the simulator picks e \in \Z_q
and u \in Z_q and sets a = g^u h^{-e}.
NOTE that as the verifier is HONEST, sampling e
\textcolor{Salmon}{\xleftarrow{\char"1F4B0}}\mathbb{Z}_q
works for us. However, if the verifier was a cheating, then the ZK proof
would be more complex.
Opening Pedersen Commitments
Pedersen Commitments are a useful primitive that
allows a user to commit to a value without revealing it, only to reveal
it later and still be bounded to the value. However, sometimes the
committer might want NOT to reveal the value in plain
text. Schnorr’s protocol allows a prover to reveal that he has knowledge
of a correct witness in zero knowledge. The protocol proceeds as
follows:
Let c = g^xh^r_x be a commitment to
x using randomness r_x
\textcolor{Salmon}{\xleftarrow{\char"1F4B0}}\Z_q, where
g,h are generators for an appropriate
group \mathbb{G}_q of prime order q.
Paul picks a,b \in \Z_q and
sends to the verifier d =
g^ah^b.
Victor sends Paul a challenge e
\textcolor{Salmon}{\xleftarrow{\char"1F4B0}}\Z_q
Paul sends back u=a + ex and
v=b + er_{x}
Victor checks g^uh^v =
dc^e
Completeness
By definition. Just do the algebra.
Special Soundness/Proof
of Knowledge
It’s pretty much the same story as the original Schnorr Sigma
protocol, except now the prover is proving that they are privy to two
secret pieces of information instead of one. We derive the following
extractor which simply rewinds the prover once with challenges e, e^\prime, to get the transcripts
- d, e, u, v
- d, e^\prime, u^\prime,
v^\prime
We know that Victor accepts, so we must have
dc^{e} = g^uh^v and dc^{e^\prime} = g^{u^\prime}h^{v^\prime}, so
we see that x = (u-u^\prime)(e^\prime -
e)^{-1} and r = (v-v^\prime)(e^\prime -
e)^{-1}. Thus it is special sound.
Honest Zero Knowledge
Again the proof is quite similar. The simulator samples e, u, v \xleftarrow{Z_q} and sets d such that g^uh^v
= dc^e. All the messages are perfectly indistinguishable. The
proof works out due to the homomorphic properties of Pedersen
commitments.
Disjunctive OR proof
Now say Paul has committed to a value x using randomness r. He wants to convince Victor that x = 0 or x=1 without revealing which
one it is.
One can use the same proof above to get the desired outcome. Note
that if Paul could predict the challenge e then the protocol is no longer sound. Paul
can send a such that the final check
artificially holds – just like the simulator. So when trying to prove
one of two things is true, Paul takes Victor’s challenge e, samples e_0
\xleftarrow{R} \Z_q and sets e_1 = e -
e_0. He then uses e_0 to cheat
and e_1 properly as he cannot predict
it before hand. Victor does cannot tell from the transcript which proof
is true and which one is not. The details are as follows:
Public knowledge: g, h, \mathbb{G}_q{q},
\Z_q, say the prover committed to 0 i.e. c = h^r. Note Victor does not know what c is committed to.
Paul samples v_1, e_1 \in \Z_q
and sets d_1(\frac{c}{g})^{e_1} =
h^{v_1}. This is the message he sends to cheat the verifier with
challenge e_1. He then samples b \in \Z_q and sets d_0 = h^b. Paul sends to Victor – d_0, d_1.
Victor samples e \xleftarrow{R}
\Z_q and sends e to
Paul.
Paul sets e_0 = e_1 - e_0. Then
he computes v_0 = b + e_0r. He then
sends to Victor v_0, v_1, e_0,
e_1.
Victor checks the following:
e = e_1 + e_0 ensuring that Paul
did not cheat both times.
d_0c^{e_0} = h^{v_0}. The honest
pass.
d_1c^{e_1} = g^e_1h^v_1. The
cheating pass.
Note if the the prover had committed to 1, it would not have changed
the protocol. Assume c=gh^r. Now Paul
does the following:
Paul samples v_0, e_0 \in \Z_q
and sets d_0 such that d_0c^{e_0} = h^{v_0}. He then samples b \in Z_q and sets d_1 = h^b.
Victor samples e \xleftarrow{R}
\Z_q and sends e to
Paul.
Victor sets e_1 = e - e_0 and
sets v_1 = b + e_1r. He then sends to
Victor v_0, v_1, e_0, e_1.
Victor checks if e= e_0 + e_1
and d_0c^{e_0} = h^{v_0} which should
pass by definition. Finally he checks if d_1c^{e_1} = g^{e_1}h^{v_1} just as
before.
Completeness
Completeness follows from the definitions.
Special Soundness
To show special soundness the knowledge extractor needs to extract
the randomness r for the commitment.
Let’s focus on the case where c = h^r.
The other case will be identical. The extractor has access to d_0, e_0, v_0 and d_0, e_0^\prime, v_0^\prime. We know the
verifier accepts, so it is easy to show that r
= \frac{v_0 - v_0^\prime}{e_0^\prime - e_0}.
Honest Verifier Zero
Knowledge
The simulator is able to sample both e_1 and e_2
so showing that this is zero knowledge is no harder than showing the
previous protocols were zero knowledge. In the first case where c=h^r it samples e_0, e_1, v_0 \in \Z_q and sets d_0 such that d_0c^{e_0} = h^{v_0}. For d_1 the prover was cheating anyway, so the
simulator can just mimic their actions.
Maurer’s Proof of Theorem 2
Proof: In Mauer’s proof sketch for Theorem 2, he is
suggesting that the simulator repeatedly choose the challenge c at random, and use “c-simulatability” to
generate a transcript (a, c, z)
distributed identically to those generated by the honest prover
interacting with the verifier when the challenge is c.
With this procedure, the probability that the simulator picks a c such that the dishonest verifier V would
have actually sent c in response to the
first-message being a, and such that V
would have accepted (a, c, z) is:
\star = \sum_{c \in S}
\Pr[\text{simulator picks challenge c}] \times q(c)
where q(c) = \Pr[A] and A is the event that the malicious V winds up sending challenge c when interacting with honest prover, and
accepting the resulting transcript
As |S| is polynomial, we have for at
least one c^\star, q(c^\star) must be non-negligible. This is
because the probability of the dishonest V accepting when interacting with the honest
prover is \sum_{c \in S} q(c) and,
\sum_{c \in S} q(c) is negligible if
q(c) is negligible for all c
Hence, the equation denoted by (\star) above at least (1/|S|) \times q(c^\star), which is
non-negligible since |S| is polynomial
and q(c^\star) is non-negligible.
Cramer, R., Damgård, I., Schoenmakers, B., 1994. Proofs of partial
knowledge and simplified design of witness hiding protocols, in: Annual
International Cryptology Conference. Springer, pp. 174–187.