Cryptography Reference
In-Depth Information
1
u
2
, and handle the
(see Exercise
11.4.12
)from
A
to the variety
F
(
x
1
)
F
(
x
2
)
F
(
x
3
)
=
characteristic 2 and 3 cases.
x
3
Exercise
11.4.12
(Shallue
and
van
de
Woestijne
[
491
])
Let
F
(
x
)
=
+
Ax
+
B
u
2
v
2
u
2
and
H
(
u,v
)
=
+
uv
+
+
A
(
u
+
v
)
+
B
.Let
V
:
F
(
x
1
)
F
(
x
2
)
F
(
x
3
)
=
and let
S
:
y
2
H
(
u,v
)
y
2
,F
(
u
=−
F
(
u
). Show that the map
ψ
(
u,v,y
)
→
(
v,
−
A
−
u
−
v,u
+
+
y
2
)
H
(
u,v
)
/y
) is a rational map from
S
to
V
.Let
p>
3beprime.Fix
u
∈ F
p
such that
=
0 and 3
u
2
+
+
−
A
2
=
F
(
u
)
2
Au
4
B
0. Show that the surface
S
for this fixed value of
u
is
A/
2)]
2
[3
u
2
/
4
A
2
/
4]
y
2
[
y
(
v
+
u/
2
+
+
+
Au/
2
+
B
−
=−
F
(
u
)
.
1
1
Hence, show there is a rational map from
A
to
S
and hence a rational map from
A
to
V
.
1
C
when
C
is a curve
of genus at least 1. This follows from the Hurwitz genus formula: if the map has degree
d
then we have
It is worth noting that there can be no rational map
φ
:
P
→
1
)
0 where
R
is a positive integer
counting the ramification, which is a contradiction. The above maps do not contradict this
fact. They are not rational maps from
−
2
=
2
g
(
P
−
2
=
d
(2
g
(
C
)
−
2)
+
R
≥
1
) to an elliptic curve; there is always one
part of the function (such as computing a square-root or cube-root) that is not a rational
map.
Icart [
273
] has given a simpler map for elliptic curves
y
2
P
1
A
(or
x
3
=
+
Ax
+
B
over
F
q
when
q
≡
2(mod3).Let
u
∈ F
q
. Define
=
v
2
u
6
/
27
1
/
3
u
4
)
/
(6
u
)
,x
u
2
/
3
v
=
(3
A
−
−
B
−
+
and
y
=
ux
+
v
(11.4)
where
the
cube
root
is
computed
by
exponentiating
to
the
power
(2
q
−
1)
/
3
≡
3
−
1
(mod (
q
−
1)).
Exercise 11.4.13
Verify that the point (
x,y
) of equation (
11.4
) is a point on
E
:
y
2
=
x
3
+
Ax
+
B
over
F
q
. Show that, given a point (
x,y
) on an elliptic curve
E
over
F
q
as above,
one can efficiently compute
u
∈ F
q
, if it exists, such that the process of equation (
11.4
)
gives the point (
x,y
).
In most cryptographic applications, we are interested in sampling from subgroups of
E
(
F
q
) of prime order
r
. As mentioned earlier, the simplest way to transform elements
sampled randomly in
E
(
F
q
) into random elements of the subgroup is to exponentiate to the
power #
E
(
F
q
)
/r
(assuming that
r
#
E
(
F
q
)).
11.4.3 Hashing to algebraic groups
Recall that sampling from algebraic groups is the task of selecting group elements uniformly
at random. On the other hand, a hash function
H
:
l
{
0
,
1
}
→
G
(
F
q
) is a deterministic
l
and outputs a group element. It is required that the
output distribution of
H
, corresponding to the uniform distribution of the message space, is
algorithm that takes an input
m
∈{
0
,
1
}
