CWI Cryptology Group

Abstract: An isogeny graph is a graph whose vertices are isogenous abelian varieties and whose edges represent isogenies between them. The specific case of Jacobians of genus 2 curves defined over a finite field has applications in cryptography. What can be said about connectivity and expander properties of those graphs, when the edges correspond to computable isogenies of small, prime degree? Under the Generalized Riemann Hypothesis, these properties imply the random self-reducibility of the discrete logarithm problem on the Jacobians with maximal endomorphism ring.

Abstract: In 2013 the Discrete Logarithm Problem in finite fields of small characteristic enjoyed a rapid series of developments, starting with the heuristic polynomial-time relation generation method due to Gologlu, Granger, McGuire and Zumbragel, and culminating with the first heuristic quasi-polynomial algorithm (QPA) due to Barbulescu, Gaudry, Joux and Thome, which built upon an approach due to Joux. In 2014 Granger, Kleinjung and Zumbragel devised a way to extend the original GGMZ approach, resulting in a completely new QPA which has some interesting properties; in particular in some families of fields one can rigorously prove the complexity. In this talk we review these developments and compare the two QPAs.

Abstract: These days, hyperelliptic curves of genus 2 are taken into consideration for their possible usage in real life public key and pairing-based crypto systems. An interesting problem is the problem of generating a new genus 2 curve that satisfies certain cryptographic requirements. One way of solving this issue is the CM method that utilizes the so called Igusa class polynomials of rational coefficients. In case one needs to compute the Igusa polynomials, establishing the denominators of the coefficients improves significantly their computation time. In my presentation, I will focus on the Lauter-Viray algorithm for computing denominators of the Igusa class polynomials.

Abstract: I will present a heuristic algorithm for solving exact, as well as approximate, shortest vector and closest vector problems on lattices. The algorithm can be seen as a modified sieving algorithm for which the vectors of the intermediate sets lie in overlattices or translated cosets of overlattices. The key idea is hence to no longer work with a single lattice but consider problems in related lattices that are easier to solve. We initiate the algorithm by sampling very short vectors in an overlattice of the original lattice that admits a quasi-orthonormal basis and hence an efficient enumeration of vectors of bounded norm. Taking sums of vectors in the sample, we construct short vectors in the next lattice. Finally, we obtain solution vector(s) in the initial lattice as a sum of vectors of an overlattice. The complexity analysis relies on the Gaussian heuristic. This heuristic is backed by experiments in low and high dimensions that closely reflect these estimates when solving hard lattice problems in the average case. Joint work with Nicolas Gama and Antoine Joux (ANTS 2014)

Abstract: Lattice-based cryptography is a promising candidate for providing cryptographic functions that remain secure in a post-quantum era. The security of lattice-based schemes relies on the hardness of lattice problems such as the problem of finding short vectors in integral lattices. In this presentation, I will describe a new variant of the parallel Gauss sieve algorithm which can compute such short vectors. Furthermore, I will outline how to use the additional algebraic structure in the setting of ideal lattices by using the fast Fourier transform to speed up the computation of inner products between a vector and the rotations of another. This is joint work with Michael Naehrig (Microsoft Research) and Joop van de Pol (University of Bristol)

Abstract: Breaking the key of a single RSA cryptosystem may not be worth the effort. But breaking many RSA keys may become economically viable, due to Coppersmith's factorization factory from the early 1990s. In this talk I will discuss the practical potential along with some related, recently obtained results.