The aim of the IACR Ph.D. database is twofold. On the first hand, we want to offer an overview of Ph.D. already completed
in the domain of cryptology. Where possible, this should also include a subject classification, an abstract, and
access to the full text.
On the second hand, it deals with Ph.D. subjects
currently under investigation. This way, we provide a timely
map of contemporary research in cryptology.
All entries or changes need to be approved by an editor. You can contact them via phds (at) iacr.org.
Peter Birkner (#802)
Topic of his/her doctorate.
Efficient Arithmetic on Low-Genus Curves
elliptic curves, hyperelliptic curves, efficient curve arithmetic, Edwards curves
Year of completion
Public key cryptosystems are almost always based on two problems in number theory, the discrete-logarithm problem and the factorisation of integers. In this
thesis we treat certain aspects of both of these problems.
The most crucial parts of a cryptosystem that is based on the discrete-logarithm problem are the group and the efficiency of the arithmetic in this group. In this work we have investigated divisor class groups of hyperelliptic curves of genus 2 and 3 over binary fields. We suggest certain curves such that the appropriate group is considered secure, and provide efficient arithmetic on these curves.
The most important operation in curve-based cryptosystems is single-scalar multiplication of divisor classes. Therefore a very time-efficient arithmetic is necessary. Since scalar multiplication is almost always computed using double and-add algorithms (or variants of these), it stands to reason to develop efficient doubling and addition formulas. In case of elliptic curves it turned out that point halving is very efficient, and hence halve-and-add algorithms proved very successful and could even replace the double-and-add methods in some situations.
So it is natural to ask if similar results can be obtained for hyperelliptic curves as well. For genus-2 curves we have developed explicit halving formulas which can in some settings even beat the doubling counterparts. For the high-speed case
on the genus-2 curves we also give a complete case study, that covers all special cases, depending on the polynomial representation of the divisor class.
We have generalised this also to the genus-3 case and investigated several types of curves and developed explicit halving formulas. For some curves of a rather
general form we could even beat the doubling formulas by 10 to 20 field multiplications which is a speedup of about 30-40%. For the most common setting in
genus 3 we give (like in genus 2) a complete case study for all possible subcases.
This provides a programmer with everything he needs to do an implementation of a cryptosystem based on the DLP on divisor class groups of hyperelliptic curves of genus 3.
The third subject in this thesis (besides hyperelliptic curves of genus 2 and genus 3) is Edwards curves. We have investigated elliptic curves in Edwards and twisted Edwards form. We have looked at explicit addition, doubling and tripling formulas in affine, projective and inverted Edwards coordinates. The arithmetic on Edwards curves turns out to be faster than on elliptic curves in
other forms. Twisted Edwards curves cover even more elliptic curves: We have shown that every Montgomery-form elliptic curve is birationally equivalent to a twisted Edwards curve. This brings the speed of the Edwards addition law to Montgomery curves.
Furthermore, we have demonstrated how to construct Edwards and twisted Edwards curves with prescribed torsion subgroup and positive rank, which is essential
for the ECM method of factorisation. With this we treat the second problem on which cryptosystem can be based on. The use of Edwards curves improved the speed of factoring integers by using better curves and faster arithmetic.
peter.birkner (at) web.de