Cryptography Reference
In-Depth Information
then deterministically chooses one of the values
s
i
(for example, by ordering the roots as
integers
s
1
<s
2
<s
3
<s
4
and then generating an integer
i
∈{
1
,
2
,
3
,
4
}
using a pseudoran-
(
e,f,
(
ef
)
−
1
s
i
(mod
N
)).
It is crucially important that, if one signs the same message twice, then the same signature
is output. To verify a signature
s
dom number generator on input
m
). The signature is the triple
s
=
=
(
e,f,s
) for public key
N
and message
m
one computes
H
(
m
) and then checks that
ef s
2
≡
H
(
m
)(mod
N
).
Exercise 24.6.4
Show that if a signer outputs two signatures (
e
1
,f
1
,s
1
) and (
e
2
,f
2
,s
2
)for
the same message
m
such that
s
1
≡±
s
2
(mod
N
) then one can factor the modulus.
Exercise 24.6.5
Show that it is not necessary to compute the Jacobi symbol (
H
(
m
N
)
when generating Rabin-Williams signatures as above. Instead, one can compute
H
(
m
)
(
p
+
1)
/
4
(mod
p
) and
H
(
m
)
(
q
+
1)
/
4
(mod
q
) as is needed to compute the
s
i
and determine
e
and
f
with only a little additional computation.
Theorem 24.6.6
The Rabin-Williams signature scheme sketched above has UF-CMA
security in the random oracle model (i.e., if H is replaced by a random oracle) if factoring
Williams integers is hard and if the pseudorandom generator is indistinguishable from a
random function.
Proof
(Sketch) Let
A
be a perfect adversary against the Rabin-Williams signature scheme
and let
N
be a Williams integer to be factored. The simulator runs the adversary
A
on
N
.
The simulator must handle the queries made by
A
to the random oracle. To do this it
maintains a list of hash values, which is initially empty. When
A
queries
H
on
m
,the
simulator first checks whether
m
appears on the list of hash values, and, if it does, responds
with the same value as previously. If
H
has not been previously queried on
m
, the simulator
chooses random
s
)
∗
,
e
ef s
2
∈
(
Z
/N
Z
∈{−
1
,
1
}
,
f
∈{
1
,
2
}
and computes
h
=
(mod
N
).
h<
2
κ
then return
h
and store (
m
,e,f,s,h
) in the list. If
h
is too big then repeat
with a different choice for (
s,e,f
). Since
N<
2
κ
+
O
(log(
κ
))
the expected number of trials is
polynomial in log(
N
).
When
A
makes a signature query on
m
, the simulator first queries
H
(
m
) and gets the
values (
e,f,s
) from the hash list such that
H
(
m
)
If 0
≤
ef s
2
(mod
N
). The simulator can
therefore answer with (
e,f,s
), which is a valid signature. (It is necessary to show that the
values (
e,f,s
) output in this way are indistinguishable from the values output in the real
cryptosystem, and this requires that the pseudorandom choice of
s
from among the four
possible roots be computationally indistinguishable from random.)
Finally,
A
outputs a signature (
e
∗
,f
∗
,s
∗
) on a message
m
∗
. Recalling the values (
e,f,s
)
from the construction of
H
(
m
∗
)wehave
e
∗
=
≡
e
,
f
∗
=
f
and (
s
∗
)
2
s
2
≡
(mod
N
). With
probability 1
/
2 we can factor
N
as gcd(
N,s
∗
−
s
). We refer to Section 6 of Bernstein [
44
]
for the full details.
Exercise 24.6.7
Show that if one can find a collision for the hash function
H
in Bernstein's
variant of Rabin-Williams signatures and one has access to a signing oracle then one can
factor
N
with probability 1
/
2.
