Schedule
Titles link to abstracts, papers (except for invited speakers) and slides (when available).
Links to Monday, Tuesday, Wednesday, Thursday, Friday.
Monday
| 09:00 - 10:00 | Registration/sign-in |
| 10:00 - 11:00 | Invited talk Chris Peikert Finding Short Generators of Ideals, and Implications for Cryptography, slides |
| 11:00 - 11:30 | Coffee break |
| 11:30 - 12:30 | Contributed talks
Wouter Castryck, Ilia Iliashenko and Frederik Vercauteren On error distributions in ring-based LWE, slides Gary McGuire, Henriette Heer and Oisin Robinson JKL-ECM: An implementation of ECM using Hessian curves, slides |
| 12:30 - 14:00 | Lunch break |
| 14:00 - 15:30 | Contributed talks Jung Hee Cheon, Jinhyuck Jeong and Changmin Lee An algorithm for NTRU problems and cryptanalysis of the GGH multilinear map without an encoding of zero, slides Steven Galbraith, Shishay Gebregiyorgis and Sean Murphy Algorithms for the approximate common divisor problem, slides Christine van Vredendaal Reduced memory meet-in-the-middle attack against the NTRU private key, slides |
| 15:30 - 16:00 | Coffee break |
| 16:00 - 17:00 | Contributed talks
Shi Bai, Thijs Laarhoven and Damien Stehlé Tuple lattice sieving, slides Pierrick Gaudry, Laurent Grémy and Marion Videau Collecting relations for the number field sieve in GF(p^6), slides |
Tuesday
| 09:30 - 10:30 | Invited talk Wei Ho Arithmetic invariant theory and distributions of invariants for number fields and elliptic curves |
| 10:30 - 11:00 | Coffee break |
| 11:00 - 12:30 | Contributed talks Jennifer Balakrishnan, Wei Ho, Nathan Kaplan, Simon Spicer, William Stein and James Weigandt Databases of elliptic curves ordered by height and distributions of Selmer groups and ranks, slides Andrew R. Booker, Jeroen Sijsling, Andrew V. Sutherland, John Voight and Dan Yasaki A database of genus 2 curves over the rational numbers, slides Kiran Kedlaya and Andrew Sutherland A census of zeta functions of quartic K3 surfaces over F_2, slides |
| 12:30 - 14:00 | Lunch break |
| 14:00 - 15:30 | Contributed talks Zander Kelley Roots of sparse polynomials over a finite field, slides Francois Morain, Charlotte Scribot and Benjamin Smith Computing cardinalities of Q-curve reductions over finite fields, slides J. Steffen Müller and Michael Stoll Computing canonical heights on elliptic curves in quasi-linear time, slides |
| 15:30 - 16:30 | Coffee break & Poster session |
| 16:30 - 17:30 | Buisness meeting |
Wednesday
| 09:30 - 10:30 | Invited talk Ghaith Hiary Analytic algorithms to compute L-functions | , slides
| 10:30 - 11:00 | Coffee break |
| 11:00 - 12:30 | Contributed talks Nathan Ryan, Nicolás Sirolli, Nils-Peter Skoruppa and Gonzalo Tornaría Computing Jacobi forms, slides Hugo Labrande and Emmanuel Thomé Computing theta functions in quasi-linear time in genus 2 and above, slides Tony Quertier Effective Hasse principle for the intersection of two quadrics, slides |
| 12:30 - 14:00 | Lunch break |
| 14:00 - ??:?? | Free afternoon |
| ??:?? - ??:?? | Conference dinner |
Thursday
| 09:30 - 10:30 | Invited talk Bianca Viray Brauer groups and the Brauer-Manin obstruction on geometrically abelian surfaces and geometrically Kummer surfaces |
| 10:30 - 11:00 | Coffee break |
| 11:00 - 12:30 | Contributed talks Jennifer S. Balakrishnan, Sorina Ionica, Kristin Lauter and Christelle Vincent Constructing genus 3 hyperelliptic Jacobians with CM, slides Luca Defeo, Jerome Plût, Eric Schost and Cyril Hugounenq Explicit isogenies in quadratic time in any characteristic, slides Tom Fisher Visualizing elements of order 7 in the Tate-Shafarevich group of an elliptic curve, slides |
| 12:30 - 14:00 | Lunch break |
| 14:00 - 15:30 | Contributed talks David Harvey, Maike Massierer and Andrew Sutherland Computing L-series of geometrically hyperelliptic curves of genus three, slides Abhinav Kumar and Ronen Mukamel Real multiplication through explicit correspondences, slides Yih-Dar Shieh Character theory approach to Sato-Tate groups, slides |
| 15:30 - 16:00 | Coffee break |
| 16:00 - 16:30 | Contributed talk Andreas-Stephan Elsenhans and Joerg Jahnel Point counting on K3 surfaces and an application concerning real and complex multiplication, slides |
| 16:30 - 17:30 | Rump session |
Friday
| 09:30 - 10:30 | Invited talk Henri Cohen Using trace formulas to construct modular form spaces | , slides
| 10:30 - 11:00 | Coffee break |
| 11:00 - 12:30 | Contributed talks Jean-François Biasse, Claus Fieker and Michael Jacobson Fast heuristic algorithms for computing relations in the class group of a quadratic order with applications to isogeny evaluation, slides Gebhard Boeckle and Damian Gvirtz Division algebras and maximal orders for given invariants Alexandre Gelin and Antoine Joux Reducing number field defining polynomials: an application to class group computations, slides |
Shi Bai, Thijs Laarhoven and Damien Stehlé - Tuple lattice sieving
Lattice sieving is asymptotically the fastest approach for solving the shortest vector problem (SVP) on Euclidean lattices. All known sieving algorithms for solving SVP require space which (heuristically) grows as $2^{0.2075 n + o(n)}$, where $n$ is the lattice dimension. In high dimensions, the memory requirement becomes a limiting factor for running these algorithms, making them uncompetitive with enumeration algorithms, despite their superior asymptotic time complexity. We show that sieving algorithms can be generalized to solve SVP with less memory. The idea is to consider reductions of tuples of vectors rather than pairs of vectors as existing sieve algorithms do. For triples, we estimate that the space requirement scales as $2^{0.1887 n + o(n)}$. The naive algorithm for this triple sieve runs in time $2^{0.5661 n + o(n)}$. With appropriate filtering of pairs, we show that the time complexity can be reduced to $2^{0.4812 n + o(n)}$ while keeping the same space complexity. We further analyze the effects of using larger tuples for reduction, and conjecture how this provides a continuous tradeoff between the memory-intensive sieving and the asymptotically slower enumeration.
Jennifer Balakrishnan, Wei Ho, Nathan Kaplan, Simon Spicer, William Stein and James Weigandt - Databases of elliptic curves ordered by height and distributions of Selmer groups and ranks
Several tables of data associated to ranks of elliptic curves have been developed over the past few decades, but in previous work the curves have been ordered by conductor. Recent developments, led by work of Bhargava–Shankar, have given new upper bounds on the average algebraic rank in families of elliptic curves over Q ordered by height by studying the average sizes of n-Selmer groups in these families. We describe databases of elliptic curves over Q ordered by height in which we compute ranks and 2-Selmer group sizes, the distributions of which may also be compared to these theoretical results. A striking new phenomenon observed in these databases is that the average rank eventually decreases as height increases.
Jennifer S. Balakrishnan, Sorina Ionica, Kristin Lauter and Christelle Vincent - Constructing genus 3 hyperelliptic Jacobians with CM
Given a CM sextic field $K$, we give an explicit method for finding and constructing all genus $3$ hyperelliptic curves defined over number fields whose Jacobians have complex multiplication by the maximal order of this field. Our algorithm works in complete generality, for any CM sextic field $K$, and for any period matrix for the Jacobian.
Jean-François Biasse, Claus Fieker and Michael Jacobson - Fast heuristic algorithms for computing relations in the class group of a quadratic order with applications to isogeny evaluation
In this paper, we present novels algorithms for finding small relations and ideal factorizations in the ideal class group of an order in an imaginary quadratic field, where both the norms of the prime ideals and the size of the coefficients involved are bounded. We show how our methods can be used to improve the computation of large-degree isogenies and endomorphism rings of elliptic curves defined over finite fields. We obtain improved heuristic complexity results in almost all cases for these problems, and significantly improved performance in practice, especially in situations where the ideal class group can be computed in advance.
Gebhard Boeckle and Damian Gvirtz - Division algebras and maximal orders for given invariants
Brauer classes of a global field can be represented by cyclic algebras. Effective constructions of such algebras and a maximal order therein are given for $\BF_q(t)$, excluding cases of wild ramification. As part of the construction, we also obtain a new description of subfields of cyclotomic function fields.
Andrew R. Booker, Jeroen Sijsling, Andrew V. Sutherland, John Voight and Dan Yasaki - A database of genus 2 curves over the rational numbers
We describe the construction of a database of genus 2 curves of small discriminant that includes geometric and arithmetic invariants of each curve, its Jacobian, and the associated L-function. This data has been incorporated into the $L$-Functions and Modular Forms Database (LMFDB).
Wouter Castryck, Ilia Iliashenko and Frederik Vercauteren - On error distributions in ring-based LWE
Since its introduction in 2010 by Lyubashevsky, Peikert and Regev, the Ring Learning With Errors problem (Ring-LWE) has been widely used as a building block for cryptographic primitives, due to its great versatility and its hardness proof consisting of a (quantum) reduction to ideal lattice problems. This reduction assumes a lower bound on the width of the error distribution that is often violated in practice. In this paper we show that caution is needed when doing so, by providing for any $\varepsilon > 0$, a family of number fields $K$ of increasing degree $n$ for which Ring-LWE can be broken easily as soon as the errors required by the reduction are scaled down by $|\Delta_K|^{\varepsilon/n}$ with $\Delta_K$ the discriminant of $K$.
Jung Hee Cheon, Jinhyuck Jeong and Changmin Lee - An algorithm for NTRU problems and cryptanalysis of the GGH multilinear map without an encoding of zero
Let h and g be polynomials of bounded Euclidean norm in the ring Z[X]/
Luca Defeo, Jerome Plût, Eric Schost and Cyril Hugounenq - Explicit isogenies in quadratic time in any characteristic
Consider two elliptic curves $E,E'$ defined over the finite field $\F_q$, and suppose that there exists an isogeny $\psi$ between $E$ and $E'$. We propose an algorithm that determines $\psi$ from the knowledge of $E$, $E'$ and of its degree $r$, by using the structure of the $ℓ$-torsion of the curves (where $ℓ$~is a prime different from the characteristic~$p$ of the base field). Our approach is inspired by a previous algorithm due to Couveignes, that involved computations using the $p$-torsion on the curves. The most refined version of that algorithm, due to De Feo, has a complexity of~$\tildO(r^2) p^{O(1)}$ base field operations. On the other hand, the cost of our algorithm is $\tildO(r^2 + \sqrt{r} \log(q))$; this makes it an interesting alternative for the medium- and large-characteristic cases.
Andreas-Stephan Elsenhans and Joerg Jahnel - Point counting on K3 surfaces and an application concerning real and complex multiplication
We report on our project to find explicit examples of $K3$ surfaces having real or complex multiplication. Our strategy is to search through the arithmetic consequences of RM and CM. In order to do this, an efficient method is needed for point counting on surfaces defined over finite fields. We describe $p$-adic algorithms based on ideas of Kedlaya and Harvey.
Tom Fisher - Visualizing elements of order 7 in the Tate-Shafarevich group of an elliptic curve
We study the elliptic curves in Cremona's tables that are predicted by the Birch--Swinnerton-Dyer conjecture to have elements of order 7 in their Tate-Shafarevich group. We show that in many cases these elements are visible in an abelian surface or abelian threefold.
Steven Galbraith, Shishay Gebregiyorgis and Sean Murphy - Algorithms for the approximate common divisor problem
The security of homomorphic encryption over the integers and its variants depends on the hardness of the Approximate Common Divisor (ACD) problem. We analyse and compare algorithms for the ACD problem. One of our main contributions is to compare the multivariate polynomial approach with other methods. We find that the multivariate polynomial approach is not better than the orthogonal lattice algorithm. We also develop a sample-amplification technique for ACD samples, and consider a pre-processing algorithm similar to the Blum-Kalai-Wasserman (BKW) algorithm for learning parity with noise. We explain why, unlike in other settings, the BKW algorithm does not give an improvement over the lattice algorithms.
Pierrick Gaudry, Laurent Grémy and Marion Videau - Collecting relations for the Number Field Sieve in GF(p^6)
In order to assess the security of cryptosystems based on the discrete logarithm problem in non-prime finite fields, as are the torus-based or pairing-based ones, we investigate thoroughly the case in GF(p^6) with the Number Field Sieve. We provide new insights, improvements, and comparisons between different methods to select polynomials intended for a sieve in dimension 3 using a special-q strategy. We also take into account the Galois action to increase the relation productivity of the sieving phase. To validate our results, we ran several experiments and real computations for various selection methods and field sizes with our publicly available implementation of the sieve in dimension 3, with special-q and various enumeration strategies.
Alexandre Gelin and Antoine Joux - Reducing number field defining polynomials: an application to class group computations
In this paper, we describe how to compute the smallest monic polynomial that defines a given number field K. We make use of the one-to-one correspondence between monic defining polynomials of K and algebraic integers that generate K. Thus, the smallest polynomial corresponds to a vector in the lattice of integers of K and this vector is short in some sense. The main idea is to consider weighted coordinates for the vectors of the lattice of integers of K. This allows us to find the desired polynomial by enumerating short vectors in these weighted lattices. In the context of the subexponential algorithm of Biasse and Fieker for computing class groups, this algorithm can be used as a precomputation step that speeds up the rest of the computation. It also widens the applicability of their faster conditional method, which requires a defining polynomial of small height, to a much larger set of number field descriptions.
David Harvey, Maike Massierer and Andrew Sutherland - Computing L-series of geometrically hyperelliptic curves of genus three
Let C/Q be a curve of genus three, given as a double cover of a plane conic with no Q-rational points. Such a curve is hyperelliptic over the algebraic closure of Q but does not have a hyperelliptic model of the usual form over Q. We describe an algorithm that computes the local zeta functions of C at all odd primes of good reduction up to a prescribed bound N. A novel feature of the new algorithm is an adaptation of the "accumulating remainder tree" to matrices with entries in a quadratic field. We report on an implementation, and compare its performance to previous algorithms for the rational hyperelliptic case.
Kiran Kedlaya and Andrew Sutherland - A census of zeta functions of quartic K3 surfaces over F_2
We compute the complete set of candidates for the zeta function of a K3 surface over F_2 consistent with the Weil conjectures, as well as the complete set of zeta functions of smooth quartic surfaces over F_2. These sets differ substantially, but we do identify natural subsets which coincide. This gives some numerical evidence towards a Honda-Tate theorem for transcendental zeta functions of K3 surfaces; such a result would refine a recent theorem of Taelman, in which one must allow an uncontrolled base field extension.
Zander Kelley - Roots of sparse polynomials over a finite field
For a $t$-nomial $f(x) = \sum_{i = 1}^t c_i x^{a_i} \in \mathbb{F}_q[x]$, we show that the number of distinct, nonzero roots of $f$ is bounded above by $2 (q-1)^{1-\varepsilon} C^\varepsilon$, where $\varepsilon = 1/(t-1)$ and $C$ is the size of the largest coset in $\mathbb{F}_q^*$ on which $f$ vanishes completely. Additionally, we describe a number-theoretic parameter depending only on $q$ and the exponents $a_i$ which provides a general and easily-computable upper bound for $C$. We thus obtain a strict improvement over an earlier bound of Canetti et al.\ which is related to the uniformity of the Diffie-Hellman distribution.
Abhinav Kumar and Ronen Mukamel - Real multiplication through explicit correspondences
We describe a method to compute equations for real multiplication on the divisors of genus two curves via algebraic correspondences. We implement our method for various examples drawn from the algebraic models for Hilbert modular surfaces computed by Elkies–Kumar. We also compute a correspondence over the universal family over the Hilbert modular surface of discriminant 5 and use our equations to prove a conjecture of A. Wright on dynamics over the moduli space of Riemann surfaces.
Hugo Labrande and Emmanuel Thomé - Computing theta functions in quasi-linear time in genus 2 and above
We outline an algorithm to compute Theta(z,tau) in genus 2 in quasi-optimal time, borrowing ideas from the algorithm for theta constants and the one for Theta(z,tau) in genus 1. Our implementation shows a large speedup for precisions as low as a few thousand decimal digits. We also lay out a strategy to generalize this algorithm to genus g.
Gary McGuire, Henriette Heer and Oisin Robinson - JKL-ECM: An implementation of ECM using Hessian curves
We present JKL-ECM, an implementation of the elliptic curve method of integer factorisation which uses certain twisted Hessian curves in a family studied by Jeon, Kim and Lee. This implementation takes advantage of torsion subgroup injection for families of elliptic curves over a quartic number field, in addition to the `small parameter' speedup. We produced thousands of curves with torsion $\mathbb{Z}/6\mathbb{Z}\oplus\mathbb{Z}/6\mathbb{Z}$ and small parameters in twisted Hessian form, which admit curve arithmetic that is `almost' as fast as that of twisted Edwards form. This allows JKL-ECM to compete with GMP-ECM for finding large prime factors. Also, JKL-ECM, based on GMP, accepts integers of arbitrary size. We classify the torsion subgroups of Hessian curves over $\mathbb{Q}$ and further examine torsion properties of the curves described by Jeon, Kim and Lee. In addition, the high-performance curves with torsion $\mathbb{Z}/2\mathbb{Z}\oplus\mathbb{Z}/8\mathbb{Z}$ of Bernstein et al are completely recovered by the $\mathbb{Z}/4\mathbb{Z}\oplus\mathbb{Z}/8\mathbb{Z}$ family of Jeon, Kim and Lee, and hundreds more curves are produced besides, all with small parameters and base points.
Francois Morain, Charlotte Scribot and Benjamin Smith - Computing cardinalities of Q-curve reductions over finite fields
We present a specialized point-counting algorithm for a class of elliptic curves over GF(p^2) that includes reductions of quadratic Q-curves modulo inert primes and, more generally, any elliptic curve over GF(p^2) with a low-degree isogeny to its Galois conjugate curve. These curves have interesting cryptographic applications. Our algorithm is a variant of the Schoof--Elkies--Atkin (SEA) algorithm, but with a new, lower-degree endomorphism in place of Frobenius. While it has the same asymptotic asymptotic complexity as SEA, our algorithm is much faster in practice.
J. Steffen Müller and Michael Stoll - Computing canonical heights on elliptic curves in quasi-linear time
We introduce an algorithm that can be used to compute the canonical height of a point on an elliptic curve over the rationals in quasi-linear time. As in most previous algorithms, we decompose the difference between the canonical and the naive height into an archimedean and a non-archimedean term. Our main contribution is an algorithm for the computation of the non-archimedean term that requires no integer factorization and runs in quasi-linear time.
Tony Quertier - Effective Hasse principle for the intersection of two quadrics
We consider a smooth system of two homogeneous quadratic equations over the rationals in $n \geq 13$ variables. In this case, the Hasse principle is known to hold, thanks to the work of Mordell in 1959. The only local obstruction is over the reals. In this paper, we give an explicit algorithm to decide whether a nonzero rational solution exists, and if so, compute one.
Nathan Ryan, Nicolás Sirolli, Nils-Peter Skoruppa and Gonzalo Tornaría - Computing Jacobi forms
We describe an implementation for computing holomorphic and skew-holomorphic Jacobi forms of integral weight and scalar index on the full modular group. This implementation is based on formulas derived by one of the authors which express Jacobi forms in terms of modular symbols of elliptic modular forms. Since this method allows to generate a Jacobi eigenform directly from a given modular eigensymbol without reference to the whole ambient space of Jacobi forms it makes it possible to compute Jacobi Hecke eigenforms of large index. We illustrate our method with several examples.
Yih-Dar Shieh - Character theory approach to Sato-Tate groups
In this article, we propose to use the character theory of compact Lie groups and their orthogonality relations for the study of Frobenius distribution and Sato-Tate groups. The results show the advantages of this new approach in several aspects. With samples of Frobenius ranging in size much smaller than the moment statistic approach, we obtain very good approximation to the expected values of these orthogonality relations, which give useful information about the underlying Sato-Tate groups and strong evidence of the correctness of the generalized Sato-Tate conjecture. In fact, $ 2^{10} $ to $ 2^{12} $ points provide satisfactory convergence. Even for $ g = 2 $, the classical approach using moment statistics requires about $ 2^{30} $ sample points to obtain such information.
Christine van Vredendaal - Reduced memory meet-in-the-middle attack against the NTRU private key
NTRU is a public-key cryptosystem introduced at ANTS-III. The two most used techniques in attacking the NTRU private key are meet-in-the-middle attacks and lattice-basis reduction attacks. In the 2007 CRYPTO paper ``A Hybrid Lattice-Reduction and Meet-in-the-Middle Attack Against NTRU'' both techniques are combined and it is pointed out that the largest obstacle to attacks is the memory capacities that are required for the meet-in-the-middle phase. In this paper an algorithm is presented that applies low-memory techniques to find `golden' collisions to Odlyzko's meet-in-the-middle attack against the NTRU private key. Several aspects of NTRU secret keys and the algorithm are analysed. The running time of the algorithm with a maximum storage capacity of $w$ is estimated and experimentally verified. Experiments indicate that decreasing the storage capacity by a factor $c$ increases the running time by a factor $\sqrt{c}$.