Cryptography Reference
In-Depth Information
close to uniform in the group
G
(
F
q
). The basic idea is to use
m
as the randomness required
by the sampling algorithm.
Recall that a hash function is also usually required to satisfy some security requirements
such as collision resistance. This is usually achieved by first applying a collision resistant
hash function
H
:
H
(
m
). In this section we are only
concerned with the problem of using
m
as input to a sampling algorithm.
The first case to consider is hashing to
l
l
and setting
m
=
{
0
,
1
}
→{
0
,
1
}
F
p
.If
p>
2
l
+
1 then we are in trouble since
one cannot get uniform coverage of a set of size
p
−
1 using fewer than
p
−
1 elements.
This shows that we always need
l>
log
2
(#
G
(
F
q
)) (though, in some applications, it might
be possible to still have a useful cryptographic system even when the image of the hash
function is a subset of the group).
Example 11.4.14
Suppose 2
l
>p
and
m
∈{
0
,
1
}
l
. The method of Example
11.4.2
gives
output close to uniform (at least, if
l
−
log
2
(
p
) is reasonably large).
p
n
<
2
l
. Give a hash function
H
:
l
Exercise 11.4.15
Let
q
=
{
0
,
1
}
→ F
q
.
It is relatively straightforward to turn the algorithms of Example
11.4.8
and Exer-
cise
11.4.9
into hash functions. In the elliptic curve case, there is a growing literature on
transforming a sampling algorithm into a hash function. We do not give the details.
11.4.4 Hashing from algebraic groups
In some applications, it is also necessary to have a hash function
H
:
G
(
l
where
G
is an algebraic group. Motivation for this problem is given in the discussion
of key derivation functions in Section
20.2.3
. A framework for problems of this type is
randomness extraction
. It is beyond the scope of this topic to give a presentation of this
topic, but some related results are given in Sections
21.7
and
21.6
.
F
q
)
→{
0
,
1
}
11.5 Determining group structure and computing generators for elliptic curves
F
q
is cyclic, it follows that all subgroups of finite fields and tori are cyclic. However,
elliptic curves and divisor class groups of hyperelliptic curves can be non-cyclic. Deter-
mining the group structure and a set of generators for an algebraic group
G
(
Since
F
q
) can be
necessary for some applications. It is important to remark that solutions to these problems
are not expected to exist if the order
N
=
#
G
(
F
q
) is not known or if the factorisation of
N
is not known.
Let
E
be an elliptic curve over
F
q
and let
N
=
#
E
(
F
q
). If
N
has no square factors then
.If
r
2
N
then there could be a point of order
r
2
E
(
F
q
) is isomorphic as a group to
Z
/N
Z
F
q
) has a non-cyclic subgroup of order
r
2
or two “independent” points of order
r
(i.e.,
E
(
but exponent
r
).
The Weil pairing (see Section
26.2
) can be used to determine the group structure of
an elliptic curve. Let
r
be a prime and
P,Q
∈
E
(
F
q
)oforder
r
. The key fact is that the
