Cryptography Reference
In-Depth Information
cryptographic functionalities, other times the aim is to generate hard instances of the DLP
more quickly than previous methods.
Definition 13.5.1
Let
G
be a finitely generated Abelian group. The
multi-dimensional
discrete logarithm problem
or
representation problem
4
is: given
g
1
,g
2
,...,g
l
,h
∈
G
and
S
1
,
S
2
,...,
S
l
⊆ Z
to find
a
j
∈
S
j
for 1
≤
j
≤
l
, if they exist, such that
g
a
1
g
a
2
···
g
a
l
.
h
=
The
product discrete logarithm problem
5
is: given
g,h
∈
G
and
S
1
,
S
2
,...,
S
l
⊆ Z
to find
a
j
∈
S
j
for 1
≤
j
≤
l
, if they exist, such that
g
a
1
a
2
···
a
l
.
h
=
Remark 13.5.2
A natural variant of the product DLP is to compute only the product
a
1
a
2
···
a
l
rather than the
l
-tuple (
a
1
,...,a
l
). This is just the DLP with respect to a specific
instance generator (see the discussion in Section
2.1.2
). Precisely, consider an instance
generator that, on input of a security parameter
κ
, outputs a group element
g
of prime order
r
and then chooses
a
j
∈
S
j
for 1
g
a
1
a
2
···
a
l
. The stated variant of
the product DLP is the DLP with respect to this instance generator.
≤
j
≤
l
and computes
h
=
g
1
,...,g
l
is cyclic. The solution to Exercise
13.5.4
applies in all cases. However, there may be
other ways to tackle the non-cyclic case (e.g., exploiting efficiently computable group
homomorphisms, see [
214
] for example), so the main interest is the case when
G
is cyclic
of prime order
r
.
Note that the representation problem can be defined whether or not
G
=
Example 13.5.3
The representation problem can arise when using the GLV method (see
Section
11.3.3
) with intentionally small coefficients. In this case,
g
2
=
ψ
(
g
1
),
g
1
,g
2
is a
≤
√
r
).
g
a
1
g
a
2
cyclic group of order
r
, and
h
=
where 0
≤
a
1
,a
2
<w
2
The number of possible choices for
h
in both the representation problem and product
DLP is at most
l
j
=
1
#
S
j
(it could be smaller if the same
h
can arise from many different
combinations of (
a
1
,...,a
l
)). If
l
is even and #
S
j
=
S
1
for all
j
then there is an easy
#
l/
2
1
S
time/memory tradeoff algorithm requiring
O
(#
) group operations.
Exercise 13.5.4
Write down an efficient BSGS algorithm to solve the representation
problem. What is the running time and storage requirement?
Exercise 13.5.5
Give an efficient BSGS algorithm to solve the product DLP. What is the
running time and storage requirement?
4
This computational problem seems to be first explicitly stated in the work of Brands [
92
] in the case
S
i
= Z
.
5
The idea of using product exponents for improved efficiency appears in Knuth [
308
] where it is called the “factor method”.
