Cryptography Reference
In-Depth Information
UF-CMA definition, the adversary is successful only if it produces a valid signa-
ture for a message whose signature was not queried. A stronger security property
is obtained when the adversary cannot generate new valid message/signature
pairs (where the message may or may not be the same) and hence it cannot gen-
erate new valid signatures for one of the queried messages. A signature scheme
in which an adversary may obtain, from a given message/signature pair, different
signatures for the same message, is said to be malleable.
4. As in the case of message authentication codes, replay attacks in which the
adversary re-sends a copy of a message previously signed by the signer are
not prevented by the previous security definition. As in that case, the task of
preventing such attacks is usually left to a higher-level application that may
use, for example, sequence numbers or timestamps in order to make the signed
messages unique.
9.2 Some Early Signature Schemes
As happens with public-key encryption, there are digital signature schemes that have
security reductions to suitable assumptions about the hardness of computational
problems. In fact, pointing out once more the central role that one-way functions play
in cryptography, it was shown in [166] that the existence of secure (in the UF-CMA
sense) signature schemes is equivalent to the existence of one-way functions. But,
as in the case of encryption, there is also a trade-off between security and efficiency,
although in recent years secure schemes have been found that are efficient enough
for practical use. Next we are going to describe some early signature schemes that
are not secure but serve to better appreciate the possible attacks and what should be
done to prevent them.
9.2.1 Plain RSA Signatures
The first signature scheme appeared in the original RSA paper [164], where a way to
use the RSAalgorithm for this purposewas proposed. This was based on the 'trapdoor
one-way permutation paradigm' which had been introduced by Diffie and Hellman
in [67]. The idea is to use (a family of) trapdoor permutations in a way similar to
that now the signing algorithm is the decryption algorithm and the signer would sign
a message by “decrypting” it with its private key. Thus, given
where
f
S
is a
(public) trapdoor permutation and
t
S
is the associated (private) trapdoor information
known only to
S
, the signer computes the signature
s
(
f
S
,
t
S
)
f
−
1
S
. Afterwards, the
signature is publicly verifiable by just “encrypting” it with the public function and
checking that the result
f
S
(
=
(
m
)
f
−
1
S
s
)
=
f
S
(
(
m
))
is equal to
m
.
