Cryptography Reference
In-Depth Information
We emphasize that the security proof of the Schnorr identification protocol suffers
from
being meaningful for really small values of
t
,
being valid when the verifier is honest only.
The first drawback makes the security result on the signature scheme impossible, be-
cause hash functions usually output
t
128 bits. The second drawback is reasonable
for a digital signature, because the message (and therefore how the challenge will be
generated out of the commitment) is decided before the commitment is made. However
in real identification protocols, we must prove that no verifier can extract any useful
information out of this protocol. This is still possible for really small
t
's, and the reason
why it is possible is because we can actually cheat with probability 2
−
t
.
≥
Indeed, we can make a prover
A
which succeeds with probability 2
−
t
without
knowing the secret key:
2
t
1.
A
picks a random
e
0
with 1
≤
e
0
≤
and a random
s
∈
Z
q
,
y
−
e
0
g
s
mod
p
and sends it to
B
,
3. for any received challenge,
A
outputs
s
.
2.
A
computes
r
=
Clearly this succeeds when
e
e
0
. Therefore, if a cheater
B
can extract some informa-
tion in order to break the system, we can run it with this cheater and retry every time it
fails. Within a complexity factor of 2
t
, this simulation with the cheater will break the
scheme as well, but without knowing the secret key. Therefore, if a malicious verifier
can extract some useful information from the protocol within a complexity
=
(
T
),
then there exists an algorithm that produces the same information within a complexity
O
O
(2
t
T
).
The above argument is valid, for two reasons.
The commitment is statistically indistinguishable from a right commitment: the
distribution of
y
−
e
0
g
s
mod
p
is clearly uniform in the subgroup spanned by
g
.
Therefore, making a commitment like this will not change the behavior of the
malicious verifier.
The challenge
e
cannot depend on
e
0
: the distribution of
y
−
e
0
g
s
mod
p
is also
clearly independent from
e
0
thanks to
s
, which is not revealed at this point.
Therefore, the success probability is independent from (
r
,
e
), and actually equal
to 2
−
t
.
We summarize all these properties by saying that the Schnorr identification scheme is
a
zero-knowledge interactive proof
for small values of
t
. Security for higher values (in
particular for the Schnorr signature) is an open problem.
In Chapter 11, we will see other identification protocols (like the Fiat-Shamir or
the Guillou-Quisquater protocols). Transformation into signature schemes is straight-
forward: each time the verifier has to produce something, we generate it from a
Search WWH ::
Custom Search