Cryptography Reference
In-Depth Information
Similarly, one can compute signatures for all the messages
m
i
. Hence, the simulator provides
to
A
the public key (
g
1
,g
2
,h,z
=
e
(
g
1
,g
2
)) and all
t
signatures.
Eventually,
A
outputs a forgery (
m
,
s
) such that
m
1
and
q
is polynomial in the security parameter then
m
is one of the dummy messages with
negligible probability (
q
=
m
i
for 1
≤
i
≤
t
.If
t<q
−
−
1
−
t
)
/r
. One has
g
(
m
+
a
)
−
1
g
F
(
a
)(
m
+
a
)
−
1
(mod
r
)
(mod
r
)
=
=
.
s
1
1
The final trick is to note that the polynomial
F
(
a
) can be written as
G
(
a
)(
a
+
m
)
+
c
for
)
∗
. Hence, the rational
some explicitly computable values
G
(
a
)
∈
(
Z
/r
Z
)[
a
] and
c
∈
(
Z
/r
Z
function
F
(
a
)
/
(
a
+
m
) can be written as
F
(
a
)
a
c
m
=
G
(
a
)
+
m
.
+
a
+
One can therefore deduce
g
(
a
+
m
)
−
1
(mod
r
)
as required.
1
A fully secure signature scheme is given in [
71
] and it requires an extra element in the
public key and an extra element (of
) in the signature. The security proof is rather
more complicated, but the essential idea is the same.
Jao and Yoshida [
280
] showed the converse result, namely that if one can solve
q
-SDH
then one can forge signatures for the Boneh-Boyen scheme. It follows that one can use the
algorithms of Section
21.5
to forge signatures, though this is not a serious problem since
those algorithms require exponential time.
Z
/r
Z
22.3 Lattice attacks on signatures
As mentioned earlier, there is a possibility that signatures could leak information about the
private key. Indeed, Nguyen and Regev [
410
] give such an attack on lattice-based signatures.
The aim of this section is to present an attack due to Howgrave-Graham and Smart [
270
].
They determine the private key when given some signatures and given some bits of the
random values
k
(for example, due to a side-channel attack or a weak pseudorandom number
generator). The analysis of their attack was improved by Nguyen and Shparlinski [
411
,
412
]
(also see Chapter 16 of [
499
]).
The attack works for any signature scheme where one can obtain from a valid signature a
linear equation modulo
r
with two unknowns, namely the private key
a
and the randomness
k
. We now clarify that this attack applies to the
s
2
value for the Schnorr, Elgamal and DSA
signature schemes:
Schnorr:
s
2
≡
k
+
a
s
1
(mod
r
) where
s
1
,
s
2
are known.
Elgamal:
k
s
2
≡
H
(
m
)
−
aF
(
s
1
)(mod
r
) where
H
(
m
)
,F
(
s
1
) and
s
2
are known.
DSA:
k
s
2
≡
H
(
m
)
+
a
s
1
(mod
r
) where
H
(
m
)
,
s
1
and
s
2
are known.
Suppose we are given a message
m
and a valid signature (
s
1
,
s
2
) and also the
l
most
or least significant bits of the random value
k
used by the Sign algorithm to generate
s
1
.
