RISC Seminars
Archives: [2019] [2018] [2017] [2016] [2015] [2014] [2013] [2012] [2011] [2010] [2009] [2008] [2007] [2006] [2005] [2004] [List of Speakers](To receive information about upcoming seminars, register for the RISC mailing list.)
[print]
Special LACAL@RISC Seminar on Cryptologic Algorithms
Date:  February 6 
Location:  Euler room (Z009), CWI 
Schedule:  
10:3011:00  Benjamin Wesolowski (LACAL, EPFL): Random SelfReducibility of the Discrete Logarithm Problem in Genus 2 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 selfreducibility of the discrete logarithm problem on the Jacobians with maximal endomorphism ring.

11:0011:15  Coffee break 
11:1512:00  Rob Granger (LACAL, EPFL): A tale of two QPAs Abstract: In 2013 the Discrete Logarithm Problem in finite fields of small
characteristic enjoyed a rapid series of developments, starting with the
heuristic polynomialtime relation generation method due to Gologlu,
Granger, McGuire and Zumbragel, and culminating with the first heuristic
quasipolynomial 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.

12:0013:45  Lunch break 
13:4514:15  Alina Dudeanu (LACAL, EPFL): Computing Denominators of Igusa Class Polynomials Abstract: These days, hyperelliptic curves of genus 2 are taken into consideration for their possible usage in real life public key and pairingbased 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 LauterViray algorithm for computing denominators of the Igusa class polynomials.

14:1514:45  Anja Becker (LACAL, EPFL): A Sieve Algorithm Based on Overlattices 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 quasiorthonormal 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)

14:4515:00  Coffee break 
15:0015:30  Joppe Bos (NXP Semiconductors, exLACAL): Sieving for Shortest Vectors in Ideal Lattices: a Practical Perspective Abstract: Latticebased cryptography is a promising candidate for providing
cryptographic functions that remain secure in a postquantum era. The security
of latticebased 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)

15:4516:30  Arjen Lenstra (LACAL, EPFL): Factorization Factories 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.

0.03929s