DIAMANT Symposium Spring 2017

Great Tolls: How to induce optimal flows under strategic link owners

Network pricing games provide a framework for modeling real-world 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 single-commodity series-parallel networks. Starting from the same linear program, we obtain multiplicative approximation results for arbitrary networks with polynomial latencies of bounded degree, while in the single-commodity 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.

Valuated matroids in tropical geometry

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.

The geometry of numbers of lattice polytopes

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.

Generalized flow, the net present value problem, and an open question in arithmetic computation

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).

Improving Side-channel Attacks on Lattice-based Cryptography

In the search for post-quantum secure alternatives to RSA and ECC, lattice-based cryptography appears to be an attractive and efficient option. A particularly interesting lattice-based 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 real-world adoption in strongSwan, an IPsec-based VPN suite. In contrast, the implementation-security aspects of BLISS, and lattice-based cryptography in general, are still largely unexplored. At CHES 2016, Groot Bruinderink et al. presented the first side-channel attack on BLISS, thus proving that this topic cannot be neglected. Nevertheless, their attack has some limitations. First, the technique is demonstrated via a proof-of-concept experiment that was not performed under realistic attack settings. Furthermore, the attack does not apply to BLISS-B, 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 side-channel key-recovery algorithm against both the original BLISS and the BLISS-B variant. Our key-recovery algorithm draws on a wide array of techniques, including learning-parity with noise, integer programs, maximimum likelihood tests, and a lattice-basis 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 post-quantum cryptography are not only possible, but also practical. We mount an asynchronous cache attack on the production-grade BLISS-B implementation of strongSwan. The attack recovers the secret signing key after observing roughly 6,000 signature generations.

Constructing a consensus phylogeny from a leaf-removal distance

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.

Using (noncommutative) polynomial optimization to bound matrix factorization ranks

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 cpsd-rank (completely positive semidefinite rank) of a matrix. The cpsd-rank 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 cp-rank and nonnegative rank of a matrix, and I will compare this to existing techniques.

Discrete logarithms in finite fields of small characteristic

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 quasi-polynomial complexity and work over finite fields of small characteristic admitting a particular kind of presentation. If every finite field K of small characteristic could be embedded in a slightly larger field K admitting this kind of presentation then we could deduce that the discrete logarithm problem over finite fields of small characteristic has at most quasi-polynomial complexity. Unfortunately this has not yet been proven. 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 quasi-polynomial and it is easy to prove that every finite field K of small characteristic could be embedded in a slightly larger field K admitting a presentation of this new kind.

Integral forms of reductive algebraic groups

Let G be a reductive algebraic group over a number field or a p-adic 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 R-submodule 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.

Constructing genus 2 curves with a prescribed number of points

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.

Construction of Picard curves with CM

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.

Finding short generators in multiquadratic number fields

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, Smart-Vercauteren, Gentry-Halevi, Garg-Gentry-Halevi, et al. Work over the last few years has shown that for some number fields this problem has a surprisingly low post-quantum 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 quasi-polynomial time without a quantum computer.