Cryptography Reference
In-Depth Information
and
h
s
1
g
H
(
m
)
g
s
2
.
=
Show how to determine the private key of a user given a valid signature.
F
p
Exercise 22.2.6
(Bleichenbacher [
62
]) Consider the Elgamal encryption scheme in
with the function
F
(
n
)
s
2
<r
are not
performed by the Verify algorithm. Show how an adversary who has maliciously chosen
the system parameter
g
can produce selective forgeries for any public key under a passive
attack.
=
n
(mod
r
). Suppose the checks
s
1
∈
g
and 0
≤
Exercise 22.2.7
(Vaudenay [
552
]) Let
H
be a hash function with
l
-bit output. Show
how to efficiently compute an
l
-bit prime
r
and messages
m
1
,
m
2
such that
H
(
m
1
)
≡
H
(
m
2
)(mod
r
). Hence, show that if one can arrange for an algebraic group with subgroup
of order
r
to be used as the system parameters for a signature scheme then one can obtain
a signature on
m
1
for any public key
h
by obtaining from user
A
a signature on
m
2
.
A convenient feature of Elgamal signatures is that one can verify a batch of signatures
faster than individually verifying each of them. Some details are given in Exercise
22.2.8
.
Early work on this problem was done by Naccache, M'Raıhi, Vaudenay and Raphaeli [
403
]
(in the context of DSA) and Yen and Laih [
570
]. Further discussion of the problem is given
by Bellare, Garay and Rabin [
31
].
Exercise 22.2.8
Let (
s
1
,i
,
s
2
,i
) be purported signatures on messages
m
i
with respect to
public keys
h
i
for 1
≤
i
≤
t
. A verifier can choose random integers 1
≤
w
i
<r
and verify
all signatures together by testing whether
s
1
,i
∈
g
and 0
≤
s
2
,i
<r
for all
i
and the single
equation
t
t
g
t
i
=
1
w
i
H
(
m
i
)
.
h
w
i
F
(
s
1
,i
)
i
s
w
i
s
2
,i
1
,i
=
(22.3)
i
=
1
i
=
1
Show that if all the signatures (
s
1
,i
,
s
2
,i
) are valid then the batch is declared valid. Show
that if there is at least one invalid signature in the batch then the probability the batch
is declared valid is at most 1
/
(
r
−
1). Show how to determine, with high probability, the
invalid signatures using a binary search.
If one uses the methods of Exercise
22.2.2
then verifying the
t
signatures separately
requires
t
three-dimensional multi-exponentiations. One can break equation (
22.3
)into
about 2
t/
3 three-dimensional multi-exponentiations. So, for groups where testing
s
1
,i
∈
is easy (e.g., elliptic curves of prime order), the batch is asymptotically verified in about
2
/
3 the time of verifying the signatures individually. Show how to speed up verification of
a batch of signatures further if the public keys
h
i
are all equal. How much faster is this than
verifying the signatures individually?
Yen and Laih [
570
] consider batch verification of naive Schnorr signatures as mentioned
in Section
22.1.2
.Given
t
signatures (
s
0
,i
,
s
2
,i
) on messages
m
i
and for keys
h
i
Yen and
g
