Low Genus Algebraic Curves in Cryptography
Tech report number
CERIAS TR 2009-07
Preserving a strong connection between mathematics and information security, elliptic and hyperelliptic curve cryptography are playing an increasingly important role during the past decade. We present some problems that relate low genus curves and cryptography. We first discuss a new application of elliptic curve cryptography (ECC) to a real-world problem of access control in secure broadcasting of data. The asymmetry, introduced by the elliptic curve discrete logarithm problem, is the key to achieving the required security feature that existing methods fail to obtain. We then talk about the use of genus 2 curves in the ``real model'' in cryptography, and present explicit divisor doubling formulas for such curves. These formulas are particularly important for implementation purposes. Finally, we present a new method for finding cryptographically strong parameters for the CM construction of genus 2 curves. This method uses the idea of polynomial parameterization, which allows suitable parameters to be generated in batches. We give a brief analysis of the algorithm. We also provide algorithms for generating parameters for genus 2 curves to be used in pairing-based cryptography. Our method is an adaptation of the Cocks-Pinch construction for pairing-friendly elliptic curves. Our methods start from a prescribed embedding degree $k$ and a primitive quartic CM field $K$, and output a prime subgroup order $r$ of the Jacobian over a prime field $mathbb_p$, with $rho = 2log(p)/log(r)approx 8$.
2009 – 1 – 1