Cryptography Reference
In-Depth Information
11
Basic algorithms for algebraic groups
In Section
4.1
a number of basic computational tasks for an algebraic group
G
were listed.
Some of these topics have been discussed already, especially providing efficient group
operations and compact representations for group elements. But some other topics (such
as efficient exponentiation, generating random elements in
G
and hashing from or into
G
)
require further attention. The goal of this chapter is to briefly give some details about these
tasks for the algebraic groups of most interest in the topic.
The main goal of the chapter is to discuss exponentiation and multi-exponentiation.
These operations are crucial for efficient discrete logarithm cryptography and there are a
number of techniques available for specific groups that give performance improvements.
It is beyond the scope of this topic to present a recipe for the best possible exponentiation
algorithm in a specific application. Instead, our focus is on explaining the mathematical
ideas that are used. For an “implementors guide” in the case of elliptic curves we refer to
Bernstein and Lange [
51
].
Let
G
be a group (written in multiplicative notation). Given
g
we wish
to compute
g
a
. We assume in this chapter that
a
is a randomly chosen integer of size
approximately the same as the order of
g
, and so
a
varies between executions of the
exponentiation algorithm. If
g
does not change between executions of the algorithm then
we call it a
fixed base
and otherwise it is a
variable base
.
As mentioned in Section
2.8
, there is a significant difference between the cases where
g
is fixed (and one is computing
g
a
repeatedly for different values of
a
) and the case where
both
g
and
a
vary. Section
2.8
already briefly mentioned addition chains and sliding window
methods. The literature on addition chains is enormous and we do not delve further into
this topic. Window methods date back to Brauer in 1939 and sliding windows to Thurber;
we refer to Bernstein's excellent survey [
41
] for historical details. Other references for fast
exponentiation are Chapters 9 and 15 of [
16
], Chapter 3 of [
248
] and Sections 14.6 and
14.7 of [
376
].
∈
G
and
a
∈ N
11.1 Efficient exponentiation using signed exponents
In certain algebraic groups, computing the inverse of a group element is much more efficient
than a general group operation. For example, Exercise
6.3.1
and Lemma
6.3.12
show that
inversion in
G
q,
2
and
T
2
(
F
q
) is easy. Similarly, inversion in elliptic and hyperelliptic curve
