Cryptography Reference
In-Depth Information
Definition 21.6.7
For all
n
G
n
is an element of order
r
n
where
r
n
is an
n
-bit prime. We call this a
family of groups
.For
n
∈ N
let (
G
n
,g
n
,r
n
) be such that
G
n
is a group and
g
n
∈
g
n
.For
n
∈ N
define the function
f
n
:
{
0
,
1
,...,r
n
−
1
}→
G
n
by
f
n
(
a
)
=
∈ N
define
i
(
n
)
is defined so that
b
i
(
n
)
(
a
)isbit
i
(
n
)of
a
, when
a
is represented as an
n
-bit string. Then
b
i
(
n
)
is a
hardcore
predicate for the DLP
(alternatively, bit
i
(
n
)isa
hardcore bit for the DLP
) if, for all
probabilistic polynomial-time algorithms
A
, the advantage
Adv
a
∈{
0
,
1
,...,r
n
−
1
}
A
(
f
n
(
a
))
∈{
0
,
1
,...,n
−
1
}
. The predicate
b
i
(
n
)
:
{
0
,
1
,...,r
n
−
1
}→{
0
,
1
}
b
i
(
n
)
(
a
)
=
is negligible as a function of
n
.
0 in the above definition. If the DLP is
hard then Theorem
21.6.3
shows that the LSB is a hardcore bit.
The least significant bit (LSB) is the case
i
(
n
)
=
.Let
g
have prime order
r>
2
m
. Suppose
A
is a perfect oracle
Example 21.6.8
Fix
m
∈ N
,
A
(
g
x
) is the predicate
b
m
(
x
) (i.e., bit
m
of
x
). One can
use
A
to solve the DLP by guessing the
m
such that, for
x
∈{
0
,
1
,...,r
−
1
}
1LSBsof
x
and then using essentially the
same argument as Theorem
21.6.3
. Hence, if
m
is fixed and
g
varies in a family of groups
as in Example
21.6.7
then
b
m
(
x
) is a hardcore predicate for the DLP. A similar result holds
if
m
is allowed to grow, but is bounded as
m
−
=
O
(log(log(
r
))).
We now give an example of a hardcore predicate that is not just a bit of the DLP.
g
x
.
Exercise 21.6.9
Let
g
have prime order
r
.Let
f
:
{
0
,
1
,...,r
−
1
}→
G
be
f
(
x
)
=
Define the predicate
b
:
x
0
where
x
0
and
x
1
are
the two least significant bits of
x
. Show that
b
is a hardcore predicate for
f
.
{
0
,
1
,...,r
−
1
}→{
0
,
1
}
by
b
(
x
)
=
x
1
⊕
It is not true that any bit of the DLP is necessarily hardcore. For example, one can
consider the most significant bit of
a
, which is
b
n
−
1
(
x
) in Definition
21.6.7
.
2
l
u
be a prime where 0
<u<
2
l
−
κ
.Let0
Example 21.6.10
Let
r
=
+
≤
a<r
be chosen
uniformly at random and interpreted as an (
l
1)-bit string. Then the most significant bit
of
a
is equal to 1 with probability
u/r < u/
2
l
<
1
/
2
κ
and is equal to 0 with probability
at least 1
+
1
/
2
κ
. Hence, when
κ
1 then the most significant bit is not a hardcore bit
for the DLP. Note that the function
g
a
is not used here; the result merely follows from the
distribution of integers modulo
r
.
−
≤
2
l
2
l
−
1
u
where 0
<u<
2
l/
2
.Let0
Exercise 21.6.11
Let
r
=
+
+
≤
a<r
be uniformly
chosen and represented as an (
l
+
1)-bit string. Show that neither the most significant bit
(i.e., bit
l
) nor bit
l
−
1of
a
are hardcore for the DLP.
The above examples show that for some primes the most significant bit is easy to predict.
For other primes the most significant bit can be hard.
