Cryptography Reference
In-Depth Information
of knowledge of
s
A
to Bob, without revealing anything about
s
A
, called a zero-
knowledge proof of a modular square root of
t
A
.
Protocol Steps
1. Alice selects an
m
m
2
(mod
n
) to Bob. (The
value
m
is called a
commitment
and
w
is called a
witness
.)
)
∗
and sends
w
∈
(
Z
/n
Z
≡
2. Bob chooses
c
∈{
0
,
1
}
and sends it to Alice. (The value
c
is called a
challenge
.)
ms
A
(mod
n
) and sends it to Bob. (The value
r
is called
3. Alice computes
r
≡
the
response
.)
4. Bob computes
r
2
modulo
n
. f
r
2
wt
A
(mod
n
), then terminate the
protocol with Bob rejecting the proof. Otherwise go to step 5.
≡
5. Reset
a
's value to
a
1 and go to step 1 if
a>
0. If
a
= 0, then terminate
the protocol with Bob accepting the proof.
−
Analysis
The above protocol is a three-pass protocol in the sense that three messages
are exchanged,
w
,
c
, and
r
. (Compare with the analysis of the three-pass pro-
tocol discussed on page 199.) The process in steps 1 and 2 is an instance of the
cut-and-choose protocol, whereas the process in steps 2 and 3 (given a witness
from step 1), is an instance of a challenge-response protocol. Moreover, each
iteration of these rounds (namely, for each value of
a
used), are sequential and
independent. In other words, there is a variation from one round to the other,
with the initial randomness giving the guarantee that theywill be so. The pro-
tocol is designed to ensure that onlythe prover, Alice, with knowledge of the
secret
s
A
is capable of answering all of the challenges with correct responses,
and none of these responses give awayanyinformation about the secret.
Interactive proof (of knowledge) systems have to satisfy certain properties in
order to be valid. One of them is called (knowledge)
completeness
, which means
that if Alice actuallyknows the secret,
s
A
in this case, then Bob will always
accept Alice's proof. We now demonstrate that the above protocol satisfies this
property. If Alice knows
s
A
, then the response
r
ms
c
A
(mod
n
) is a square
≡
root of
wt
c
A
(mod
n
) (for any
c
) so Bob will accept.
Another propertythat interactive proof (of knowledge) systems must satisfy
is that of (knowledge)
soundness
, which means that if Alice can convince Bob
with reasonable probability, then she must know the secret. We now show that
the above protocol is sound. It is easilyseen, from the choice of the challenge
c
,
that Eve can convince Bob, with probabilityof 50%, that she is Alice if
a
=1.
However, this is the
highest
probabilitythat a
cheating prover
such as Eve can
achieve in this protocol. To see this, suppose that Eve can actuallyconvince
Bob that she is actuallyAlice, with probabilitygreater than 1
/
2. What this
means in the protocol is that Eve knows a value of
w
for which she can answer
both challenges
c
= 1 and
c
= 0. Hence, Eve can find
r
1
and
r
2
such that
r
1
≡
w
(mod
n
) and
r
2
≡
wt
A
(mod
n
)
.
Search WWH ::
Custom Search