Cryptography Reference
In-Depth Information
signatory's public key (i.e.,
k
A
) to compute the one-way function for
s
and to either
verify the digital signature (if the DSS is with appendix) or recover the original
message (if the DSS is giving message recovery). In either case, it is important to
note that only A can compute
s
(because only A is assumed to know
k
−
A
), whereas
everybody can verify
s
or recover
m
(because everybody has access to
k
A
). In fact,
public verifiability is a basic property of digital signatures and corresponding DSSs.
Similar to an asymmetric encryption system, a DSS can be defined as a set
of three efficiently computable algorithms. A DSS with appendix is defined in
Definition 2.11, and its three algorithms are illustrated in Figure 2.10.
Definition 2.11 (DSS with appendix)
A
DSS with appendix
consists of the follow-
ing three efficiently computable algorithms:
•
Generate
(1
n
)
is a probabilistic key generation algorithm that takes as input
a security parameter
1
n
and generates as output a signing key
k
−
1
and
a corresponding verification key
k
. Both keys represent the public key pair
(
k, k
−
1
)
.
•
Sign
(
k
−
1
,m
)
is a deterministic or probabilistic signature generation algo-
rithm that takes as input a signing key
k
−
1
and a message
m
(i.e., the message
to be signed), and that generates as output a digital signature
s
for
m
.
9
•
Verify
(
k, m, s
)
is a deterministic signature verification algorithm that takes as
input a verification key
k
, a message
m
, and a purported digital signature
s
for
m
, and that generates as output a binary decision (i.e., whether the digital
signature is valid). In fact,
Verify
(
k, m, s
)
must yield
valid
if and only if
s
is
a valid digital signature for message
m
and verification key
k
.
So for every public key pair
(
k, k
−
1
)
and every possible message
m
,
Verify
(
k, m,
Sign
(
k
−
1
,m
))
must yield
valid
.
Similarly, a DSS giving message recovery is defined in Definition 2.12, and
its three algorithms are illustrated in Figure 2.11.
Definition 2.12 (DSS with message recovery)
A
DSS giving message recovery
con-
sists of the following three efficiently computable algorithms:
9
Optionally, the signing algorithm may also output a new (i.e., updated) signing key. Note, however,
that in a memoryless DSS, the signing key always remains the same. Consequently, this optional
output is not illustrated in Figure 2.10.
