Cryptography Reference
In-Depth Information
4
Preliminary remarks on algebraic groups
For efficient public key cryptography based on discrete logarithms one would like to have
groups for which computing g n is as fast as possible, the representation of group elements
is as small as possible and for which the DLP (see Definition 2.1.1 or 13.0.1 ) is (at least
conjecturally) as hard as possible.
If g is a group element of order r then one needs at least log 2 ( r ) bits to represent
an arbitrary element of
. This optimal size can be achieved by using the exponent
representation , i.e. represent g a as a
g
∈ Z
/r
Z
. However, the DLP is not hard when this
representation is used.
Ideally, for any cyclic group G of order r , one would like to be able to represent arbitrary
group elements (in a manner which does not then render the DLP trivial) using roughly
log 2 ( r ) bits. This can be done in some cases (e.g., elliptic curves over finite fields with
a prime number of points), but it is unlikely that it can always be done. Using algebraic
groups over finite fields is a good way to achieve these conflicting objectives.
4.1 Informal definition of an algebraic group
The subject of algebraic groups is large and has an extensive literature. Instead of presenting
the full theory, in this topic we present only the algebraic groups that are currently believed
to be useful in public key cryptography. Informally, 1
an algebraic group over a field
k
is
a group such that:
Group elements are specified as n -tuples of elements in a field
k
.
The group operations (multiplication and inversion) can be performed using only poly-
nomial equations (or ratios of polynomials) defined over
k
. In other words, we have
n . There is not nec-
essarily a single n -tuple of polynomial equations that defines mult for all possible pairs
of group elements.
2 n
n and inverse :
n
polynomial or rational maps mult :
k
→ k
k
→ k
An algebraic group quotient is the set of equivalence classes of an algebraic group
under some equivalence relation (see Section 4.3 for an example). Note that, in general, an
algebraic group quotient is not a group.
1
We refrain from giving a formal definition of algebraic groups; mainly as it requires defining products of projective varieties.
Search WWH ::




Custom Search