Cryptography Reference
In-Depth Information
Corollary 21.5.12
Let g have prime order r and suppose r
+
1
has a factor d such that
g
a
and a perfect Static-DH oracle with respect to
(
g,h
)
then one can
compute a in O
(
r
1
/
3
)
oracle queries and O
(
r
1
/
3
log(
r
))
group operations.
r
1
/
3
. Given h
d
≈
=
Exercise 21.5.13
Fill in the missing details in the proof of Theorem
21.5.10
and prove
Corollaries
21.5.11
and
21.5.12
.
Satoh [
459
] extends Cheon's algorithm to algebraic groups of order
ϕ
n
(
r
) (essentially,
to the groups
G
n,r
). He also improves Theorem
21.5.10
in the case of
d
|
(
r
+
1) to only
g
a
i
for 1
require
h
i
=
d
.
A natural problem is to generalise Theorem
21.5.10
to other algebraic groups, such as
elliptic curves. The obvious approach does not seem to work (see Remark 1 of [
122
]), so
it seems a new idea is needed to achieve this. Finally, Section 5.2 of [
123
] shows that, at
least asymptotically, most primes
r
are such that
r
≤
i
≤
1 has a useful divisor.
Both [
104
] and [
122
] remark that a decryption oracle for classic textbook Elgamal
leads to a Static-DH oracle: given an Elgamal public key (
g,g
a
) and any
h
1
∈
−
1or
r
+
g
one
can ask for the decryption of the ciphertext (
c
1
,c
2
)
(
h
1
,
1) (one can also make this less
obvious using random self-reducibility of Elgamal ciphertexts) to get
c
2
c
−
a
=
h
−
1
.From
this, one computes
h
1
. By performing this repeatedly one can compute a sequence
h
i
=
=
1
g
a
i
as required. The papers [
104
,
122
] contain further examples of cryptosystems that provide
Static-DH oracles, or computational assumptions that contain values of the form
h
i
=
g
a
i
.
21.6 Hard bits of discrete logarithms
Saying that a computational problem is hard is the same as saying that it is hard to write
down a binary representation of the answer. Some bits of a representation of the answer
may be easy to compute (at least, up to a small probability of error) but if a computational
problem is hard then there must be at least one bit of any representation of the answer that
is hard to compute. In some cryptographic applications, it is important to be able to locate
some of these “hard bits”. Hence, the main challenge is to prove that a specific bit is hard.
A potentially easier problem is to determine a small set of bits, at least one of which is
hard. A harder problem is to prove that some set of bits are all simultaneously hard (for this
concept see Definition
21.6.14
).
The aim of this section is to give a rigorous definition for the concept of “hard bits” and
to give some easy examples (hard bits of the solution to the DLP). In Section
21.7
we will
consider related problems for the CDH problem. We first show that certain individual bits
of the DLP, for any group, are as hard to compute as the whole solution.
Definition 21.6.1
Let
g
∈
G
have prime order
r
. The computational problem
DL-LSB
is:
given (
g,g
a
) where 0
≤
a<r
to compute the least significant bit of
a
.
Exercise 21.6.2
Show that DL-LSB
≤
R
DLP.
Theorem 21.6.3
Let G be a group of prime order r. Then DLP
≤
R
DL-LSB.
