Cryptography Reference
In-Depth Information
A solution for affine points on elliptic curves is to reject
P
with probability 1
/
2if
P
is
of the form (
x,
0). For a detailed analysis and generalisation of this algorithm see von zur
Gathen, Shparlinski and Sinclair [
222
].
Exercise 11.4.10
Give a randomised algorithm to sample elliptic curve points uniformly
at random. Determine the expected running time of this algorithm.
Deterministic sampling of elliptic curve points
The above methods are randomised, not just due to the randomness that naturally arises
when sampling, but also because of the use of randomised algorithms for solving quadratic
equations, and because not every
x
in the field is an
x
-coordinate of an elliptic curve point.
It is of interest to minimise the reliance on randomness, especially when using the above
ideas to construct a hash function (otherwise, there may be timing attacks). We first give
an easy example.
≡
Exercise 11.4.11
(Boneh and Franklin [
75
]) Let
p
2 (mod 3) be prime. Consider the
supersingular elliptic curve
E
:
y
2
=
x
3
+
F
p
. One can sample points uniformly
a
6
over
in
E
(
F
p
)
−{
O
E
}
by uniformly choosing
y
∈ F
p
and setting
x
=
(
y
2
−
a
6
)
1
/
3
(mod
p
).
The cube root is computed efficiently by exponentiation to the power (2
p
−
1)
/
3
≡
3
−
1
(mod
p
−
1).
The first general results on deterministic methods to find points on curves over finite
fields
k
are due to Schinzel and Skałba [
462
]. Given
a
6
∈ k
(the case char(
k
)
=
2 is not
interesting since the curve is singular, and the case char(
k
)
=
3 is easy since taking cube
roots is easy, so assume char(
2
,
3), they give a formula, in terms of
a
6
, for four values
y
1
,...,y
4
such that the equation
x
3
k
)
=
y
i
has a solution
x
+
a
6
=
∈ k
for some 1
≤
i
≤
4.
This method therefore produces at most 12 points on any given curve.
Skałba [
510
] gave results for general curves
y
2
=
=
x
3
+
+
a
6
.
This method can give more than a fixed number of points for any given curve. More
precisely, Skałba gives explicit rational functions
X
i
(
t
)
F
(
x
) where
F
(
x
)
a
4
x
∈ Q
(
t
)for1
≤
i
≤
3 such that
there is a rational function
U
(
t
)
∈ Q
(
t
) and such that
F
(
X
1
(
t
2
))
F
(
X
2
(
t
2
))
F
(
X
3
(
t
2
))
U
(
t
)
2
.
=
In other words, Skałba gives a rational map from
A
1
to the variety
F
(
x
1
)
F
(
x
2
)
F
(
x
3
)
=
u
2
.
∈ F
p
, where
p>
3 is prime, it follows that at least one of the
F
(
X
i
(
t
2
)) is a
Evaluating at
t
F
p
. One can therefore find a point on
E
by taking square roots. Note that efficient
algorithms for computing square roots modulo
p
are randomised in general. Skałba avoids
this problem by assuming that the required quadratic non-residue has been precomputed.
Shallue and van de Woestijne [
491
] improve upon Skałba's algorithm in several ways.
First, and most significantly, they show that a deterministic sampling algorithm does not
require a quadratic non-residue modulo
p
. They achieve this by cleverly using all three
values
F
(
X
1
(
t
2
))
,F
(
X
2
(
t
2
)) and
F
(
X
3
(
t
2
)). In addition, they give a simpler rational map
square in
