Cryptography Reference
In-Depth Information
produced by the Sign algorithm but with
s
2
=
0 then an adversary would be able to deter-
mine the private key
a
.
We saw in Exercise
22.2.2
that verifying Elgamal signatures is slow compared with
verifying Schnorr signatures using the method in Example
22.1.13
.Exercise
22.2.12
shows
a variant of DSA (analogous to naive Schnorr signatures) that allows signature verification
closer in speed to Schnorr signatures.
Exercise 22.2.12
(Antipa,
et al.
[
11
]) Consider the following variant of the DSA
g
k
,
s
2
=
signature
scheme:
to
sign
m
choose
1
≤
k<r
randomly,
compute
s
0
=
k
−
1
(
H
(
m
)
+
aF
(
s
0
)) (mod
r
) and return (
s
0
,
s
2
). To verify (
m
,
s
0
,
s
2
) one computes
H
(
m
)
s
−
1
2
F
(
s
0
)
s
−
1
u
1
=
(mod
r
),
u
2
=
(mod
r
) as in standard DSA and checks whether
2
g
u
1
h
u
2
.
s
0
=
(22.5)
Show that one can also verify the signature by checking, for any 1
≤
v<r
, whether
s
0
=
g
u
1
v
h
u
2
v
.
(22.6)
Show that one can efficiently compute an integer 1
≤
v<r
such that the equation (
22.6
)
can be verified more quickly than equation (
22.5
).
There is no proof of security for DSA signatures in the standard or random oracle model.
A proof of security in the random oracle model of a slightly modified version of DSA (the
change is to replace
H
(
m
) with
H
(
m
s
1
)) was given by Pointcheval and Vaudenay [
434
,
98
]
(also see Section 10.4.2 of [
553
]). A proof of security for DSA in the generic group model
7
was given by Brown; see Chapter II of [
61
].
Exercise 22.2.13
Consider a digital signature scheme where a signature on message
m
with respect to public key
h
is an integer 0
≤
s
<r
such that
h
s
)
.
=
H
(
m
s
What is the problem with this signature scheme?
22.2.3 Signatures secure in the standard model
None of the signature schemes considered so far has a proof of security in the standard
model. Indeed, as mentioned, Paillier and Vergnaud [
426
] give evidence that Schnorr
signatures cannot be proven secure in the standard model. In this section we briefly mention
a signature scheme due to Boneh and Boyen [71, 72] that is secure in the standard model.
However, the security relies on a very different computational assumption than DLP and the
scheme needs groups with an extra feature (namely, a pairing; see Definition
22.2.14
). We
7
The generic group model assumes that any algorithm to attack the scheme is a generic algorithm for the group
G
. This seems
to be a reasonable assumption when using elliptic curves.
