## Abstract

This thesis studies the implications of using public key cryptographic
primitives
that are based in, or map to, the multiplicative group of finite fields
with small extension degree.
A central observation is that the multiplicative group of extension fields
essentially decomposes as a product of algebraic tori, whose properties
allow for improved communication efficiency.
Part I of this thesis is concerned with the constructive
implications of this idea.
Firstly, algorithms are developed for the efficient
implementation of torus-based cryptosystems and their
performance compared with previous work. It is then shown
how to apply these methods to operations required in low
characteristic pairing-based cryptography. Finally,
practical schemes for high-dimensional tori are discussed.
Highly optimised implementations and benchmark timings
are provided for each of these systems.
Part II addresses the security of the schemes presented in Part I, i.e.,
the hardness of the discrete logarithm problem.
Firstly, an heuristic analysis
of the effectiveness of the Function Field Sieve in small
characteristic is given. Next presented is an implementation of this
algorithm for characteristic three fields used in pairing-based
cryptography. Finally, a new index calculus algorithm
for solving the discrete logarithm problem on algebraic tori
is described and analysed.

Translated title of the contribution | On Small Degree Extension Fields in Cryptology |
---|---|

Original language | English |

Publication status | Published - 2005 |