Search

We describe a framework for constructing an efficient non-interactive key exchange (NIKE) protocol for n parties for any n >= 2. Our approach is based on the problem of computing isogenies between isogenous elliptic curves, which is believed to be difficult. We do not obtain a working protocol because of a missing step that is currently an open mathematical problem. What we need to complete our protocol is an efficient algorithm that takes as input an abelian variety presented as a product of isogenous elliptic curves, and outputs an isomorphism invariant of the abelian variety. Our framework builds a cryptographic invariant map, which is a new primitive closely related to a cryptographic multilinear map, but whose range does not necessarily have a group structure. Nevertheless, we show that a cryptographic invariant map can be used to build several cryptographic primitives, including NIKE, that were previously constructed from multilinear maps and indistinguishability obfuscation.

We give bounds on the primes of geometric bad reduction for curves of genus three of primitive CM type in terms of the CM orders. In the case of genus one, there are no primes of geometric bad reduction because CM elliptic curves are CM abelian varieties, which have potential good reduction everywhere. However, for genus at least two, the curve can have bad reduction at a prime although the Jacobian has good reduction. Goren and Lauter gave the first bound in the case of genus two. In the cases of hyperelliptic and Picard curves, our results imply bounds on primes appearing in the denominators of invariants and class polynomials, which are important for algorithmic construction of curves with given characteristic polynomials over finite fields., Comment: 16 pages, some minor updates, some typos are corrected

Given a sextic CM field $K$, we give an explicit method for finding all genus 3 hyperelliptic curves defined over $\mathbb{C}$ whose Jacobians are simple and have complex multiplication by the maximal order of this field, via an approximation of their Rosenhain invariants. Building on the work of Weng, we give an algorithm which works in complete generality, for any CM sextic field $K$, and computes minimal polynomials of the Rosenhain invariants for any period matrix of the Jacobian. This algorithm can be used to generate genus 3 hyperelliptic curves over a finite field $\mathbb{F}_p$ with a given zeta function by finding roots of the Rosenhain minimal polynomials modulo $p$., Comment: 20 pages; to appear in ANTS XII

Let $C$ be a smooth, absolutely irreducible genus-$3$ curve over a number field $M$. Suppose that the Jacobian of $C$ has complex multiplication by a sextic CM-field $K$. Suppose further that $K$ contains no imaginary quadratic subfield. We give a bound on the primes $\mathfrak{p}$ of $M$ such that the stable reduction of $C$ at $\mathfrak{p}$ contains three irreducible components of genus $1$.

