Cryptography Reference
In-Depth Information
least significant bits); see Jao, Jetchev and Venkatesan [
276
] for some results. However,
Boneh and Shparlinski [
79
] had the insight to consider a more general oracle.
Definition 21.7.16
Let
p
be an odd prime and
k
∈ N
.Let
A
x,k
(
A,B,P,
[
a
]
P,
[
b
]
P
)bean
F
p
) for the elliptic curve
E
:
y
2
x
3
oracle that returns LSB
k
(
x
([
ab
]
P
)) where
P
∈
E
(
=
+
Ax
+
B
. Similarly, let
A
y,k
(
A,B,P,
[
a
]
P,
[
b
]
P
) be an oracle that returns LSB
k
(
y
([
ab
]
P
)).
F
p
) where
E
:
y
2
x
3
The crucial idea is that, given a point
P
=
(
x
P
,y
P
)
∈
E
(
=
+
(
u
2
x,u
3
y
) and
φ
(
P
)
E
(
Ax
+
B
, one can consider an isomorphism
φ
(
x,y
)
=
∈
F
p
) where
E
:
Y
2
u
6
B
. Hence, instead of randomising instances of CDH in a way
analogous to that done earlier, one calls the oracle
A
x,k
(
u
4
A,u
6
B,φ
(
P
)
,φ
([
a
]
P
)
,φ
([
b
]
P
))
to get LSB
k
(
x
(
φ
([
ab
]
P
)))
X
3
u
4
AX
=
+
+
LSB
k
(
u
2
x
([
ab
]
P
)(mod
p
)) where
u
is controlled by the
attacker. This is very similar to the easy case of the hidden number problem in
=
F
p
from
Lemma
21.7.5
.
Lemma 21.7.17
Suppose p
≡
2(mod3)
. Then
LSB
1
(
y
([
ab
]
P
))
is a hardcore bit for CDH
on elliptic curves over
F
p
.
Proof
We suppose
A
y,
1
is a perfect oracle for LSB
1
(
y
([
ab
]
P
)) as above. Calling
A
y,
1
(
u
4
A,u
6
B,φ
(
P
)
,φ
([
a
]
P
)
,φ
([
b
]
P
))
gives LSB
1
(
u
3
y
([
ab
]
P
)). Since gcd(3
,p
−
1)
=
1 it follows that cubing is a permutation
F
p
and one can perform the method of Lemma
21.7.5
to compute
y
([
ab
]
P
). Given
y
([
ab
]
P
) there are at most 3 choices for
x
([
ab
]
P
) and so CDH is solved with noticeable
probability.
of
2 (mod 3)), Boneh and Shparlinski have to work
harder. They use the method of Alexi, Chor, Goldreich and Schnorr [
9
] or the simplified
version by Fischlin and Schnorr [
186
] to extend the idea to non-perfect oracles.
12
Once
this is done, the following trick can be applied to determine LSB
1
(
tx
([
ab
]
P
)): when
t
is a
square one calls the oracle for LSB
1
(
u
2
x
([
ab
]
P
)) on
u
In the general case (i.e., when
p
≡
=
√
t
(mod
p
), and when
t
is not
a square one flips a coin. The resulting non-perfect oracle for LSB
1
therefore solves the
problem. We refer to [
79
] for the details.
We make some remarks.
1. A nice feature of the elliptic curve results is that they are independent of the order of
the point
P
and so work for subgroups of any size.
2. The literature does not seem to contain bit security results for CDH on elliptic curves
over non-prime fields. This would be a good student project.
3. Jetchev and Venkatesan [
281
] use isogenies to extend the applicability of the Boneh-
Shparlinski method. Their motivation is that if one has an LSB
1
(
x
([
ab
]
P
)) oracle that
12
This is why Boneh and Shparlinski consider least significant bits rather than most significant bits for their result. The technique
of Alexi et al is to randomise the query LSB
1
(
tα
)asLSB
1
(
sα
)
⊕
LSB
1
((
t
+
s
)
α
) for suitable values
s
. A good student project
would be to obtain an analogous result for other bits (e.g., most significant bits).
