Cryptography Reference
In-Depth Information
22
Digital signatures based on discrete logarithms
Public key signatures and their security notions were defined in Section
1.3.2
.Theyare
arguably the most important topic in public key cryptography (for example, to provide
authentication of automatic software updates; see Section
1.1
). This chapter gives some
digital signature schemes based on the discrete logarithm problem. The literature on this
topic is enormous and we only give a very brief summary of the area. RSA signatures are
discussed in Section
24.6
.
22.1 Schnorr signatures
∈
We assume throughout this section that an algebraic group
G
and an element
g
G
of
prime order
r
are known to all users. The values (
G,g,r
) are known as
system parameters
.
Let
h
g
a
be a user's public key. A digital signature, on a message
m
with respect to a
public key
h
, can be generated by a user who knows the private key
a
. It should be hard to
compute a signature for a given public key without knowing the private key.
To explain the Schnorr signature scheme it is simpler to first discuss an identification
scheme.
=
22.1.1 The Schnorr identification scheme
Informally, a
public key identification scheme
is a protocol between a Prover and a Verifier,
where the Prover has a public key
pk
and private key
sk
, and the Verifier has a copy of
pk
.
The protocol has three communication stages: first, the Prover sends a commitment
s
0
, then
the Verifier sends a challenge
s
1
and finally the Prover sends a response
s
2
. The Verifier
either accepts or rejects the proof. The protocol is supposed to convince the Verifier that they
are communicating with a user who knows the private key corresponding to the Prover's
public key. In other words, the Verifier should be convinced that they are communicating
with the Prover.
For the Schnorr scheme [
469
,
470
] the Prover has public key
h
g
a
where
g
is an
=
element of an algebraic group of prime order
r
and 1
≤
a<r
is chosen uniformly at
g
k
and sends
random. The Prover chooses a random integer 0
≤
k<r
, computes
s
0
=
