Cryptography Reference
In-Depth Information
view. What is missing here is the
non
-
repudiation
property (also called
undeniability
)
that should make it infeasible for a user such as Bob to repudiate messages previously
sent by him. Traditional written signatures are supposed to have this property and so
should digital signatures, which entails that the signature should be tied to a unique
user, who alone has the capacity of generating it. In the public-key setting this will
be possible because a signature will be generated by means of a private key which is
in the sole possession of the signer and this should be sufficient to convince a third
party of the authenticity of a document.
Another advantage of digital signatures with respect to MACs is implicit in the
preceding comments: since verification of the signature only requires knowledge
of the public key, these signatures are publicly verifiable and hence transferable. In
particular, this implies that a message signed by a particular signer can be shown to
a third party who can verify the signature and, in turn, can convince other parties of
the message's authenticity. This feature is very important in practice to ensure that
public keys can be securely distributed, which is an indispensable condition for the
implementation of public-key cryptography.
9.1 Digital Signature Schemes
Digital signatures play a role in the public-key setting similar to message authentica-
tion codes in the private-key setting. Thus digital signature schemes are defined in a
way similar to MACs, except that now the tag generation algorithm
Mac
is replaced
by a
signing algorithm
Sign
, which generates a
signature
. Of course, another dif-
ference with message authentication codes is that now the key generation algorithm
must generate a public/private key pair instead of a single (private) key.
9.1.1 Definition of Signature Schemes
Definition 9.1
A
digital signature scheme
(or, simply, a
signature scheme
)isa
3-tuple
Σ
=
(
Gen
,
Sign
,
Ve r
)
of polynomial-time algorithms that satisfy the fol-
lowing conditions:
•
The key generation algorithm
Gen
is a probabilistic algorithm that takes as input
a
security parameter
1
k
and outputs a pair
of keys called, respectively,
the public key and the private key. We write, as usual,
(
pk
,
sk
)
1
k
(
pk
,
sk
)
←
Gen
(
)
.
•
The signing algorithm
Sign
takes as input a private key
sk
and a message
m
(in
a message space
M
which may depend on
pk
) and outputs a signature
σ
, so that
we write
σ
←
Sign
(
sk
,
m
)
.
Sign
is a probabilistic algorithm in most cases.
•
The verification algorithm
Ve r
is a deterministic algorithm that takes as input a
public key
pk
, a message
m
, and a signature
σ
and outputs a bit
b
∈{
0
,
1
}
.This
output
b
:=
Ve r
(
pk
,
m
,σ)
is interpreted as meaning
valid
when
b
=
1 and
invalid
when
b
=
0.
