Cryptography Reference
In-Depth Information
Exercise 11.4.7
Let
G
be a finite Abelian group. Let
g
1
,...,g
k
be fixed elements that
generate
G
.Let
m
1
,...,m
k
be the orders of
g
1
,...,g
k
respectively. Then one can generate
an element of
G
at random by choosing integers
a
1
,...,a
k
uniformly at random such that
0
≤
a
i
<m
i
for 1
≤
i
≤
k
and computing
k
g
a
i
.
(11.2)
i
=
1
Show that this process does sample from
G
with uniform distribution.
11.4.1 Sampling from tori
F
q
.
We now mention further techniques to speed up sampling from subgroups of
F
q
) and
G
2
,q
⊆ F
q
2
are in one-to-one corrre-
Example 11.4.8
Lemma
6.3.4
shows that
T
2
(
spondence with the set
{
1
}∪{
(
a
+
θ
)
/
(
a
+
θ
):
a
∈ F
q
}
.
T
2
(
F
q
)or
G
2
,q
as fol
lo
ws: choose uniformly 0
≤
≤
Hence, one can sample from
a
p
and,
=
+
+
if
a
p
, output 1, otherwise output (
a
θ
)
/
(
a
θ
).
F
q
)or
G
6
,q
uniformly at random is less simple since the
compression map does not map to the whole of
Generating elements of
T
6
(
2
(
F
q
). Indeed, the group
G
6
,q
has
q
2
A
−
1
<q
2
q
+
elements. Example
6.4.4
showed, in the case
q
≡
2
,
5 (mod 9), how to map
2
(
F
q
):
a
2
b
2
A
={
(
a,b
)
∈ A
−
ab
+
=
1
}
(11.3)
to a subset of
T
6
(
F
q
).
Exercise 11.4.9
Let
q
2
,
5 (mod 9). Give an algorithm to generate points in the set
A
of equation (
11.3
) uniformly at random. Hence, show how to efficiently choose random
elements of a large subset of
≡
T
6
(
F
q
)or
G
6
,q
uniformly at random.
11.4.2 Sampling from elliptic curves
Let
E
:
y
2
=
x
3
+
a
4
x
+
a
6
be an elliptic curve over
F
q
where
q
is not a power of 2. To
generate points in
E
(
F
q
) one can proceed as follows: choose a random
x
∈ F
q
, test whether
x
3
+
a
4
x
+
a
6
is a square in
F
q
, if not then repeat, otherwise take square roots to get
y
and output (uniformly) one of
y
. It is not surprising that an algorithm to generate random
points is randomised, but something that did not arise previously is that this algorithm uses
a randomised subroutine (i.e., to compute square roots efficiently) and may need to be
repeated several times before it succeeds (i.e., it is a Las Vegas algorithm). Hence, only an
expected run time for the algorithm can be determined.
A more serious problem is that the output is not uniform. For example,
±
O
E
is never
output, and points (
x,
0) occur with probability twice the probability of (
x,y
) with
y
=
0.