We study the problem of efficiently constructing a curve C of genus 2 over a finite field F for which either the curve C itself or its Jacobian has a prescribed number N of F-rational points. In the case of the Jacobian, we show that any `CM-construction' to produce the required genus-2 curves necessarily takes time exponential in the size of its input. On the other hand, we provide an algorithm for producing a genus-2 curve with a given number of points that, heuristically, takes polynomial time for most input values. We illustrate the practical applicability of this algorithm by constructing a genus-2 curve having exactly 10^2014 + 9703 (prime) points, and two genus-2 curves each having exactly 10^2013 points. In an appendix we provide a complete parametrization, over an arbitrary base field k of characteristic neither 2 nor 3, of the family of genus-2 curves over k that have k-rational degree-3 maps to elliptic curves, including formulas for the genus-2 curves, the associated elliptic curves, and the degree-3 maps., Comment: Made a number of clarifications and corrected some typographical errors

We provide new upper bounds on N_q(g), the maximum number of rational points on a smooth absolutely irreducible genus-g curve over F_q, for many values of q and g. Among other results, we find that N_4(7) = 21 and N_8(5) = 29, and we show that a genus-12 curve over F_2 having 15 rational points must have characteristic polynomial of Frobenius equal to one of three explicitly given possibilities. We also provide sharp upper bounds for the lengths of the shortest vectors in Hermitian lattices of small rank and determinant over the maximal orders of small imaginary quadratic fields of class number 1. Some of our intermediate results can be interpreted in terms of Mordell-Weil lattices of constant elliptic curves over one-dimensional function fields over finite fields. Using the Birch and Swinnerton-Dyer conjecture for such elliptic curves, we deduce lower bounds on the orders of certain Shafarevich-Tate groups., Comment: LaTeX, 35 pages

We prove a higher dimensional generalization of Gross and Zagier's theorem on the factorization of differences of singular moduli. Their result is proved by giving a counting formula for the number of isomorphisms between elliptic curves with complex multiplication by two different imaginary quadratic fields $K$ and $K^\prime$, when the curves are reduced modulo a supersingular prime and its powers. Equivalently, the Gross-Zagier formula counts optimal embeddings of the ring of integers of an imaginary quadratic field into particular maximal orders in $B_{p, \infty}$, the definite quaternion algebra over $\QQ$ ramified only at $p$ and infinity. Our work gives an analogous counting formula for the number of simultaneous embeddings of the rings of integers of primitive CM fields into superspecial orders in definite quaternion algebras over totally real fields of strict class number 1. Our results can also be viewed as a counting formula for the number of isomorphisms modulo $\frak{p} | p$ between abelian varieties with CM by different fields. Our counting formula can also be used to determine which superspecial primes appear in the factorizations of differences of values of Siegel modular functions at CM points associated to two different CM fields, and to give a bound on those supersingular primes which can appear. In the special case of Jacobians of genus 2 curves, this provides information about the factorizations of numerators of Igusa invariants, and so is also relevant to the problem of constructing genus 2 curves for use in cryptography., Comment: 32 pages

We give a classification of all principally polarized abelian surfaces that admit an $(l,l)$-isogeny to themselves, and show how to compute all the abelian surfaces that occur. We make the classification explicit in the simplest case $l=2$. As part of our classification, we also show how to find all principally polarized abelian surfaces with multiplication by a given imaginary quadratic order., Comment: 25 pages

Bruinier and Yang conjectured a formula for an intersection number on the arithmetic Hilbert modular surface, CM(K).T_m, where CM(K) is the zero-cycle of points corresponding to abelian surfaces with CM by a primitive quartic CM field K, and T_m is the Hirzebruch-Zagier divisors parameterizing products of elliptic curves with an m-isogeny between them. In this paper, we examine fields not covered by Yang's proof of the conjecture. We give numerical evidence to support the conjecture and point to some interesting anomalies. We compare the conjecture to both the denominators of Igusa class polynomials and the number of solutions to the embedding problem stated by Goren and Lauter., Comment: 27 pages, 1 table, 1 appendix with Magma code. To appear in Fields Communications Volume WIN - Women In Numbers, Proceedings of the WIN Workshop, Banff International Research Station, Banff, Canada

For a complex abelian variety $A$ with endomorphism ring isomorphic to the maximal order in a quartic CM-field $K$, the Igusa invariants $j_1(A), j_2(A),j_3(A)$ generate an abelian extension of the reflex field of $K$. In this paper we give an explicit description of the Galois action of the class group of this reflex field on $j_1(A),j_2(A),j_3(A)$. We give a geometric description which can be expressed by maps between various Siegel modular varieties. We can explicitly compute this action for ideals of small norm, and this allows us to improve the CRT method for computing Igusa class polynomials. Furthermore, we find cycles in isogeny graphs for abelian surfaces, thereby implying that the `isogeny volcano' algorithm to compute endomorphism rings of ordinary elliptic curves over finite fields does not have a straightforward generalization to computing endomorphism rings of abelian surfaces over finite fields.

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., Comment: 18 pages; revised version includes some small mathematical corrections, reformatted

For a quartic primitive CM field $K$, we say that a rational prime $p$ is {\it evil} if at least one of the abelian varieties with CM by $K$ reduces modulo a prime ideal $\gerp| p$ to a product of supersingular elliptic curves with the product polarization. We call such primes {\it evil primes for $K$}. In \cite{GL}, we showed that for fixed $K$, such primes are bounded by a quantity related to the discriminant of the field $K$. In this paper, we show that evil primes are ubiquitous in the sense that, for any rational prime $p$, there are an infinite number of fields $K$ for which $p$ is evil for $K$. The proof consists of two parts: (1) showing the surjectivity of the abelian varieties with CM by $K$, for $K$ satisfying some conditions, onto the the superspecial points modulo $\gerp$ of the Hilbert modular variety associated to the intermediate real quadratic field of $K$, and (2) showing the surjectivity of the superspecial points modulo $\gerp$ of the Hilbert modular variety associated to a large enough real quadratic field onto the superspecial points modulo $\gerp$ with principal polarization on the Siegel moduli space., Comment: 11 pages

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., Comment: 8 pages, appendix added with correction to Elkies' running time, final version to appear in London Math Society Journal of Computation and Mathematics

We present a new method for constructing genus 2 curves over a finite field with a given number of points on its Jacobian. This method has important applications in cryptography, where groups of prime order are used as the basis for discrete-log based cryptosystems. Our algorithm provides an alternative to the traditional CM method for constructing genus 2 curves. For a quartic CM field K with primitive CM type, we compute the Igusa class polynomials modulo p for certain small primes p and then use the Chinese remainder theorem (CRT) and a bound on the denominators to construct the class polynomials. We also provide an algorithm for determining endomorphism rings of ordinary Jacobians of genus 2 curves over finite fields, generalizing the work of Kohel for elliptic curves., Comment: 16 pages. to appear in Proceedings of AGCT-10

