International Association for Cryptologic Research

International Association
for Cryptologic Research


Eyal Z. Goren


Genus 2 Curves with Complex Multiplication
Eyal Z. Goren Kristin E. Lauter
Genus 2 curves are useful in cryptography for both discrete-log based and pairing-based systems, but a method is required to compute genus 2 curves with Jacobian with a given number of points. Currently, all known methods involve constructing genus 2 curves with complex multiplication via computing their 3 Igusa class polynomials. These polynomials have rational coefficients and require extensive computation and precision to compute. Both the computation and the complexity analysis of these algorithms can be improved by a more precise understanding of the denominators of the coefficients of the polynomials. The main goal of this paper is to give a bound on the denominators of Igusa class polynomials of genus 2 curves with CM by a primitive quartic CM field $K$. We give an overview of Igusa's results on the moduli space of genus two curves and the method to construct genus 2 curves via their Igusa invariants. We also give a complete characterization of the reduction type of a CM abelian surface, for biquadratic, cyclic, and non-Galois quartic CM fields, and for any type of prime decomposition of the prime, including ramified primes.
Cryptographic hash functions from expander graphs
We propose constructing provable collision resistant hash functions from expander graphs. As examples, we investigate two specific families of optimal expander graphs for provable hash function constructions: the families of Ramanujan graphs constructed by Lubotzky-Phillips-Sarnak and Pizer respectively. When the hash function is constructed from one of Pizer's Ramanujan graphs, (the set of supersingular elliptic curves over ${\FF}_{p^2}$ with $\ell$-isogenies, $\ell$ a prime different from $p$), then collision resistance follows from hardness of computing isogenies between supersingular elliptic curves. We estimate the cost per bit to compute these hash functions, and we implement our hash function for several members of the LPS graph family and give actual timings.


Denis Charles (2)
Kristin E. Lauter (3)