IMB > Recherche > Séminaires
Le 17 janvier 2017
à 10:00
Séminaire de Théorie Algorithmique des Nombres
Salle 385
Damien Stehlé ENS Lyon
Tuple lattice sieving
Lattice sieving is asymptotically the fastest approach for solving the shortest vector problem (SVP) on Euclidean lattices. All known sieving algorithms for solving SVP require space which (heuristically) grows as $2^{0.2075n+o(n)}$, where n is the lattice dimension. In high dimensions, the memory requirement becomes a limiting factor for running these algorithms, making them uncompetitive with enumeration algorithms, despite their superior asymptotic time complexity. We generalize sieving algorithms to solve SVP with less memory. We consider reductions of tuples of vectors rather than pairs of vectors as existing sieve algorithms do. For triples, we estimate that the space requirement scales as $2^{0.1887n+o(n)}$. The naive algorithm for this triple sieve runs in time $2^{0.5661n+o(n)}$. With appropriate filtering of pairs, we reduce the time complexity to $2^{0.4812n+o(n)}$ while keeping the same space complexity. We further analyze the effects of using larger tuples for reduction, and conjecture how this provides a continuous tradeoff between the memory-intensive sieving and the asymptotically slower enumeration. Joint work with Shi Bai, Thijs Laarhoven
Le 14 mars 2017
à 10:00
Séminaire de Théorie Algorithmique des Nombres
Salle 385
Cécile Pierrot Centrum Wiskunde & Informatica\, Amsterdam
Nearly sparse linear algebra
Linear algebra is a widely used tool both in mathematics and computer science, and cryptography is no exception to this rule. Yet, it introduces some particularities, such as dealing with linear systems that are often sparse, or, in other words, linear systems inside which a lot of coefficients are equal to zero. We propose to enlarge this notion to nearly sparse matrices, characterized by the concatenation of a sparse matrix and some dense columns, and to design an algorithm to solve this kind of problems. Motivated by discrete logarithms computations on medium and high characteristic finite fields, the Nearly Sparse Linear Algebra bridges the gap between classical dense linear algebra problems and sparse linear algebra ones, for which specific methods have already been established. Our algorithm particularly applies on one of the three phases of NFS (Number Field Sieve) which precisely consists in finding a non trivial element of the kernel of a nearly sparse matrix.
Le 23 mai 2017
à 10:00
Séminaire de Théorie Algorithmique des Nombres
Salle 385
Christophe Petit Oxford
Post-quantum cryptography from supersingular isogeny problems?
We review existing cryptographic schemes based on the hardness of computing isogenies between supersingular isogenies, and present some attacks against them. In particular, we present new techniques to accelerate the resolution of isogeny problems when the action of the isogeny on a large torsion subgroup is known, and we discuss the impact of these techniques on the supersingular key exchange protocol of Jao-de Feo.
Le 30 mai 2017
à 10:00
Séminaire de Théorie Algorithmique des Nombres
Salle 385
Benjamin Wesolowski EPFL
Isogeny graphs of ordinary abelian varieties
Fix a prime number $\ell$. Graphs of isogenies of degree a power of $\ell$ are well-understood for elliptic curves, but not for higher-dimensional abelian varieties. We study the case of absolutely simple ordinary abelian varieties over a finite field. We analyse graphs of so-called $\mathfrak l$-isogenies, resolving that, in arbitrary dimension, their structure is similar, but not identical, to the ``volcanoes'' occurring as graphs of isogenies of elliptic curves. Specializing to the case of principally polarizable abelian surfaces, we then exploit this structure to describe graphs of a particular class of isogenies known as $(\ell, \ell)$-isogenies. These results lead to new, provable algorithms to navigate in isogeny graphs, with consequences for the CM-method in genus 2, for computing explicit isogenies, and for the random self-reducibility of the discrete logarithm problem in genus 2 cryptography.
Le 6 juin 2017
à 10:00
Séminaire de Théorie Algorithmique des Nombres
Salle 385
Guilhem Castagnos imb
Encryption Switching Protocols Revisited: Switching modulo p
Last year, Couteau, Peters and Pointcheval introduced a new primitive called encryption switching protocols, allowing to switch ciphertexts between two encryption schemes. If such an ESP is built with two schemes that are respectively additively and multiplicatively homomorphic, it naturally gives rise to a secure 2-party computation protocol. It is thus perfectly suited for evaluating functions, such as multivariate polynomials, given as arithmetic circuits. Couteau et al. built an ESP to switch between Elgamal and Paillier encryptions which do n ot naturally fit well together. Consequently, they had to design a clever variant of Elgamal over Z/nZ with a costly shared decryption. In this talk, we first present a conceptually simple generic construction for encryption switching protocols. We then give an efficient instantiation of our generic approach that uses two well-suited protocols, namely a variant of Elgamal in Z/pZ and the Castagnos-Laguillaumie encryption defined over class groups of quadrat ic fields which is additively homomorphic over Z/pZ. Among other advantages, this allows to perform all computations modulo a prime p instead of an RSA modulus. Overall, our solution leads to significant reductions in the number of rounds as well as the number of bits exchanged by the parties during the interactive protocols. We also show how to extend its security to the malici ous setting.
Le 13 juin 2017
à 10:00
Séminaire de Théorie Algorithmique des Nombres
Salle 385
Bernhard Schmidt Nanyang Technological University\, Singapore
The Anti-Field-Descent Method
A circulant Hadamard matrix of order $v$ is a matrix of the form \[H=\begin{pmatrix} a_1 & a_2 & \cdots & a_v \\ a_v & a_1 & \cdots & a_{v-1} \\ \cdots & \cdots & \cdots &\cdots \\ a_2 & a_3 & \cdots & a_1 \\ \end{pmatrix}\] with $a_i=\pm 1$ such that any two rows of $H$ are orthogonal with respect to the standard inner product. It is conjectured that there is no circulant Hadamard matrix of order larger than $4$.
Le 17 octobre 2017
à 10:00
Séminaire de Théorie Algorithmique des Nombres
Salle 385
Fredrik Johansson imb
Numerics of classical elliptic functions, elliptic integrals and modular forms
We review methods for validated arbitrary-precision numerical computation of elliptic functions and their inverses (the complete and incomplete elliptic integrals), as well as the closely related Jacobi theta functions and $\mathrm{SL}_2(\mathbb{Z})$ modular forms. A general strategy consists of two stages: first, using functional equations to reduce the function arguments to a smaller domain; second, evaluation of a suitable truncated series expansion. For elliptic functions and modular forms, one exploits periodicity and modular transformations for argument reduction, after which the rapidly convergent series expansions of Jacobi theta functions can be employed. For elliptic integrals, a comprehensive strategy pioneered by B. Carlson consists of using symmetric forms to unify and simplify both the argument reduction formulas and the series expansions (which involve multivariate hypergeometric functions). Among other aspects, we discuss error bounds as well as strategies for argument reduction and series evaluation that reduce the computational complexity. The functions have been implemented in arbitrary-precision complex interval arithmetic as part of the Arb library.
Le 24 octobre 2017
à 10:00
Séminaire de Théorie Algorithmique des Nombres
Salle 385
José Manuel Rodriguez Caballero Labri
Context-free languages in Algebraic Geometry and Number Theory.
Kassel and Reutenauer computed the zeta function of the Hilbert scheme of n points on a two-dimensional torus and showed it satisfies several number-theoretical properties via modular forms. Classifying the singularities of this rational function into zeros and poles, we define a word which contains a lot of number-theoretical information about n (the above-mentioned number of points). This nontrivial connection between natural numbers and words can be used to define many classical subsets of natural numbers in terms of rational and context-free languages (e.g. the set of semi-perimeters of Pythagorean triangles, the set of numbers such that any partition into consecutive parts has an odd number of parts). Also, some arithmetical functions can be described in way (e.g. the Erdös-Nicolas function, the number of middle divisors). Finally, this approach provides a new technique to prove number-theoretical results just using relationships among context-free languages.
Le 14 novembre 2017
à 10:00
Séminaire de Théorie Algorithmique des Nombres
Salle 385
Jean Kieffer ENS Paris
Accélération du protocole d'échange de clés de Couveignes-Rostovtsev-Stolbunov
Ce protocole d'échange de clés est fondé sur la théorie de la multiplication complexe: un ordre dans un corps quadratique imaginaire agit sur un ensemble de courbes elliptiques ordinaires isogènes définies sur un corps fini. Pour instancier le protocole, on est amené à calculer des isogénies de différents degrés entre ces courbes à l'aide des algorithmes développés pour le comptage de points. Ce cryptosystème peut être accéléré par un bon choix de courbe elliptique initiale, notamment par la présence de points de torsion rationnels, et l'on présente une méthode de recherche de telles courbes.
Le 20 novembre 2017
à 14:00
Séminaire de Théorie Algorithmique des Nombres
Salle 385
Christian Klein
Computational approach to compact Riemann surfaces
A purely numerical approach to compact Riemann surfaces starting from plane algebraic curves is presented. The critical points of the algebraic curve are computed via a two-dimensional Newton iteration. The starting values for this iteration are obtained from the resultants with respect to both coordinates of the algebraic curve and a suitable pairing of their zeros. A set of generators of the fundamental group for the complement of these critical points in the complex plane is constructed from circles around these points and connecting lines obtained from a minimal spanning tree. The monodromies are computed by solving the de ning equation of the algebraic curve on collocation points along these contours and by analytically continuing the roots. The collocation points are chosen to correspond to Chebychev collocation points for an ensuing Clenshaw–Curtis integration of the holomorphic differentials which gives the periods of the Riemann surface with spectral accuracy. At the singularities of the algebraic curve, Puiseux expansions computed by contour integration on the circles around the singularities are used to identify the holomorphic differentials. The Abel map is also computed with the Clenshaw–Curtis algorithm and contour integrals. As an application of the code, solutions to the Kadomtsev–Petviashvili equation are computed on non-hyperelliptic Riemann surfaces.
Le 28 novembre 2017
à 10:00
Séminaire de Théorie Algorithmique des Nombres
Salle 385
Frank Vallentin
Coloring the Voronoi tessellation of lattices
We define the chromatic number of a lattice: It is the least number of colors one needs to color the interiors of the cells of the Voronoi tesselation of a lattice so that no two cells sharing a facet are of the same color. We compute the chromatic number of the irreducible root lattices and for this we apply a generalization of the Hoffman bound.
Séminaire de Théorie Algorithmique des Nombres
Responsables : Razvan Barbulescu et Wessel Van Woerden
Afficher 2022 - 2021 - 2020 - 2019 - 2018 - 2017 - 2016 - 2015 - antérieurs
Institut de Mathématiques de Bordeaux UMR 5251
Université de Bordeaux
351, cours de la Libération - F 33 405 TALENCE
Tél: +33 (0)5 40 00 60 70
institut
math.u-bordeaux.fr
