Cryptography Reference
In-Depth Information
1 so that Alice and Bob share the key 2
x
. Prove that MSB
1
(2
x
) is a hardcore
1
≤
x<p
−
bit.
[Hint: Suppose one has a perfect oracle
A
that on input
g
y
outputs MSB
1
(2
y
). Then one
can store Bob's transmission
g
x
and call
A
(
g
x
g
y
) to get
α
2
y
, where
α
2
x
is the desired
=
hidden number. Then apply Lemma
21.7.3
.]
∈ F
p
be a primitive root and let
>
0. Show that if one has a
perfect oracle for MSB
1
+
(
g
ab
) then one can solve DDH in
Exercise 21.7.13
Let
g
F
p
.
21.7.3 Hard bits for CDH in other groups
F
p
where
p
is prime. It is natural
So far we have only considered CDH in (subgroups of)
F
p
m
, in algebraic tori, in trace systems such as LUC and
XTR and in elliptic curves. The first issue is what is meant by “bits” of such a value. In
practice, elements in such a group are represented as an
n
-tuple of elements in
to consider CDH in subgroups of
F
p
and so
F
p
and take bits of it as done previously. When
p
is small, one can consider a sequence of bits, each from different components. An early
reference for bit security of CDH in this setting is Verheul [
555
].
It is possible to extend the results to traces relatively easily. The idea is that if
it is natural to consider one component in
{
θ
1
,...,θ
m
}
=
j
=
1
α
j
θ
j
is hidden and if
t
i
=
j
=
1
t
i,j
θ
j
are known
then Tr(
αt
i
) is a linear equation in the unknown
α
i
.Li,Naslund and Shparlinski [
349
]
have studied the bit security of CDH in LUC and XTR. We refer to Chapters 6 and 19 of
Shparlinski [
499
] for further details and references.
is a basis for
F
p
m
over
F
p
,if
α
∈ F
2
m
. Suppose
one has a perfect oracle
A
such that
A
(
g,g
a
,g
b
) returns the first coefficient of the normal
basis representation of
g
ab
. Show how to use
A
to compute
g
ab
. Hence, conclude that the
first coefficient is a hardcore bit for CDH in
F
2
m
be represented using a normal basis and let
g
Exercise 21.7.14
Let
F
2
m
.
∈ F
2
m
have prime order
r>m
. Sup-
pose one has a perfect oracle
A
such that
A
(
g,g
a
,g
b
) returns the constant coefficient of
the polynomial basis representation of
g
ab
. Show how to use
A
to compute
g
ab
. Hence,
conclude that the constant coefficient is a hardcore bit for CDH in
Exercise 21.7.15
Let
F
2
m
= F
2
[
x
]
/
(
F
(
x
)) and let
g
F
2
m
.
Hard bits for elliptic curve Diffie-Hellman
We now consider the case of elliptic curves
E
over
F
q
. A typical way to extract bits from
an elliptic curve point
P
is to consider the
x
-coordinate
x
(
P
) as an element of
F
q
and then
extract bits of this. It seems hard to give results for the bit security of CDH using an oracle
A
(
P,
[
a
]
P,
[
b
]
P
)
=
MSB
k
(
x
([
ab
]
P
)); the natural generalisation of the previous approach
is to call
A
(
P,
[
a
]
P
[
zb
]
P
)) but the problem is that it
is difficult to infer anything useful about
x
([
ab
]
P
)from
x
([
ab
]
P
+
[
z
]
P,
[
b
]
P
)
=
MSB
k
(
x
([
ab
]
P
+
+
[
zb
]
P
) (similarly, for
