Cryptography Reference
In-Depth Information
A
B
certificate for
y
−−−−−−−−−−−−−−−−−−−→
e
←−−−−−−−−−−−−−−−−−−−
r
||
g
k
=
pick
k
,
r
mod
p
2
t
pick
e
,1
≤
e
≤
s
−−−−−−−−−−−−−−−−−−−→
check
ry
e
s
=
ex
+
k
mod
q
g
s
≡
(
mod
p
)
Figure 10.10.
The Schnorr identification protocol.
For instance, the Schnorr signature comes from the Schnorr identification protocol.
This protocol is actually performed by the owner of the secret key in order to convince
someone that he knows the secret key related to some public key. When we have
a
certificate
from a
trusted authority
, stating that the public key is linked to some
identity, we have an identification protocol. It works as follows.
Public parameters
:
p
,
q
,
g
as in the Schnorr signature.
g
x
mod
p
as in the Schnorr signature.
Interactive proof
: in order to prove that
A
knows
K
s
to
B
, they proceed as follows
(see Fig. 10.10).
1.
A
picks
k
at random, computes a
commitment r
Setup
: compute
K
s
=
x
and
K
p
=
g
k
=
mod
p
and sends it
to
B
,
2.
B
picks a
challenge e
at random such that 1
2
t
,
≤
e
≤
3.
A
computes the
response s
=
ex
+
k
mod
q
and sends it to
B
,
4.
B
checks that
ry
e
g
s
≡
(mod
p
).
The connection with the Schnorr signature is straightforward: the challenge
e
is simu-
lated by a hash function with the commitment
r
and the message.
Let us first consider a simple case where a honest
B
always accepts when interacting
with
A
. This means that
A
can compute the response to all potential challenges
e
,in
particular to any two different
e
1
and
e
2
. We can thus transform
A
into an extractor for
the discrete logarithm
x
of
y
as follows. Let
A
generate
r
, and let us send her
e
1
.We
obtain a successful response
s
1
in return. Let us now restart
A
from the same internal
state in order to generate
r
again, and let us now submit the challenge
e
2
. We obtain a
successful response
s
2
in return. Obviously we have
g
s
1
y
−
e
1
g
s
2
y
−
e
2
r
≡
≡
(mod
p
)
.
s
1
−
s
2
So
e
1
−
e
2
mod
q
is a discrete logarithm of
y
in basis
g
. This means that if
A
successfully
passes all identification challenges then she must be able to compute the discrete
logarithm of
y
. Therefore there is no way for a malicious cheater to impersonate
A
to
B
with 100% chances without the ability to solve the discrete logarithm problem.
We can prove a much stronger result, namely that there is no way to succeed with
probability
P
without the ability to compute
x
.
Here is a more precise statement.
Search WWH ::
Custom Search