Programme of the Diamant symposium
June 1 and 2 2017
Hotel Van der Valk, Breukelen
Thursday  
11:0011:25  arrival and coffee 
11:2511:30  welcome 
Cristóbal Guzmán (Universidad Católica de Chile/CWI)  Great Tolls: How to induce optimal flows under strategic link owners 
11:3012:25 
Network pricing games provide a framework for modeling realworld settings with two types of strategic agents: users of the network and owners of the network. Owners of the network post a price for usage of the link they own; users of the network select routes based on price and level of use by other users. The challenge in these games is that there are two levels of competition: one, among the owners to attract users to their link so as to maximize profit; and second, among users of the network to select routes that are cheap yet not too congested. Interestingly, we observe that: (i) an equilibrium may not exist; (ii) it might not be unique; and (iii) the network performance at equilibrium can be arbitrarily inefficient. Our main result is to observe that a slight regulation on the network owners market solves all three issues above. Specifically, if the authority could set appropriate caps (upper bounds) on the tolls (prices) operators can charge then: the game among the link operators has a unique strong Nash equilibrium and the users’ game results in a Wardrop equilibrium that achieves the optimal total delay. We call any price vector with these properties a great set of tolls. We then ask, can we compute great tolls that minimize total users’ payments? We show that this optimization problem reduces to a linear program in the case of singlecommodity seriesparallel networks. Starting from the same linear program, we obtain multiplicative approximation results for arbitrary networks with polynomial latencies of bounded degree, while in the singlecommodity case we obtain a surprising bound, which only depends on the topology of the network. This is joint work with José Correa, Thanasis Lianeas, Evdokia Nikolova and Marc Schröder.

