The Kate Edger Department of Mathematics

Elliptic Curves, Algorithms and Public Key Cryptography


Public key cryptography is an extremely active subject of research with important applications in e-commerce and internet security. In particular, key exchange is used in SSL protected communications (such as online shopping or internet banking) and public key digital signatures are used to verify that automatic software updates are not malicious software.

All public key cryptosystems are based on computational problems in mathematics which are believed to be difficult to solve efficiently. For example, the famous RSA cryptosystem is based on the difficulty of computing the prime factors of large composite integers. Similarly, elliptic curve cryptography is based on the difficulty of the discrete logarithm problem in the group of points on an elliptic curve over a finite field. Currently almost all public key cryptography used in the real world is based on factoring or discrete logarithms.

A major theme of my research is the study of computational problems underlying public key cryptography. I develop and analyse algorithms to solve these computational problems or variants of them. My research can be seen as testing the cryptosystems in light of mathematical developments, to determine whether they are still secure.

A recent research interest of mine has been randomised algorithms for variants of the discrete logarithm problem on elliptic curves. These randomized algorithms (building on work of John Pollard from the 1970s) do not require large amounts of storage and they can be parallelised and/or distributed over the internet. Together with my former PhD student Raminder Ruprai and with John Pollard, I have been studying the discrete logarithm problem in an interval: Given $g$, $h$ and $N$ find an integer $a$ such that $h=g^a$ and $0 \le a < N$. New algorithms have been found which solve this problem faster than was previously known.

I am also interested in algorithms for computing isogenies between elliptic curves over finite fields, and algorithms for computational problems related to lattices. There are a number of problems in these areas which are suitable for student projects at various levels.

Researchers at The University of Auckland: