Cryptography Reference
In-Depth Information
We require that any signature properly generated by
Sign
is declared valid by
Ve r
,
i.e., that for any
(
,
)
∈
M
pk
sk
output by
Gen
and any message
m
, the following
equality holds:
Ve r
(
pk
,
m
,
Sign
(
sk
,
m
))
=
1.
Signature schemes are used in a way similar to public-key encryption schemes.
Each user
S
who wants to have the ability to sign messages runs
Gen
1
k
(
)
to obtain a
pairofkeys
. The public key
pk
is published and the private key remains the
sole possession of
S
.If
S
wants to sign a message
m
, it computes
(
pk
,
sk
)
).
Any partywanting to verify the authenticity of
m
uses the public key
pk
and computes
Ve r
σ
←
Sign
(
sk
,
m
; if it obtains the value 1 then the message is authentic. Of course, the
same requirements for keys as in the case of public-key encryption are also valid here
and, in particular, secure distribution of public keys must be carried out. This seems
to lead to a vicious circle since these keys need to be authenticated which in turn
requires digital signatures, and so on, but, as we will see when discussing public-key
infrastructures in Sect.
9.7
, once a single public-key has been securely distributed by
whatever means, it can be used for the secure distribution of other public keys.
(
pk
,
m
,σ)
9.1.2 Security of Signature Schemes
A message/signature pair
which is produced by an adversary and accepted by
the verification algorithm as valid is called a (valid)
forgery
. To produce forgeries
is the goal of an adversary of a signature scheme and hence the adversary is often
called a
forger
. The security notions for signature schemes aim at preventing adver-
saries from producing forgeries but there are different classes of attacks according
to the adversary capabilities and the adversary goals. The attacks were classified by
Goldwasser et al. [92] and, from the point of view of the capability, the weakest
adversary is one that only knows the signer's public key, in which case we have a
key
-
only attack
(also called a
no
-
message attack
). But it is more reasonable to assume
that the adversary has seen valid message/signature pairs and even that the adversary
may have chosen these pairs adaptively. This leads to the stronger notion of
message
attacks
, where the adversary is assumed to have access to some of these pairs. In [92],
a hierarchy of four classes of attacks of this type is given, with the strongest being
the
adaptive chosen message attack
, in which the adversary can adaptively choose
messages to be signed by the signer acting as a 'signature oracle'. The security notion
obtained by considering these strong attacks is the preferred one for new signature
schemes. On the other hand, there is also a strength hierarchy in the types of attack
obtained by considering the adversary goal; these attacks in decreasing strength order
are (as always, success is required to happen with non-negligible probability):
(
m
,
s
)
1.
Total break
: The adversary is able to recover the signer's private key.
2.
Universal forgery
: The adversary obtains an efficient algorithm which is able to
sign any message with the signer's signature.
