## CryptoDB

### Kristin E. Lauter

#### Publications

**Year**

**Venue**

**Title**

2010

EPRINT

Computing genus 2 curves from invariants on the Hilbert moduli space
Abstract

We give a new method for generating genus 2 curves over a finite field with a given number of points on the Jacobian of the curve. We define two new invariants for genus 2 curves as values of modular functions on the Hilbert moduli space and show how to compute them. We relate them to the usual three Igusa invariants on the Siegel moduli space and give an algorithm to construct curves using these new invariants. Our approach simplifies the complex analytic method for computing genus 2 curves for cryptography and reduces the amount of computation required.

2010

EPRINT

Genus 2 Curves with Complex Multiplication
Abstract

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.

2010

EPRINT

An Analysis of Affine Coordinates for Pairing Computation
Abstract

In this paper we analyze the use of affine coordinates for pairing computation. We observe that in many practical settings, for example when implementing optimal ate pairings in high security levels, affine coordinates are faster than using the best currently known formulas for projective coordinates. This observation relies on two known techniques for speeding up field inversions which we analyze in the context of pairing computation. We give detailed performance numbers for a pairing implementation based on these ideas, including timings for base field and extension field arithmetic with relative ratios for inversion-to-multiplication costs, timings for pairings in both affine and projective coordinates, and average timings for multiple pairings and products of pairings.

2008

EPRINT

Computing Hilbert Class Polynomials
Abstract

We present and analyze two algorithms for computing the Hilbert class polynomial H_D(X). The first is a p-adic lifting algorithm for inert primes p in the order of discriminant D < 0. The second is an improved Chinese remainder algorithm which uses the class group action on CM-curves over finite fields. Our run time analysis gives tighter bounds for the complexity of all known algorithms for computing H_D(X), and we show that all methods have comparable run times.

2008

EPRINT

The Elliptic Curve Discrete Logarithm Problem and Equivalent Hard Problems for Elliptic Divisibility Sequences
Abstract

We define three hard problems in the theory of elliptic divisibility sequences (EDS Association, EDS Residue and EDS Discrete Log), each of which is solvable in sub-exponential time if and only if the elliptic curve discrete logarithm problem is solvable in sub-exponential time. We also relate the problem of EDS Association to the Tate pairing and the MOV, Frey-R\"{u}ck and Shipsey EDS attacks on the elliptic curve discrete logarithm problem in the cases where these apply.

2008

EPRINT

Modular polynomials for genus 2
Abstract

Modular polynomials are an important tool in many algorithms involving elliptic curves. In this article we generalize this concept to the
genus 2 case. We give the theoretical framework describing the genus 2
modular polynomials and discuss how to explicitly compute them.

2008

EPRINT

Full Cryptanalysis of LPS and Morgenstern Hash Function
Abstract

Collisions in the LPS cryptographic hash function of Charles, Goren and Lauter have been found by Zémor and
Tillich, but it was not clear whether computing preimages was also easy for this hash
function. We present a probabilistic polynomial time algorithm solving this problem. Subsequently, we study the
Morgenstern hash, an interesting variant of LPS hash, and break this function as well. Our attacks build upon the ideas of Zémor and Tillich but are not straightforward extensions of it. Finally, we discuss fixes for the
Morgenstern hash function and other applications of our results.

2007

EPRINT

Computing endomorphism rings of Jacobians of genus 2 curves over finite fields
Abstract

We present probabilistic algorithms which, given a genus 2 curve C defined over a finite field and a quartic CM field K, determine whether the endomorphism ring of the Jacobian J of C is the full ring of integers in K. In particular, we present algorithms for computing the field of definition of, and the action of Frobenius on, the subgroups J[l^d] for prime powers l^d. We use these algorithms to create the first implementation of Eisentrager and Lauter's algorithm for computing Igusa class polynomials via the Chinese Remainder Theorem, and we demonstrate the algorithm for a few small examples. We observe that in practice the running time of the CRT algorithm is dominated not by the endomorphism ring computation but rather by the need to compute p^3 curves for many small primes p.

2006

EPRINT

Cryptographic hash functions from expander graphs
Abstract

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.

2006

EPRINT

Signatures for Network Coding
Abstract

This paper presents a practical digital signature scheme to be used in conjunction with network coding. Our scheme simultaneously provides authentication and detects malicious nodes that intentionally corrupt content on the network. The homomorphic property of the signatures allows nodes to sign any linear comination of the incoming packets without contacting the signing authority, but it is computationally infeasible for a node to sign a linear combination of the packets without disclosing what linear combination was used in the generation of the packet. Furthermore, we prove that the signature scheme is secure under well known cryptographic assumptions of the hardness of the Discrete-Log problem and the computational co-Diffie-Hellman problem on elliptic curves. Our scheme has a three-fold advantage over schemes based on homomorphic hashing: Firstly, we do not need to securely transmit hash values of the packets that the source transmits; secondly, since our scheme is based on elliptic curves, smaller security parameters suffice and this translates to improved efficiency since the bit lengths involved are smaller; finally, our scheme provides authentication of the data in addition to detecting pollution of packets.

2006

EPRINT

Stronger Security of Authenticated Key Exchange
Abstract

In this paper we study security definitions for authenticated key
exchange (AKE) protocols. We observe that there are several
families of attacks on AKE protocols that lie outside the boundary
of the current class of security definitions. In an attempt to
bring these attacks within the scope of analysis we extend the AKE
security definition to provide greater powers to the adversary. We
provide a general framework for defining AKE security, which we call
strong AKE security, such that existing security definitions
occur as instances of the framework. We then introduce NAXOS, a new
two-pass AKE protocol, and prove that it is secure in this stronger
definition.
In addition, we formulate a notion of ephemeral secret key which
captures all ephemeral information used in session establishment. We
demonstrate the importance of this formulation by showing that a
secure AKE protocol SIG-DH can become vulnerable when instantiated
with signature schemes which are insecure against revelation of the
secret random bits used in the signature generation.

