IACR News item: 25 May 2012
PhD Database
Name: Peter Birkner
Topic: Efficient Arithmetic on Low-Genus Curves
Category: public-key cryptography
Description: Public key cryptosystems are almost always based on two problems in number theory, the discrete-logarithm problem and the factorisation of integers. In this\r\nthesis we treat certain aspects of both of these problems.\r\n
\r\nThe 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.\r\n
\r\nThe 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.\r\n
\r\nSo 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\r\non 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.\r\n
\r\nWe 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\r\ngeneral 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\r\ngenus 3 we give (like in genus 2) a complete case study [...]
Topic: Efficient Arithmetic on Low-Genus Curves
Category: public-key cryptography
Description: Public key cryptosystems are almost always based on two problems in number theory, the discrete-logarithm problem and the factorisation of integers. In this\r\nthesis we treat certain aspects of both of these problems.\r\n
\r\nThe 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.\r\n
\r\nThe 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.\r\n
\r\nSo 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\r\non 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.\r\n
\r\nWe 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\r\ngeneral 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\r\ngenus 3 we give (like in genus 2) a complete case study [...]
Additional news items may be found on the IACR news page.