Programme of the DIAMANT symposium
Hotel Van der Valk, Veenendaal
28 and 29 May 2015


11:00-11:25 arrival and coffee
11:25-11:30 welcome
Leo van Iersel (TUD) Reconstructing evolutionary histories
A phylogenetic network is a directed graph that describes the evolutionary history of a set of objects. Such networks are especially relevant in biology, where the objects are different species, and in linguistics, where the objects are different languages. Reconstructing phylogenetic networks is significantly more challenging than the well-studied problem of reconstructing phylogenetic trees. I will discuss different approaches that have been proposed quite recently, including reconstructing a network from a collection of trees, from sequences and from smaller networks.
12:30-13:30 lunch
Abtien Javanpeykar (UL)
Radical Galois groups
13:30-13:55 Let K be a finite extension of Q. A radical Galois group over K is the Galois group of some field extension of K obtained by adjoining all radicals of finitely many elements of K. We state a theorem describing the structure of such groups, showing which topological groups arise as radical Galois groups over K. A main ingredient of the proof of this theorem is continuous cochain cohomology. We briefly show how the latter is used in the proof.
Zhao Sun (TiU)  Convergence analysis for Lasserre's measure-based hierarchy of upper bounds for polynomial optimization
14:00-14:25 We consider the problem of minimizing a polynomial over a compact set, and analyze a measure-based hierarchy of upper bounds proposed by Lasserre. This hierarchy is obtained by searching for an optimal probability density function which is a sum of squares of polynomials, so that the expectation is minimized. In this talk, we will show its rate of convergence. The main idea is to use the truncated Taylor series of the Gaussian distribution function.
Shin-Ichi Tanagawa (CWI) Matroids of group-labeled graphs in graph rigidity
A group-labeled graph is a graph whose oriented edges are labeled invertibly from a group. Two classes of matroids on group-labeled graphs, called frame matroids (Dowling geometries) and lift matroids, have been extensively studied. In this talk I will show extensions of these matroids in two ways. The first one is extending the rank function of each matroid based on submodular functions over the underlying groups, and another one is extending the canonical linear representation of the union of copies of a frame matroid or a lift matroid. It turns out that linear matroids of the latter extension are special cases of the first extensions. This work is motivated from recent research on the rigidity of graphs (bar-joint frameworks) with symmetries. I will show various examples of new matroids appeared in the analysis of the infinitesimal rigidity of graphs (frameworks) with a point group or a crystallographic symmetry.
15:00-15:30 tea
Sabine Burgdorf (CWI)  Polyhedral approximation of the completely positive semidefinite cone
15:30-15:55 The completely positive semidefinite cone $\mathcal{CS}_+^n$ is a generalization of the completely positive cone: it consists of all the nxn symmetric matrices that admit a Gram representation by positive semidefinite matrices of any size instead of Gram representations by nonnegative vectors. This cone is used by Laurent and Piovesan to model quantum graph parameters as conic optimization problems, and by Mancinska and Roberson to characterize the set of bipartite quantum correlations as projection of an affine section of it. We will present a hierarchy of polyhedral cones which covers the interior of $\mathcal{CS}_+^n$. This hierarchy will then be used for computing some variant of the quantum chromatic number by way of a linear program. Joint work with M. Laurent and T. Piovesan.
Sander Dahmen (VU Amsterdam) Congruent number curves and Lucas sequences
16:00-16:55 A standard technique for determining the perfect powers in a Lucas sequence combines bounds coming from linear forms in logarithms with local information obtained via Frey curves and modularity. The key to this approach is the fact that such a Diophantine problem can be translated into a ternary Diophantine equation over the rationals for which Frey curves are available. In this talk we consider shifted powers ($ax^n+b$) in Lucas sequences, which do not typically correspond to ternary equations over the rationals. However, they do, under certain hypotheses, lead to ternary equations over totally real fields, allowing us to employ Frey curves over those fields. We illustrate this approach by solving a specific case of such a shifted powers problem, which yields the final ingredient required in work of Bennett on integral points on congruent number curves. This is joint work with Michael Bennett, Maurice Mignotte, and Samir Siksek.
Noriko Yui (Queen's U, MPIM Bonn) Update on automorphy of Calabi-Yau varieties over Q

Let X be a Calabi-Yau variety of dimension d. We will focus on the cases where d ≤ 3. Calabi–Yau varieties of dimension 1, 2 are elliptic curves and K3 surfaces, respectively. The dimension 3 Calabi–Yau varieties are Calabi–Yau threefolds where one can observe, among other things, mirror symmetry in full force. I will consider Calabi–Yau varieties defined over Q. Our goal is to discuss the modularity/automorphy of the (l-adic) Galois representations associated to the d-th etale cohomology groups of these Calabi–Yau varieties. In the last two decades, the modularity has been established for Calabi–Yau varieties over Q, whose Galois representations are two-dimensional. In this talk, I will discuss the automorphy/modularity of higher dimensional Galois representations (e.g., of dimension > 2). I will present some examples in support of the modularity/automorphy focusing on the two (or three) situations: (1) when X is equipped with a large automorphism group, and the Galois representation of X splits into smaller dimensional pieces, (2) when X is of CM type, and (3) the intersection of (1) and (2).

17:45-19.00 drinks
19:00 dinner
Nadia Heninger (UPenn) How Diffie-Hellman fails in practice
9:00-9:55 We investigate the security of Diffie-Hellman key exchange as used in popular Internet protocols and find it to be less secure than widely believed. First, we present a novel flaw in TLS that allows a man-in-the-middle to downgrade connections to “export-grade” Diffie-Hellman. To carry out this attack, we implement the number field sieve discrete log algorithm. After a week-long precomputation for a specified 512-bit group, we can compute arbitrary discrete logs in this group in minutes. We find that 82% of vulnerable servers use a single 512-bit group, allowing us to compromise connections to 7% of Alexa Top Million HTTPS sites. In response, major browsers are being changed to reject short groups. We go on to consider Diffie-Hellman with 768- and 1024-bit groups. A small number of fixed or standardized groups are in use by millions of TLS, SSH, and VPN servers. Performing precomputations on a few of these groups would allow a passive eavesdropper to decrypt a large fraction of Internet traffic. In the 1024-bit case, we estimate that such computations are plausible given nation-state resources, and a close reading of published NSA leaks shows that the agency’s attacks on VPNs are consistent with having achieved such a break. We conclude that moving to stronger key exchange methods should be a priority for the Internet community.
Thijs Laarhoven (TUE) Sieving for shortest lattice vectors using locality-sensitive hashing
10:00-10:25 Most lattice-based cryptographic primitives rely on the shortest vector problem (SVP) on lattices being hard. To assess the computational hardness of SVP and breaking these schemes, one commonly relies on the estimated time complexity of enumeration for solving SVP. In 2001 the breakthrough work of Ajtai et al. showed that SVP can actually be solved faster in high dimensions, using a technique called sieving. Although this technique seemed impractical at first, various improvements have since shown that sieving may be competitive with enumeration after all. In this talk we will look at recent advances in sieving using a technique from nearest-neighbor searching called locality-sensitive hashing.
10:30-11:00 coffee
Sietse Ringers (RUG) A new, efficient and secure attribute-based credential scheme
11:00-11:25 A credential scheme is a set of cryptographic protocols in which an issuer can grant a credential to a user, who can then show it to other parties. This may allow the user to, for example, authenticate himself or prove that he has some property contained in the credential. Attribute-based credentials can contain several attributes; i.e., pieces of data, generally statements about the owner of the credential. In such a scheme, the user can selectively show some of the attributes contained in his credential, while hiding the others. The scheme should be such that only the issuer can create new credentials, and ideally, it should not be possible to tell if two transactions in which the same attributes were disclosed did or did not originate from the same credential (this is called unlinkability). A number of such attribute-based credential schemes exist. However, finding schemes that satisfy all of the above demands while still being sufficiently efficient for implementation on smart cards is something of a challenge. In this talk we present a new attribute-based credential scheme, based on bilinear pairings on elliptic curves and a cryptographic assumption called the Known Exponent Assumption, that is provably unforgeable, unlinkable, and suitable for smart cards.
Max Klimm (TU Berlin) The equilibrium existence problem for weighted congestion games
11:30-12:25 Weighted congestion games are a class of noncooperative games that constitute an elegant model for the resource usage by selfish players. In a weighted congestion game, we are given a finite set of resources and a strategy of each player is to choose a subset of them. The private cost of each player is the sum of the costs of the chosen resources which depends on the total weight of the players using them. It is known that weighted congestion games need not possess a pure Nash equilibrium, i.e. a strategy vector from which no player can profitably deviate. We give a complete characterization of the maximal set of cost functions that one can allow on the resources in order to guarantee the existence of a pure Nash equilibrium. Further results on the existence of pure Nash equilibria in related models are given.
12:30-13:30 lunch
Christine van Vreedendaal (TUE) Tighter, faster, simpler side-channel security evaluations beyond computing power
13:30-13:55 A Eurocrypt 2013 paper “Security evaluations beyond computing power: How to analyze side-channel attacks you cannot mount?” by Veyrat-Charvillon, Gérard, and Standaert proposed a “Rank Estimation Algorithm” (REA) to estimate the difficulty of finding a secret key given side-channel information from independent subkeys, such as the 16 key bytes in AES-128 or the 32 key bytes in AES-256. The lower and upper bounds produced by the algorithm are far apart for most key ranks. The algorithm can produce tighter bounds but then becomes exponentially slower; it also becomes exponentially slower as the number of subkeys increases. We introduce two better algorithms for the same problem. The first, the “Extended Rank Estimation Algorithm” (EREA), is an extension of REA using statistical sampling as a second step to increase the speed of tightening the bounds on the rank. The second, the “Polynomial Rank Outlining Algorithm” (PRO), is a new approach to computing the rank. PRO can handle a much larger number of subkeys efficiently, is easy to implement in a computer-algebra system such as Sage, and produces much tighter bounds than REA in less time.
Chitchanok Chuengsatiansup (TUE) Curve41417: Karatsuba revisited
14:00-14:25 The Diffie-Hellman (DH) key-exchange protocol is commonly and widely used to establish a shared secret. In elliptic-curve cryptography, the speed of DH relies on the speed of scalar multiplication, i.e., computing nP for a scalar n and a point P. Scalar multiplication is a very time-consuming operation. There has been a lot of research to improve the computational time. We have a recent paper "Curve41417: Karatsuba revisited" in CHES 2014 which introduced speed-record constant-time software to compute scalar multiplication for a very high security level, beyond $2^{200}$. In this talk, I will explain how the speedup was achieved. Main techniques that we use are utilizing the CPU's vector unit and choosing a radix smaller than the CPU word size to represent numbers. Karatsuba's method also plays a crucial role in our implementation.
14:30-15:00 tea

Matthias Mnich (U Bonn)

Combinatorial optimization above and below guaranteed values
15:00-15:55 Many fundamental combinatorial optimization problems exhibit the property that the value of an optimal solution grows asymptotically with the length of the input. As one is generally interested in algorithmically solving large instances, algorithms solving these instances always produce output of which a large part of which simply repeats the input. This is not very efficient, in particular if the problem to solve is NP-hard. To circumvent this, we seek algorithms solving NP-hard optimization problems in time that confines the expected combinatorial explosion to the small gain of the optimal objective over the lower bound generated from the instance size. We give a survey on this area, with many positive algorithmic and negative hardness results for fundamental problems like Max Sat, Max Cut, Max Independent Set, Min Vertex Cover, and Constraint Satisfaction.
16:00 end of the symposium


Mathematics cluster DIAMANT

Upcoming events

NMC 2020 and Diamant symposium
14-4-2020 - 16-4-2020

News - more news

Call for PhD project proposals

NWO has issued a cluster-wide call for PhD project proposals. Researchers can apply if they are employed (i.e., hold a salaried position) at a Dutch university or a research institute recognised by NWO, and also have an appointment period for at least the duration of the application procedure and the entire duration of the research for which the grant is being applied for.

Read more.

ERC Starting Grant for Jesper Nederlof

Jesper Nederlof (TU/e) has been awarded an ERC Starting Grant of almost 1.5 ME. Nederlof will design faster algorithms for hard computational problems in computer science. The grant provides the researcher with the opportunity to further elaborate his own ideas during a period of five years.

Read more.

Full professor position in Discrete Mathematics in Delft

Delft Institute of Applied mathematics, Delft University of Technology, seeks a full Professor in the field of Discrete Mathematics. A description of the position can be found here. The deadline for applications is January 15, 2019.

ERC Starting grant for Daniel Dadush

Daniel Dadush (CWI) has been awarded an ERC Starting Grant of 1.5 ME for his proposal ‘Towards a Quantitative Theory of Integer Programming’. With this grant, Dadush aims to revolutionize the understanding of integer programming (IP), the most popular method used today for finding optimal solutions to real-world optimization problems.

Read more.