Cryptography Reference
In-Depth Information
signing key
k
−
1
, a valid signature for a given verification key
k
and message
m
).
The correctness requirement is simple and straightforward, and it does not lend
itself to multiple interpretations. This is not true for the security requirement. In fact,
there are many ways to read and interpret the security requirement. For example,
it is possible to say that a DSS is secure if it is computationally infeasible for an
adversary to compute, without knowledge of the signing key, a digital signature
for a specific message
m
. This is certainly something one would require from a
DSS. In fact, all systems overviewed and discussed in this chapter are secure in this
sense. Another way to read and interpret the security requirement is that it must
be computationally infeasible for an adversary to compute a valid signature for
any (random-looking and not necessarily meaningful) message. This is obviously
much more difficult to achieve, and not all systems overviewed and discussed in this
chapter are secure in this sense. There are even more ways to read and interpret the
security requirement.
To be a little bit more specific about the security requirement, we remember
from Section 1.2.2 that every security definition must specify both the adversary's
capabilities and the task the adversary is required to solve in order to be successful
(i.e., to break the security of the system). The terminology most frequently used
in this area was originally developed and introduced by Shafi Goldwasser, Silvio
Micali, and Ron Rivest in the 1980s [3]. It is still in use today, and we adopt it in
this topic.
With respect to the
adversary's capabilities
, it is first of all important to note
that we are in the realm of public key cryptography, where unconditional security
does not exist. Consequently, we have to make assumptions about the computing
power of the adversary we have in mind against whom we want to protect. The
assumption most frequently made in modern cryptography is that the adversary has
computing power at his or her disposal that is polynomially bound (with respect to
the length of the input for the underlying mathematical problem). Furthermore, we
have to specify what type of attack the adversary is able to mount. There are two
major classes of such attacks.
•
In a
key-only attack
, the adversary knows only the signatory's verification key.
In particular, he or she has no information about the message(s) that is (are)
signed.
•
In a
message attack
, the adversary knows the signatory's verification key and
has some information about the message(s) that is (are) signed or is at least
able to retrieve this information in some way or another.
