Cryptography Reference
In-Depth Information
A randomised algorithm that runs in polynomial-time (i.e.,
O
(
κ
c
)for
some constant
c
Sign:
), takes as input a message
m
and a private key
sk
,
and outputs a signature
s
.
∈ N
Verify:
An algorithm (usually deterministic) that runs in polynomial-time, takes
as input a message
m
, a signature
s
and a public key
pk
, and
outputs “valid” or “invalid”.
=
We require that Verify(
m
,
Sign(
m
,
sk
)
,
pk
)
“valid”. Typically, we require that all known
algorithms to break the signature scheme require at least 2
κ
bit operations.
The main
attack goals for signatures
are the following (for more discussion see Gold-
wasser, Micali and Rivest [
235
], Section 12.2 of Katz and Lindell [
300
], Section 15.4 of
Smart [
513
], or Section 7.2 of Stinson [
532
]):
Total break:
An adversary can obtain the private key for the given public key.
Selective forgery
(also called
target message forgery
): An adversary can generate a
valid signature for the given public key on any message.
Existential forgery:
An adversary can generate a pair (
m
,
s
) where
m
is a message and
s
is a signature for the given public key on that message.
The acronym
UF
stands for the security property “unforgeable”. In other words, a
signature scheme has UF security if every polynomial-time existential forgery algorithm
succeeds with only negligible probability. Be warned that some authors use UF to denote
“universal forgery”, which is another name for selective forgery.
As with encryption, there are various attack models.
Passive attack:
The adversary is given the public key only. This is also called a “public
key only” attack.
Known message attack:
The adversary is given various sample message-signature pairs
for the public key.
Adaptive chosen-message attack (CMA):
The adversary is given a signing oracle that
generates signatures for the public key on messages of their choosing.
In this case,
signature forgery
usually means producing a valid signature
s
for the
public key
pk
on a message
m
such that
m
was not already queried to the signing oracle
for key
pk
. Another notion, which we do not consider further in this topic, is
strong
forgery
; namely, to output a valid signature
s
on
m
for public key
pk
such that
s
is not
equal to any of the outputs of the signing oracle on
m
.
As with encryption, one says the signature scheme has the stated security property under
the stated attack model if there is no polynomial-time algorithm
A
that solves the problem
with noticeable success probability under the appropriate game. The standard notion of
security for digital signatures is
UF-CMA
security.
Exercise 1.3.7
Give a precise definition for UF-CMA security.
