Cryptography Reference
In-Depth Information
2
1
−
t
, we can transform a prover which succeeds the
Schnorr Identification Protocol with a honest verifier with probability P and time com-
plexity T into an algorithm which finds the secret key x in time complexity O
(
T
2
t
Theorem 10.1.
Fo r any P
>
/
P
)
.
This is the standard way to prove that
A
must know
x
, otherwise fail the identification
protocol with probability at least 1
2
1
−
t
. (Obviously, this statement makes sense
−
when
t
is small because of the 2
t
factor in the complexity reduction.)
The proof works as follows: let us assume that
B
follows the protocol correctly
and that
A
succeeds with probability
P
to pass the final check. Clearly
A
must output
a random
r
which only depends on the initial (random) state
ρ
of
A
(so let us denote
it
r
(
ρ
)), and a value
s
which depends on some
e
and on
ρ
(so let us denote it
s
(
ρ,
e
)).
The probability is over the distribution of
ρ
and the distribution of
e
. Let Pr[
ρ
]bethe
probability of having
ρ
as an initial state. Let 1
S
(
ρ,
e
)
be 1 if the final check succeeds
with
r
(
ρ
),
e
, and
s
(
ρ,
e
), and 0 if it fails. We have
2
−
t
1
S
(
ρ,
e
)
Pr[
P
=
ρ
]
.
ρ,
e
Let
N
(
ρ
) denote the number of possible
e
's for which the protocol succeeds. We have
2
−
t
N
(
P
=
ρ
) Pr[
ρ
]
.
ρ
1, and 2
t
Clearly, by splitting the sum for
N
(
ρ
)
≤
≥
N
(
ρ
)
≥
2, we have
2
−
t
Pr[
N
(
P
≤
ρ
)
≤
1]
+
Pr[
N
(
ρ
)
≥
2]
.
Therefore we have
+
1
2
−
t
Pr[
N
(
2
−
t
P
≤
−
ρ
)
≥
2]
P
−
2
−
t
1
P
hence Pr[
N
(
ρ
)
≥
2]
≥
≥
2
. We transform
A
as follows.
−
2
−
t
1. We generate
r
from a random
ρ
.
2. For all
e
's we compute
s
(
e
) and we check if this succeeds.
3. If we have less than two succeeding
e
's, we try again. Otherwise, we have (
e
1
,
ρ,
s
1
)
and (
e
2
,
s
2
) such that
g
s
1
y
−
e
1
g
s
2
y
−
e
2
r
≡
≡
(mod
p
)
.
We thus compute
s
1
−
s
2
x
=
mod
q
.
e
1
−
e
2
Since with probability Pr[
N
(
2] we obtain two succeeding
e
's, and that this proba-
bility is greater than
2
, this works within a complexity of
ρ
)
≥
(2
t
O
/
P
) times the complexity
of
A
and
B
.
Search WWH ::
Custom Search