Cryptography Reference
In-Depth Information
Definition 22.2.17
Let
q
∈ N
(not necessarily prime). Let
G
1
,G
2
,G
T
be pairing groups as
in Definition
22.2.14
.Let
g
1
∈
G
1
−{
1
}
and
g
2
∈
G
2
−{
1
}
.The
q
-strong Diffie-Hellman
problem
(
q
-
SDH
)is,given(
g
1
,g
2
,g
2
,g
a
2
2
,...,g
a
q
2
), where 1
≤
a<r
is chosen uniformly
at random, to output a pair
m
,g
(
m
+
a
)
−
1
(mod
r
)
1
≤
where 0
m
<r
.
This problem may look rather strange at first sight since the value
q
can vary. The problem
is mainly of interest when
q
is polynomial in the security parameter (otherwise, reading
the problem description is not polynomial-time). Problems (or assumptions) like this are
sometimes called parameterised since there is a parameter (in this case
q
) that determines
the size for a problem instance. Such problems are increasingly used in cryptography,
though many researchers would prefer to have systems whose security relies on more
familiar assumptions.
There is evidence that the computational problem is hard. Theorem 5.1 of
Bon
eh and
Boyen [
71
] shows that a generic algorithm for
q
-SDH needs to make
(
√
r/q
) group
operations to have a good chance of success. The algorithms of S
e
ction
21.5
can be used
to solve
q
-SDH. In particular, if
q
1) (and assu
ming
q<
√
r
) then Theorem
21.5.1
gives an algorithm to compute
a
with complexity
O
(
√
r/q
) group operations, which meets
the lower bound for generic algorithms.
|
(
r
−
Exercise 22.2.18
Show that one can use
ψ
and
e
to verify that the input to an instance of
the
q
-SDH is correctly formed. Similarly, show how to use
e
to verify that a solution to a
q
-SDH instance is correct.
Theorem 22.2.19
If the q-SDH problem is hard then the weak Boneh-Boyen signature
scheme is secure under a weak chosen-message attack, where the adversary requests at
most q
−
1
signatures.
Proof
(Sketch) Let (
g
1
,g
2
,g
2
,g
a
2
2
,...,g
a
q
2
)bea
q
-SDH instance and let
A
be an adversary
against the scheme. Suppose
A
outputs messages
m
1
,...,
m
t
with
t<q
.
Without loss of generality
t
1 (since one can just add dummy messages). The
idea of the proof is to choose a public key so that one knows
g
(
m
i
+
a
)
−
1
1
=
q
−
for all 1
≤
i
≤
t
.
The natural way to do this would be to set
g
t
i
=
1
(
m
i
+
a
)
1
g
1
=
=
t
i
=
1
(
m
i
+
but the problem is that we do not know
a
. The trick is to note that
F
(
a
)
a
)
=
t
i
=
0
F
i
a
i
is a polynomial in
a
with explicitly computable coefficients in
Z
/r
Z
. One can
g
F
(
a
)
2
g
aF
(
a
)
2
therefore compute
g
2
=
,
g
1
=
ψ
(
g
2
) and
h
=
using, for example
t
g
a
i
F
i
.
g
2
=
i
=
0