12:3013:30  lunch 
David de Laat (CWI)  Using (noncommutative) polynomial optimization to bound matrix factorization ranks 
13:3013:55  In this talk I will explain how polynomial optimization can be used to compute lower bounds on matrix factorization ranks. First I will show how we can use noncommutative polynomial optimization to compute lower bounds on the cpsdrank (completely positive semidefinite rank) of a matrix. The cpsdrank of a matrix A is the smallest integer d for which A can be written as the Gram matrix of positive semidefinite d by d matrices. Then I will show how we can use these ideas to also compute lower bounds on the cprank and nonnegative rank of a matrix, and I will compare this to existing techniques. 
Chloe Martindale (TUe)  Constructing genus 2 curves with a prescribed number of points 
14:0014:25  We will give a definition of class polynomials for genus 2 curves, and show how they are used to construct genus 2 curves with a prescribed number of points. We give a new algorithm to compute class polynomials for genus 2 curves, and explain briefly the applications to cryptography. 
Mark Jones (TUD)  Constructing a consensus phylogeny from a leafremoval distance 
14:3014:55  Understanding the evolution of a set of genes or species is a fundamental problem in evolutionary biology. In this talk, we are given a set of phylogenetic trees that describe conflicting evolutionary histories for a set of species, and our task is to find a single tree that agrees with the input trees as much as possible. We study a few variants of this problem, where disagreement between two trees is measured by the number of leaves that need to be deleted before the trees become identical. At the end of the talk, we'll briefly discuss how the situation becomes more complex when phylogenetic trees are generalised to phylogenetic networks. 
15:0015:30  tea 
Guido Lido (UL, Roma Tor Vergata)  Discrete logarithms in finite fields of small characteristic 
15:3015:55  Given a finite field K a generator of g of K^* and another element h of K^*, solving the discrete logarithm problem consists of finding an integer x ∈ Z such that g^x = h. Its connection to many cryptographic protocols has motivated a large amount of research intended to find efficient algorithms to solve this problem. Recently the work of A. Joux has led to algorithms significantly faster than the previous ones over “many” finite fields of small characteristic (i.e. finite fields whose characteristic is much smaller than the cardinality). These algorithms have quasipolynomial complexity and work over finite fields of small characteristic admitting a particular kind of presentation. Unfortunately it is not known which finite fields admit this kind of presentation, thus it is not proven that these algorithms can be applied in all the finite fields of small characteristic. In the talk we will define a new kind of presentation for finite fields, based on elliptic curves, and we will describe a new algorithm, based on Joux’s ideas, that works over finite fields admitting a presentation of this new kind. This algorithm is also quasipolynomial and it is easy to prove that it can actually be applied to all finite fields of small characteristic. 
Diane Maclagan (Warwick)  Valuated matroids in tropical geometry 
16:0016:55  Tropical geometry allows algebraic varieties to be studied using combinatorial and polyhedral techniques. In this talk I will highlight the role of matroids in tropical geometry, with a particular emphasis on joint work with Felipe Rincon, in which we use valuated matroids to define a subscheme of a tropical toric variety, building on work of Jeff and Noah Giansiracusa on tropicalizing subschemes. No knowledge of either matroids or tropical geometry will be assumed. 
17:0018.30  drinks 
18:30  dinner 
Friday  
Benjamin Nill (U Magdeburg)  The geometry of numbers of lattice polytopes 
9:3010:25  A lattice polytope is a polytope whose vertices have integer coordinates. Their study has grown into a very active field of research at the crossroads of convex, discrete and toric geometry, integer optimization, commutative algebra and enumerative combinatorics. In this survey talk, I will give an overview of recent developments in this research area. I will motivate where the ongoing interest in lattice polytopes comes from, what methods are used in their studies, and what the challenges are we cannot yet overcome. In particular, I will talk about current work to find sharp volume bounds, the continuing classification of lattice polytopes without interior lattice points, and the ongoing quest to understand their most important invariant  the Ehrhart polynomial  that counts the number of lattice points in their dilates. 
10:3011:00  coffee 
Leon Groot Bruinderink (TU/e)  Improving Sidechannel Attacks on Latticebased Cryptography 
11:0011:25  In the search for postquantum secure alternatives to RSA and ECC, latticebased cryptography appears to be an attractive and efficient option. A particularly interesting latticebased signature scheme is BLISS, offering key and signature sizes in the range of RSA moduli. A range of works on efficient implementations of BLISS is available, and the scheme has seen a first realworld adoption in strongSwan, an IPsecbased VPN suite. In contrast, the implementationsecurity aspects of BLISS, and latticebased cryptography in general, are still largely unexplored. At CHES 2016, Groot Bruinderink et al. presented the first sidechannel attack on BLISS, thus proving that this topic cannot be neglected. Nevertheless, their attack has some limitations. First, the technique is demonstrated via a proofofconcept experiment that was not performed under realistic attack settings. Furthermore, the attack does not apply to BLISSB, an improved variant of BLISS and also the default option in strongSwan. This problem also applies to later works on implementation security of BLISS. In this work, we solve both of the above problems. We present a new sidechannel keyrecovery algorithm against both the original BLISS and the BLISSB variant. Our keyrecovery algorithm draws on a wide array of techniques, including learningparity with noise, integer programs, maximimum likelihood tests, and a latticebasis reduction. With each application of a technique, we reveal additional information on the secret key culminating in a complete key recovery. Finally, we show that cache attacks on postquantum cryptography are not only possible, but also practical. We mount an asynchronous cache attack on the productiongrade BLISSB implementation of strongSwan. The attack recovers the secret signing key after observing roughly 6,000 signature generations. 
Milan Lopuhaä (RU)  Integral forms of reductive algebraic groups 
11:3011:55  Let G be a reductive algebraic group over a number field or a padic field K with ring of integers R, and let V be a faithful representation of G. Then a lattice L in V (i.e. a locally free Rsubmodule of maximal rank) determines a model of G over R. One may wonder to what extent one can recover L if this model is known. In this talk I will show that, up to some natural equivalence relation, there are only finitely many lattices yielding the same integral model. 
12:0013:00  lunch 
Christine van Vredendaal (TU/e)  Finding short generators in multiquadratic number fields 
13:0013:25  Finding a short element g of a number field, given the ideal generated by g, is a classic problem in computational algebraic number theory. Solving this problem recovers the private key in cryptosystems introduced by Gentry, SmartVercauteren, GentryHalevi, GargGentryHalevi, et al. Work over the last few years has shown that for some number fields this problem has a surprisingly low postquantum security level i.e. can be solved in polynomial time with a quantum computer. In this talk I will show that for multiquadratic number fields this problem can be solved in quasipolynomial time without a quantum computer. 
Anna Somoza Henares (UL, UPC Barcelona)  Construction of Picard curves with CM 
13:3013:55  The Schottky problem wonders about which principally polarized abelian varieties arise as Jacobians of curves. There exists a natural morphism between the moduli space of curves of genus g and the moduli space of principally polarized abelian varieties of dimension g, so by counting dimensions one realizes that the Schottky problem has a positive answer for g ≤ 3. However, we can still consider the effective version of the question, which seeks to determine such a curve whenever there is one. There are methods for the construction of such curves in genus 2 and genus 3, when assuming that the curve has complex multiplication by the maximal order of a certain field. In this talk we will see the current situation for genus 3 and we will focus on the family of Picard curves, giving a conjectural list of models defined over Q and possible generalizations of the method. 
14:0014:30  tea 
Neil Olver (VU)  Generalized flow, the net present value problem, and an open question in arithmetic computation 
14:3015:25  The maximum generalized flow problem is a classical generalization of maximum flow where flow is scaled as it traverses each arc, and has been intensively studied for the past few decades. Only very recently, Végh gave a "strongly polynomial" algorithm for this problem  an algorithm that is efficient in a certain refined sense. We give a new strongly polynomial algorithm that is both substantially faster and dramatically simpler. I will discuss the implications of our result to a classical problem in project scheduling, and a seemingly basic open algorithmic question in arithmetic that our work brings to light. (Includes joint work with L. Végh, as well as J. Correa, A. Schulz and L. Végh). 
15:30  end of the symposium 