Cryptography Reference
In-Depth Information
21.2 Lower bound on the complexity of CDH for generic algorithms
We have seen (Theorem
13.4.5
) that a generic algorithm requires
(
√
r
) group operations
to solve the DLP in a group of order
r
. Shoup proved an analogue of this result for CDH.
As before, fix
t
∈ R
>
0
and assume that all group elements are represented by bitstrings of
length at most
t
log(
r
).
Theorem 21.2.1
Let G be a cyclic group of prime order r. Let A be a generic algo-
rithm for CDH in G that makes at most m oracle queries. Then the probability that
A
(
σ
(
g
)
,σ
(
g
a
)
,σ
(
g
b
))
σ
(
g
ab
)
over a,b
=
∈ Z
/r
Z
and an encoding function σ
:
G
→
}
t
log(
r
)
chosen uniformly at random is O
(
m
2
/r
)
.
S
⊆{
0
,
1
}
t
log(
r
)
.
The simulator begins by uniformly choosing three distinct
σ
1
,σ
2
,σ
3
in
S
and running
A
(
σ
1
,σ
2
,σ
3
). The encoding function is then specifed at the two points
σ
1
=
Proof
The proof is almost identical to the proof of Theorem
13.4.5
.Let
S
={
0
,
1
σ
(
g
) and
σ
2
=
σ
(
h
). From the point of view of
A
,
g
and
h
are independent distinct elements of
G
.
It is necessary to ensure that the encodings are consistent with the group operations.
This cannot be done perfectly without knowledge of
a
and
b
, but using polynomials as
previously ensures there are no “trivial” inconsistencies. The simulator maintains a list of
pairs (
σ
i
,F
i
) where
σ
i
∈
S
and
F
i
∈ F
r
[
x,y
] (indeed, the
F
i
(
x,y
) will always be linear).
The initial values are (
σ
1
,
1), (
σ
2
,x
) and (
σ
3
,y
). Whenever
A
makes an oracle query on
(
σ
i
,σ
j
) the simulator computes
F
F
j
.If
F
appears as
F
k
in the list of pairs then
the simulator replies with
σ
k
and does not change the list. Otherwise, an element
σ
=
F
i
−
S
,
distinct from the previously used values, is chosen uniformly at random, (
σ,F
) is added to
the simulator's list and
σ
is returned to
A
.
After making at most
m
oracle queries,
A
outputs
σ
4
∈ Z
∈
/r
Z
. The simulator now chooses
σ
(
g
ab
). Note that if
σ
4
is
not equal to
σ
1
,σ
2
or one of the strings output by the oracle then the probability of success
is at most 1
/
(2
t
log(
r
)
−
a
and
b
uniformly at random in
Z
/r
Z
. Algorithm
A
wins if
σ
4
=
2). Hence, we assume that
σ
4
is on the simulator's list.
Let the simulator's list contain precisely
k
polynomials
m
−
{
F
1
(
x,y
)
,...,F
k
(
x,y
)
}
for
some
k
≤
m
+
3. Let
E
be the event that
F
i
(
a,b
)
=
F
j
(
a,b
) for some pair 1
≤
i<j
≤
k
or
F
i
(
a,b
)
=
ab
. The probability that
A
wins is
Pr(
A
wins
|
E
)Pr(
E
)
+
Pr(
A
wins
|¬
E
)Pr(
¬
E
)
.
(21.1)
For
each
pair
1
≤
i<j
≤
k
the
probability
that
(
F
i
−
F
j
)(
a,b
)
=
0is1
/r
by
Lemma
13.4.4
. Similarly, the probability that
F
i
(
a,b
)
−
ab
=
0is2
/r
. Hence, the proba-
O
(
m
2
/r
). On the other hand, if event
E
does not occur then all
A
“knows” about (
a,b
) is that it lies in the set
bility of event
E
is at most
k
(
k
+
1)
/
2
r
+
2
k/r
=
)
2
X
={
(
a,b
)
∈
(
Z
/r
Z
:
F
i
(
a,b
)
=
F
j
(
a,b
) and
F
i
(
a,b
)
=
ab
for all 1
≤
i<j
≤
k
}
.
r
2
m
2
/
2 Then Pr(
N/r
2
and Pr(
A
wins
Let
N
=
#
X
≈
−
¬
E
)
=
|¬
E
)
=
1
/N
.
Hence, the probability that
A
wins is
O
(
m
2
/r
).
