Cryptography Reference
In-Depth Information
as containing the additive group
,i,j,k
)
that assigns register
k
the sum of the elements in registers
i
and
j
, an oracle
O
(
Z
/r
Z
. The algorithm has access to an oracle
O
(
+
−
,i,j
)
that assigns register
j
the inverse of the element in register
i
and an oracle
O
(
,i,j
) that
returns “true” if and only if registers
i
and
j
contain the same group element. The goal of
the generic algorithm for the DLP is to output the value of the second register.
=
To implement the BSGS algorithm or Pollard rho algorithm in Maurer's model it is
necessary to allow a further oracle that computes a well-ordering relation on the group
elements.
We remark that the Shoup and Maurer models have been used to prove the security of
cryptographic protocols against adversaries that behave like generic algorithms. Jager and
Schwenk [
275
] have shown that both models are equivalent for this purpose.
13.4.3 The lower bound
We present the main result of this section using Shoup's model. A similar result can be
obtained using Maurer's model (except that it is necessary to either ignore the cost of
equality queries or else allow a total order relation on the registers).
We start with a result attributed by Shoup to Schwarz. In this section we only use the
result when
k
=
1, but the more general case is used later in the topic.
Lemma 13.4.4
Let F
(
x
1
,...,x
k
)
∈ F
r
[
x
1
,...,x
k
]
be a non-zero polynomial of total
r
the probability
degree d. Then for P
=
(
P
1
,...,P
k
)
chosen uniformly at random in
F
that F
(
P
1
,...,P
k
)
=
0
is at most d/r.
=
Proof
If
k
1 then the result is standard. We prove the result by induction on
k
. Write
F
e
(
x
1
,...,x
k
−
1
)
x
k
+
F
e
−
1
(
x
1
,...,x
k
−
1
)
x
e
−
1
F
(
x
1
,...,x
k
)
=
+···+
F
0
(
x
1
,...,x
k
−
1
)
k
where
F
i
(
x
1
,...,x
k
−
1
)
∈ F
r
[
x
1
,...,x
k
−
1
] has total degree
≤
d
−
i
for 0
≤
i
≤
e
and
k
−
1
r
e
0 then all
r
choices for
P
k
lead to a solution. The probability of this happening is at most (
d
≤
d
.If
P
=
(
P
1
,...,P
k
−
1
)
∈ F
is such that all
F
i
(
P
)
=
−
e
)
/r
(thisisthe
probability that
F
e
(
P
)
0 then there are at most
e
choices for
P
k
that give a root of the polynomial. The total probability is therefore
≤
=
0). On the other hand, if some
F
i
(
P
)
=
(
d
−
e
)
/r
+
e/r
=
d/r
.
Theorem 13.4.5
Let G be a cyclic group of prime order r. Let A be a generic algorithm
for the DLP in G that makes at most m oracle queries. Then the probability, over uniformly
chosen a
}
t
log(
r
)
, that
∈ Z
/r
Z
and uniformly chosen encoding function σ
:
G
→{
0
,
1
A
(
σ
(
g
)
,σ
(
g
a
))
a is O
(
m
2
/r
)
.
=
Proof
Instead of choosing a random encoding function in advance, the method of proof
is to create the encodings “on the fly”. The algorithm to produce the encodings is called