One can define class invariants for a quartic primitive CM field K as special values of certain Siegel (or Hilbert) modular functions at CM points corresponding to K. We provide explicit bounds on the primes appearing in the denominators of these algebraic numbers. This allows us, in particular, to construct S-units in certain abelian extensions of K, where S is effectively determined by K. It also yields class polynomials for primitive quartic CM fields whose coefficients are S-integers., Comment: 14 pages

A curve over a field k is pointless if it has no k-rational points. We show that there exist pointless genus-3 hyperelliptic curves over a finite field F_q if and only if q < 26, that there exist pointless smooth plane quartics over F_q if and only if either q < 24 or q = 29 or q = 32, and that there exist pointless genus-4 curves over F_q if and only if q < 50., Comment: LaTeX, 15 pages

The purpose of this note is to suggest an analogue for genus 2 curves of part of Gross and Zagier's work on elliptic curves. Experimentally, for genus 2 curves with CM by a quartic CM field K, it appears that primes dividing the denominators of the discriminants of the Igusa class polynomials all have the property 1) that they are bounded by d, the absolute value of the discriminant of K, and 2) that they divide d-x^2, for some integer x whose square is less than d. A slightly stronger condition is given in Section 3. Such primes are primes of bad reduction for the genus 2 curve and primes of supersingular reduction for the Jacobian of the genus 2 curve., Comment: 3 pages

We give new arguments that improve the known upper bounds on the maximal number N_q(g) of rational points of a curve of genus g over a finite field F_q for a number of pairs (q,g). Given a pair (q,g) and an integer N, we determine the possible zeta functions of genus-g curves over F_q with N points, and then deduce properties of the curves from their zeta functions. In many cases we can show that a genus-g curve over F_q with N points must have a low-degree map to another curve over F_q, and often this is enough to give us a contradiction. In particular, we able to provide eight previously unknown values of N_q(g), namely: N_4(5) = 17, N_4(10) = 27, N_8(9) = 45, N_{16}(4) = 45, N_{128}(4) = 215, N_3(6) = 14, N_9(10) = 54, and N_{27}(4) = 64. Our arguments also allow us to give a non-computer-intensive proof of the recent result of Savitt that there are no genus-4 curves over F_8 having exactly 27 rational points. Furthermore, we show that there is an infinite sequence of q's such that for every g with 0 < g < log_2 q, the difference between the Weil-Serre bound on N_q(g) and the actual value of N_q(g) is at least g/2., Comment: LaTex, 40 pages. There was a mistake in Section 7 that invalidated the proofs of two of our results. We correct the error in Section 7, and add an appendix with new proofs of the two results

Elliptic curves with a known number of points over a given prime field with n elements are often needed for use in cryptography. 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 a root modulo n of the Hilbert class polynomial H(X) for a fundamental discriminant D. The usual way is to compute H(X) over the integers and then to find the root modulo n. We present a modified version of the Chinese remainder theorem (CRT) to compute H(X) modulo n directly from the knowledge of H(X) modulo enough small primes. Our complexity analysis suggests that asymptotically our algorithm is an improvement over previously known methods., Comment: 14 pages, complexity analysis redone, several sections rewritten

Currently, the best upper bounds on the number of rational points on an absolutely irreducible, smooth, projective algebraic curve of genus g defined over a finite field F_q come either from Serre's refinement of the Weil bound if the genus is small compared to q, or from Oesterle's optimization of the explicit formulae method if the genus is large. This paper presents three methods for improving these bounds. The arguments used are the indecomposability of the theta divisor of a curve, Galois descent, and Honda-Tate theory. Examples of improvements on the bounds include lowering them for a wide range of small genus when q=2^3, 2^5, 2^{13}, 3^3, 3^5, 5^3, 5^7, and when q=2^{2s}, s>1. For large genera, isolated improvements are obtained for q=3,8,9., Comment: 16 pages including the appendix. Main paper by Kristin Lauter, appendix by Jean-Pierre Serre

We show that for all finite fields F_q, there exists a curve C over F_q of genus 3 such that the number of rational points on C is within 3 of the Serre-Weil upper or lower bound. For some q, we also obtain improvements on the upper bound for the number of rational points on a genus 3 curve over F_q., Comment: 28 pages including the appendix. Main paper by Kristin Lauter, appendix by Jean-Pierre Serre