Cryptography Reference
In-Depth Information
3. Selective forgery : The adversary is able to forge the signature of a particular
message it chooses before mounting the attack.
4. Existential forgery : The adversary is able to forge a signature of at least one
message that it cannot choose.
The strongest attacks against digital signatures are those obtained by combining
the strongest adversary capability, namely adaptive chosen message attack, with
the weakest goal: existential forgery. The security notion obtained by combining
these two types of attacks is the preferred one and, in order to define it, we start by
defining the following experiment for a signature scheme
Σ = (
Gen
,
Sign
,
Ve r
),
an adversary
A
, and a security parameter k :
Definition 9.2 The signature unforgeability experiment under an adaptive chosen
message attack , Sign uf-cma
A,Σ (
k
)
, is the following:
1 k
1. Keys
(
pk
,
sk
)
are generated by running Gen
(
)
.
2. The adversary
A
is given pk and oracle access to Sign
(
sk
, )
.
A
asks a set of
Q
(
,σ)
.
3. The output of the experiment is defined to be 1 if and only if m
queries
to the oracle and outputs a message/signature pair
m
Q
and
Ve r
(
pk
,
m
,σ) =
1
.
Now, the security definition is obtained, as usual, by formalizing the fact that the
adversary cannot succeed in the previous experiment with non-negligible probability:
Definition 9.3 A digital signature scheme
is existentially
unforgeable under an adaptive chosen-message attack (UF-CMA, for short) if, for
every PPT adversary
Σ = (
Gen
,
Sign
,
Ve r
)
A
, there exists a negligible function negl such that
Pr Sign uf-cma
1
A,Σ (
k
) =
negl (
k
).
Remarks 9.1
1. In what follows, a signature scheme with the UF-CMA security property will
often be called simply a secure signature scheme but, of course, this should not
be understood as implying that the scheme is secure in some absolute sense.
2. The definition of existential unforgeability prevents the adversary from gener-
ating existential forgeries and it might seem that this requirement is too strong
because the output message in such a forgery is likely to be meaningless. But we
have already seen that, in the context of security notions for encryption schemes,
disregarding attacks because of semantic considerations is very dangerous, and
the same happens with digital signatures. As in the case of encryption, a sig-
nature scheme that allows existential forgeries cannot be used to authenticate
keys, which are random-looking if they have been chosen—as should be the
case—uniformly at random.
3. When the signing algorithm Sign is not deterministic, there will be several dif-
ferent signatures corresponding to a given message. Note that in the previous
 
Search WWH ::




Custom Search