Cryptography Reference
In-Depth Information
The more difficult problem is testing whether a group element
g
lies in the desired
subgroup. For example, if
r
F
q
) and we are given a group element
g
, to ensure that
g
lies in the unique subgroup of order
r
one can compute
g
r
and check if this is the
identity. Efficient exponentiation algorithms can be used, but the computational cost is still
significant. In some situations, one can more efficiently test subgroup membership. One
notable case is when #
G
(
#
G
(
F
q
) is prime; this is one reason why elliptic curves of prime order
are so convenient for cryptography.
2
m
r
where
m
is small and
r
is prime. Show how to use point halving (see Exercise
9.1.4
) to efficiently
determine whether a point
P
Exercise 11.6.1
(King) Let
E
be an elliptic curve over
F
q
such that #
E
(
F
q
)
=
∈
E
(
F
q
) has order dividing
r
.
An alternative way to prevent attacks due to elements of incorrect group order is to
“force” all group elements to lie in the required subgroup by exponentiating to a
cofactor
(such as #
G
(
F
q
)
/r
). When the cofactor is small, this can be a more efficient way to deal with
the problem than testing subgroup membership, though one must ensure the cryptographic
system can function correctly in this setting.
With algebraic group quotients represented using traces (i.e., LUC and XTR) one rep-
resents a finite field element using a trace. This value corresponds to a valid element of the
extension field only if certain conditions hold. In the case of LUC, we represent
g
∈
G
2
,p
,
where
p
is prime, by the trace
V
Tr(
g
). A value
V
corresponds to an element of
G
2
,q
if and only if the quadratic polynomial (
x
=
g
p
)
x
2
−
g
)(
x
−
=
−
Vx
+
1 is irreducible (in
other words, if (
V
2
−
4
p
)
=−
1). Similarly, in XTR one needs to check whether the poly-
nomial
x
3
tx
2
t
p
x
1 is irreducible; Lenstra and Verheul [
338
] have given efficient
algorithms to do this. Section 4 of [
338
] also discusses subgroup attacks in the context of
XTR and countermeasures in this context.
−
+
−
