Cryptography Reference
In-Depth Information
Security against impersonation
Now we explain why the Verifier is convinced that the prover must know the private key
a
.
The main ideas will also be used in the security proof of Schnorr signatures so we go
through the argument in some detail. First, we define an adversary against an identification
protocol.
Definition 22.1.4
An
adversary against an identification protocol
(with an honest ver-
ifier) is a polynomial-time randomised algorithm
A
that takes as input a public key, plays
the role of the Prover in the protocol with an honest Verifier and tries to make the Verifier
accept the proof. The adversary repeatedly and adaptively sends a value
s
0
, receives a
challenge
s
1
and answers with
s
2
(indeed, the sessions of the protocol can be interleaved).
The adversary is successful if the Verifier accepts the proof with noticeable probability
(i.e., the probability, over all outputs
s
0
by
A
and all choices for
s
1
, that the adversary
can successfully respond with
s
2
is at least one over a polynomial function of the security
parameter). The protocol is secure if there is no successful adversary.
An adversary is just an algorithm
A
so it is reasonable to assume that
A
can be run
in very controlled conditions. In particular, we will assume throughout this section that
A
can be repeatedly run so that it always outputs the same first commitment
s
0
(think of
A
as a computer programme that calls a function
Random
to obtain random bits and then
simply arrange that the function always returns the same values to
A
). This will allow us
to respond to the same commitment with various different challenges
s
1
. Such an attack
is sometimes known as a
rewinding attack
(Pointcheval and Stern [
433
] call it the
oracle
replay attack
): if
A
outputs
s
0
, receives a challenge
s
1
and answers with
s
2
then re-running
A
on challenge
s
1
is the same as “rewinding” the clock back to when
A
had just output
s
0
and then giving it a different challenge
s
1
.
Theorem 22.1.5
The Schnorr identification scheme is secure against impersonation (in
the sense of Definition
22.1.4
) if the discrete logarithm problem is hard.
We first prove the result for perfect adversaries (namely, those that impersonate the user
successfully every time the protocol is run). Later we discuss the result for more general
adversaries.
Proof
(In the case of a perfect adversary) We build an expected polynomial-time algorithm
(called the simulator) that solves a DLP instance (
g,h
) where
g
has prime order
r
and
h
g
a
where 0
a<r
is chosen uniformly at random.
The simulator will play the role of the Verifier and will try to solve the DLP by interacting
with
A
. First, the simulator starts
A
by giving it
h
as the public key and giving some choice
for the function
Random
. The adversary outputs a value
s
0
, receives a response
s
1
(chosen
uniformly at random) from the simulator and then outputs
s
2
. Since
A
is perfect we assume
that (
s
0
,
s
1
,
s
2
) satisfy the verification equation.
=
≤
