Programme of the DIAMANT symposium
Hotel Van der Valk, Veenendaal
28 and 29 May 2015
Thursday  
11:0011:25  arrival and coffee 
11:2511:30  welcome 
Leo van Iersel (TUD)  Reconstructing evolutionary histories 
11:3012:25 
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 wellstudied 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:3013:30  lunch 
Abtien Javanpeykar (UL) 
Radical Galois groups 
13:3013: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 measurebased hierarchy of upper bounds for polynomial optimization 
14:0014:25  We consider the problem of minimizing a polynomial over a compact set, and analyze a measurebased 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. 
ShinIchi Tanagawa (CWI)  Matroids of grouplabeled graphs in graph rigidity 
14:3014:55 
A grouplabeled graph is a graph whose oriented edges are labeled invertibly from a group. Two classes of matroids on grouplabeled 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 (barjoint 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:0015:30  tea 
Sabine Burgdorf (CWI)  Polyhedral approximation of the completely positive semidefinite cone 
15:3015: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:0016: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 CalabiYau varieties over Q 
17:0017:40 
Let X be a CalabiYau 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 (ladic) Galois representations associated to the dth 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 twodimensional. 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:4519.00  drinks 
19:00  dinner 
Friday  
Nadia Heninger (UPenn)  How DiffieHellman fails in practice 
9:009:55  We investigate the security of DiffieHellman 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 maninthemiddle to downgrade connections to “exportgrade” DiffieHellman. To carry out this attack, we implement the number field sieve discrete log algorithm. After a weeklong precomputation for a specified 512bit group, we can compute arbitrary discrete logs in this group in minutes. We find that 82% of vulnerable servers use a single 512bit 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 DiffieHellman with 768 and 1024bit 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 1024bit case, we estimate that such computations are plausible given nationstate 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 localitysensitive hashing 
10:0010:25  Most latticebased 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 nearestneighbor searching called localitysensitive hashing. 
10:3011:00  coffee 
Sietse Ringers (RUG)  A new, efficient and secure attributebased credential scheme 
11:0011: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. Attributebased 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 attributebased 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 attributebased 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:3012: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:3013:30  lunch 
Christine van Vreedendaal (TUE)  Tighter, faster, simpler sidechannel security evaluations beyond computing power 
13:3013:55  A Eurocrypt 2013 paper “Security evaluations beyond computing power: How to analyze sidechannel attacks you cannot mount?” by VeyratCharvillon, Gérard, and Standaert proposed a “Rank Estimation Algorithm” (REA) to estimate the difficulty of finding a secret key given sidechannel information from independent subkeys, such as the 16 key bytes in AES128 or the 32 key bytes in AES256. 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 computeralgebra system such as Sage, and produces much tighter bounds than REA in less time. 
Chitchanok Chuengsatiansup (TUE)  Curve41417: Karatsuba revisited 
14:0014:25  The DiffieHellman (DH) keyexchange protocol is commonly and widely used to establish a shared secret. In ellipticcurve 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 timeconsuming 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 speedrecord constanttime 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:3015:00  tea 
Matthias Mnich (U Bonn) 
Combinatorial optimization above and below guaranteed values 
15:0015: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 NPhard. To circumvent this, we seek algorithms solving NPhard 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 