Let be a group and . Using square-and-multiply techniques, one can rapidly compute for – in fact, group operations suffice.

On the other side, the inverse question, given and , how to find , is in general hard. In fact, a result by Victor Shoup says that for a black box group, there exists no deterministic algorithm which can find the in time less than steps in any case, provided the prime is the order of . In other words: the Discrete Logarithm Problem (DLP) is hard in general: given with , find with .

Consider the subgroup generated by . It is of the form , and the map , is an epimorphism. Let with ; then induces an isomorphism . The inverse map , is called the discrete logarithm with base , denoted by . Hence, the DLP is the problem of computing the function .

In 1976, Whitfield Diffie and Martin Hellman came up with a key exchange protocol based on the fact that, given , and , one probably needs to solve at least one DLP (to obtain or ) to be able to compute . And nine years later, Taher ElGamal presented an encryption scheme which is also based on the DLP.

First, these systems were originally used with or , the multiplicative groups of finite (prime) fields, but can in fact be used with any group. In 1985, Neal Koblitz and Victor Miller independently proposed to use elliptic curves over finite fields , which yield abelian groups of size . Later, groups obtained from hyperelliptic curves or curves were proposed.

There have also been proposals to replace groups by weaker structures, for example semigroups or certain loops. In general, one can use any algebraic structure which allows to define for , such that can be computed efficiently. As for that, one usually wants , we merely require the operation to be power associative.

Now one can ask if it is possible to drop this requirement and replace exponentiation and discrete logarithms by something similar. So far, the only such algebraic structure which has a huge class of instances which can be easily obtained from algebraic objects and in which one can efficiently compute are infrastructures. In the following articles I first want to explain and discuss the definition of infrastructures and show how finite abelian groups can be interpreted as infrastructures. Then I want to explain how infrastructures can be obtained from global fields.

In case you want to read up more details, please consult the preprint of my paper The Infrastructure of a Global Field of Arbitrary Unit Rank or my PhD thesis (click Volltext).