2005

EPRINT

Security Analysis of KEA Authenticated Key Exchange Protocol
Abstract

KEA is a Diffie-Hellman based key-exchange protocol
developed by NSA which provides mutual authentication for the
parties. It became publicly available in 1998 and since then it was
neither attacked nor proved to be secure. We analyze the security of
KEA and find that the original protocol is susceptible to a class of
attacks. On the positive side, we present a simple modification of
the protocol which makes KEA secure. We prove that the modified
protocol, called KEA+, satisfies the strongest security requirements
for authenticated key-exchange and that it retains some security
even if a secret key of a party is leaked. Our security proof is in
the random oracle model and uses the Gap Diffie-Hellman assumption.
Finally, we show how to add a key confirmation feature to KEA+ (we
call the version with key confirmation KEA+C) and discuss the
security properties of KEA+C.

2004

EPRINT

Computing Modular Polynomials
Abstract

We present a new probabilistic algorithm to compute modular polynomials modulo a prime. Modular polynomials parameterize pairs of isogenous elliptic curves and are useful in many aspects of computational number theory and cryptography. Our algorithm has the distinguishing feature that it does not involve the computation of Fourier coefficients of modular forms. We avoid computing the exponentially large integral coefficients by working directly modulo a prime and computing isogenies between elliptic curves via Velu's formulas.

2003

EPRINT

Improved Weil and Tate pairings for elliptic and hyperelliptic curves
Abstract

We present algorithms for computing the {\it squared} Weil and Tate pairings on an elliptic curve and the {\it squared} Tate pairing for hyperelliptic curves. The squared pairings introduced in this paper have the advantage that our algorithms for evaluating them are deterministic and do not depend on a random choice of points. Our pairings save about 20-30\% over the usual pairings.

2003

EPRINT

Trading Inversions for Multiplications in Elliptic Curve Cryptography
Abstract

Recently, Eisentraeger-Lauter-Montgomery proposed a method for speeding up scalar multiplication on elliptic curves. That method relies on improved formulae for evaluating S = 2P + Q from given points P and Q on an elliptic curve. Compared to the naive approach, the improved formulae save a field multiplication each time the operation is performed.
This paper proposes a variant which is faster whenever a field inversion is more expensive than six field multiplications. We also give an improvement when tripling or quadrupling a point, and present a ternary/binary method to perform efficient scalar multiplication.

2002

EPRINT

An Efficient Procedure to Double and Add Points on an Elliptic Curve
Abstract

We present an algorithm that speeds exponentiation on a
general elliptic curve by an estimated 3.8% to 8.5% over the best
known general exponentiation methods when using affine coordinates.
This is achieved by eliminating a field multiplication when we compute 2P + Q from given points P, Q on the curve. We give
applications to simultaneous multiple exponentiation and to the
Elliptic Curve Method of factorization. We show how this
improvement together with another idea can speed the
computation of the Weil and Tate pairings by up to 7.8%.

2001

EPRINT

Constructing elliptic curves with a given number of points over a finite field
Abstract

In using elliptic curves for cryptography, one often needs to construct elliptic curves with a given or known number of points over a given finite field. In the context of primality proving, Atkin and Morain suggested the use of the theory of complex multiplication to construct such curves. One of the steps in this method is the calculation of the Hilbert class polynomial
$H_D(X)$ modulo some integer $p$ for a certain fundamental discriminant $D$. The usual way of doing this is to compute
$H_D(X)$ over the integers and then reduce modulo $p$. But this involves computing the roots with very high accuracy and subsequent rounding of the coefficients to the closest integer. (Such accuracy issues also arise for higher genus cases.) We present a modified version of the Chinese remainder theorem (CRT) to compute $H_D(X)$ modulo $p$ directly from the knowledge of $H_D(X)$ modulo enough small primes. Our algorithm is inspired by Couveigne's method for computing square roots in the number field sieve, which is useful in other scenarios as well. It runs in heuristic expected time less than
the CRT method in [CNST]. Moreover, our method requires very few digits of precision to succeed, and avoids calculating the exponentially large coefficients of the Hilbert class polynomial over the integers.

#### Program Committees

- Crypto 2013
- Crypto 2008
- Crypto 2007

#### Coauthors

- Amod Agashe (1)
- Juliana Belding (1)
- Joppe W. Bos (4)
- Reinier Broker (2)
- Denis Charles (4)
- Hao Chen (1)
- Jung Hee Cheon (1)
- Mathieu Ciet (1)
- Craig Costello (4)
- Alyson Deines-Schartz (1)
- Kirsten Eisenträger (3)
- Yara Elias (3)
- Andreas Enge (1)
- Tony Feng (1)
- David Freeman (1)
- Eyal Z. Goren (3)
- Sean Hallgren (1)
- Hüseyin Hisil (1)
- Hüseyin Hisil (2)
- Kamal Jain (1)
- Marc Joye (1)
- Miran Kim (2)
- David Kohel (1)
- Kim Laine (2)
- Brian A. LaMacchia (1)
- Adriana López-Alt (1)
- Anton Mityagin (3)
- Peter L. Montgomery (4)
- Travis Morrison (1)
- Michael Naehrig (5)
- Ekin Ozman (3)
- Christophe Petit (3)
- Jean-Jacques Quisquater (1)
- Martin Roetteler (1)
- Katherine E. Stange (5)
- Krysta M. Svore (1)
- Jean-Pierre Tignol (1)
- Ramarathnam Venkatesan (1)
- David J. Wu (1)
- Tonghai Yang (2)