Cryptography Reference
In-Depth Information
t<
2
k
be the integer such that
For
k
∈ N
let 0
≤
tp/
2
k
1)
p/
2
k
≤
x<
(
t
+
and define MSB
k
(
x
)
t
.
An alternative definition, which is commonly used in the literature and sometimes used in
this topic, is MSB
k
(
x
)
=
<p/
2
k
+
1
(e.g.,
u
tp/
2
k
p/
2
k
+
1
=
u
∈ Z
such that
|
x
−
u
|
=
+
).
For this definition it is unnecessary to assume
k
∈ N
and so one can allow
k
∈ R
>
0
.
Note that these are not bits of the binary representation of
x
. Instead, as in Exer-
cise
21.6.13
, they correspond to membership of
x
in a certain partition of
.
Ideally we would like to show that, say, MSB
1
is a hardcore bit for CDH. This seems to
be out of reach for
{
1
,
2
,...,p
−
1
}
≈
log
2
(
r
), if one can compute
MSB
k
(
g
ab
(mod
p
)) then one can compute
g
ab
(mod
p
). A consequence of this result is
that there exists some predicate defined on MSB
k
(
g
ab
(mod
p
)) whose value is a hardcore
bit for CDH.
The central idea of most results on the bit security of CDH is the following. Let
p
be
an odd prime and let
g
F
p
. Instead, we will show that, for
k
∈ F
p
be a primitive root. Let
h
1
=
g
a
,h
2
=
g
b
be a CDH instance
where
b
is coprime to
p
−
1. For
k
∈ N
let
A
k
be a perfect oracle such that
A
k
(
g,g
a
,g
b
)
MSB
k
(
g
ab
)
.
=
A
k
(
g,h
1
g
x
,h
2
). One has
Choose a random element 1
≤
x<p
and set
u
=
MSB
k
(
g
(
a
+
x
)
b
)
MSB
k
(
g
ab
t
)
h
2
.
u
=
=
where
t
=
In other words, the oracle
A
k
gives the most significant bits of multiples of the unknown
g
ab
by uniformly random elements
t
∈ F
p
. The problem of using this information to compute
g
ab
is (a special case of) the hidden number problem.
21.7.1 The hidden number problem
∈ F
p
and let
t
1
,...,t
n
∈ F
p
be chosen uniformly at random. The
hidden number problem
(
HNP
)isgiven(
t
i
,u
i
=
MSB
k
(
αt
i
(mod
p
))) for 1
Definition 21.7.2
Let
p
be an odd prime and
k
∈ R
>
1
.Let
α
≤
i
≤
n
to compute
α
.
Throughout this section we will allow any
k
∈ R
>
1
and define MSB
k
(
x
) to be any integer
<p/
2
k
+
1
.
Before giving the main results we discuss two easy variants of Definition
21.7.2
where
the values
t
i
can be chosen adaptively.
u
such that
|
x
−
u
|
≤
Lemma 21.7.3
Let p be an odd prime and
1
α<p. Suppose one has a perfect oracle
=
A
1
such that A
1
(
t
)
MSB
1
(
αt
(mod
p
))
. Then one can compute α using O
(log(
p
))
oracle
queries.
Exercise 21.7.4
Prove Lemma
21.7.3
.
