L’École de Jeunes Chercheurs en Informatique Mathématique 2021

7 juin 2021, 10:00 → 10 juin 2021, 14:00 Europe/Paris

En Ligne

Olivier Blazy, Philippe Gaborit (Université de Limoges)

 

Les grands thèmes du GDR IM sont l’algorithmique, la combinatoire, le
calcul formel, l’arithmétique, la protection de l’information, la
géométrie, la logique et la complexité.

L’une des vocations de ces EJCIM est de promouvoir l’ouverture des jeunes chercheurs à ces thématiques et de renforcer la cohésion scientifique de la communauté Informatique Mathématique.

Le public des EJCIM est prioritairement celui des doctorants et jeunes docteurs du GDR IM, mais aussi des étudiants de Master ou des chercheurs d’autres GDR.

lundi 7 juin

Quantique: Algorithmes quantiques de base

Exposés longs sur le quantique

Président de session: Dr François Arnault (Université de Limoges)

1 Algorithmes quantiques de base

Cet exposé vise à présenter les algorithmes quantiques de base, en particulier ceux ayant un impact potentiel en cryptographie. Parmi eux, les algorithmes de type Simon et Grover qui permettent d'accélérer la recherche de valeurs vérifiant une propriété particulière (par exemple une clé cryptographique), et les algorithmes basés sur l'utilisation de
la transformée de Fourier, comme ceux introduits par Shor qui permettent de factoriser des entiers ou de calculer des logarithmes discrets en temps polynomial.

Orateur: Dr François Arnault (Université de Limoges)

Quantique: Introduction aux codes correcteurs quantiques

Exposés longs sur le quantique

Présidents de session: Prof. Gilles Zemor (Université de Bordeaux), Prof. Philippe Gaborit (Université de Limoges)

2 Introduction aux codes correcteurs quantiques

Un code correcteur quantique peut être vu comme la donnée de deux codes correcteurs classiques. Dans la théorie classique, les codes dits LDPC (Low Density Parity Check) font partie des plus anciens codes connus: ils sont munis d'algorithmes de décodage efficaces et permettent à leurs rendements d'atteindre constructivement la limite de Shannon. Ils ont ainsi peu de rivaux, à la fois en théorie et en pratique.
On s'attend à ce que l'ordinateur quantique utilise des analogues quantiques des codes LDPC. Ces codes sont cependant nettement moins bien compris que leurs versions classiques.
Ils sont beaucoup moins faciles à construire, et les algorithmes
de décodage classiques ne s'adaptent pas naturellement.
Leurs constructions impliquent notamment une structure topologique assez forte.
Nous ferons une introduction au domaine des codes LDPC quantiques, souligneront les similarités et les différences avec la théorie classique, et évoquerons des progrès très récents.

Orateur: Prof. Gilles Zemor (Univeristé de Bordeaux)

Quantique: Programmation quantique pratique

Exposés longs sur le quantique

Président de session: Dr Simon Martiel (ATOS)

3 Programmation quantique pratique

Comme en informatique classique, il y a un fossé entre la description théorique d’un algorithme quantique et son implémentation en terme de séquence d’instructions quantiques. Dans ce cours, nous utiliserons une librairie de description de circuits quantiques (l’extension naturelle
des circuits booléens classique à un modèle quantique) pour implémenter quelques algorithmes. En particulier, nous rappellerons les principes algorithmiques derrière l’algorithme de Grover et implémenterons quelques oracles pour résoudre différents problèmes d’optimisation. Si le temps le permet, nous aborderons d’autres algorithmes de la littérature, comme l’algorithme de Bernstein Vazirani.

Orateur: Simon Martiel (atos)

mardi 8 juin

Calcul Formel: Computer algebra for lattice path combinatorics

Exposés longs sur le calcul formel

Président de session: Dr Alin Bostan (Inria)

4 Computer algebra for lattice path combinatorics

Classifying lattice walks in restricted lattices is an important problem in enumerative combinatorics. Recently, computer algebra has been used to explore and to solve a number of difficult questions related to lattice walks. We give an overview of recent results on structural properties and explicit formulas for generating functions of walks in the quarter plane, with an emphasis on the algorithmic methodology.

Orateur: Dr Alin Bostan (Inria)

Calcul Formel: Matrices polynomiales : accélérer et exploiter leur algorithmique

Exposés longs sur le calcul formel

Président de session: Vincent Neiger

5 Matrices polynomiales : accélérer et exploiter leur algorithmique

Les matrices dont les coefficients sont des polynômes à une variable sont un objet mathématique de base, qui se retrouve au coeur d'approches algorithmiques fondamentales du calcul formel : résolution de systèmes linéaires creux ou structurés, calculs d'approximants et d'interpolants, division avec reste pour les polynômes à deux variables, ...
Après une présentation du contexte, nous donnerons une vue d'ensemble des progrès récents concernant les calculs
exacts efficaces avec ce type de matrices. Ensuite, nous verrons comment ces résultats ont été exploités afin d'aboutir à des avancées majeures sur la complexité de problèmes qui n'impliquent pas nécessairement les matrices polynomiales a
priori : la composition modulaire de polynômes, et le calcul du polynôme caractéristique d'une matrice à coefficients dans un corps.

Orateur: Dr Vincent Neiger (Université de Limoges)

Présentations Doctorants: Présentations Etudiants 1

6 Algorithme de dénombrement de points fixes

Orateur: M. Charles Balthazar

7 On the Besicovitch-Stability of Noisy Random Tilings

we introduce a noisy framework for SFTs, allowing some amount of forbidden patterns to appear. Using the Besicovitch distance, which permits a global comparison of configurations, we then study the closeness of noisy measures to non-noisy ones as the amount of noise goes to 0. Our first main result is the full classification of the (in)stability in the one-dimensional case. Our second main result is a stability property under Bernoulli noise for higher-dimensional periodic SFTs, which we finally extend to an aperiodic example through a variant of the Robinson tiling.

Orateur: Léo Gayral (Université de Toulouse)

8 Asymptotic probability of connected labeled objects and virtual species

There are a number of combinatorial structures that admit a notion of connectivity, including graphs
as the most commonly used example. We are interested in the probability that a random labeled object
is connected, as its size tends to in?nity. We will show that the asymptotics for these probabilities can
be obtained in a common manner and that asymptotic coe?cients have a combinatorial meaning in terms
of virtual species. Moreover, we will show how to get the asymptotic probability that a random labeled
object has a given number of connected components, and we will indicate the combinatorial meaning of the
coe?cients involved in the asymptotic expansions.
This is ongoing work joint with Thierry Monteil.

Orateur: Khaydar Nurligareev (Université Paris 13)

9 Construction de coloriages de produits de groupes en dynamique symbolique

Orateur: Sacha Huriot (ENS Paris Scalay)

mercredi 9 juin

Présentations Doctorants: Présentations Doctorants 2

10 Aperiodic Subshifts of Finite Type on Baumslag-Solitar Groups

The Cayley graph of a group is a way to visualize its structure as a graph. A Subshift of Finite Type (SFT) on a group is the set of all the colorings of the Cayley graph that use a given finite number of colors and respect a given finite number of adjacency rules between colored vertices. Initially studied on $\mathbb{Z}$ as tilings of the biinfinite line with dominoes, the notion was extended to $\mathbb{Z}^2$ using square tiles with colored edges called Wang tiles, then to any $\mathbb{Z}^d, d>2$; and more recently to any group of finite type.

On $\mathbb{Z}$, any SFT must contain a periodic coloring -- but this becomes false with $\mathbb{Z}^2$, on which there are some SFTs with only non-periodic colorings. On $\mathbb{Z}^d, d>2$, two distinct and finer notions of aperiodicity arise. This talk will detail these results, then proceed to prove, using notably substitutions on biinfinite words, that these finer notions of aperiodicity are also present for SFTs on some Baumslag-Solitar groups, that are two-generator one-relator groups that resemble $\mathbb{Z}^2$.

This is a joint work with E. Moutot.

Orateur: Julien Esnay (ENS-Lyon)

11 Augmented Broadcast Encryption with constant size ciphertext, from standard assumption

Orateur: Anaïs Barthoulot (Orange)

Cryptographie: Cryptographie post-quantique: alternatives et enjeux

Exposé long sur la Cryptographie

Président de session: Prof. Philippe Gaborit (Université de Limoges)

12 Cryptographie post-quantique: alternatives et enjeux

Depuis l'apparition de l'algorithme de factorisation de P. Shor
en 1994, on sait que l'existence d'un ordinateur quantique suffisamment puissant peut amener à la cryptanalyse immédiate de tous les systèmes cryptographiques actuels basés sur la théorie des nombres utilisés en pratique comme les algorithmes RSA, les systèmes basés sur le logarithme
discret sur Z/pZ ou encore sur les courbes elliptiques. Dans cet exposé nous ferons le point sur les différentes alternatives pour resister à ce type d'attaques et notamment la cryptographie basée sur les réseaux, les codes correcteurs (en Hamming et en métrique rang) ou encore les signatures basées sur les fonctions de hachages ou encore la cryptographie multivariée. Nous considérerons aussi les enjeux au niveau du concours international lancé par le NIST (institut des standards amériain) sur la crypotgraphie post-quantique.

Orateur: Prof. Philippe Gaborit (Université de Limoges)

Cryptographie: Preuves Implicites

Exposé long sur la Cryptographie

Président de session: Olivier Blazy

13 Preuves Implicites

Les Smooth Projective Hash Functions ont été introduites en 2002 par Cramer et Shoup pour permettre de faire du chiffrement CC2.
Nous allons montrer comment les classifier, comment en construire et comment étendre le champ des langages pouvant être générés.
Pour celà, nous les étudions tout d’abord sous l’angle classique des courbes elliptiques mais également des réseaux euclidiens, ou même de la cryptographie à base de codes. Ensuite nous proposons de nouvelles méthodologies pour construire et prouver des protocoles d’échanges de clé authentifiés (que nous regroupons derrière le concept de LAKE : Language Based Authenticated Key Exchange, Echange de clé authentifié par un langage), et des protocoles asymétriques (regroupés sous le concept d’OLBE : Oblivious Language-Based Envelope, Enveloppe Inconsciente basée sur un langage). A chaque fois, nous regarderons les
fonctionnalités idéales, des instantiations génériques et montrons comment instantier les diverses briques pour générer des protocoles sûrs et le plus efficaces possibles. Bien que développées de façon générique, nous remarquons que nos instantiations conduisent à des protocoles extrêmement efficaces même en cas de corruptions adaptatives, et que ces constructions se transposent presque naturellement aux hypothèses post-quantiques.

Orateur: Olivier Blazy

Syndrome de l'imposture

Président de session: Dr Natacha Portier (Ens-Lyon)

14 Atelier sur le syndrome d'imposture

Avez-vous déjà entendu parler du syndrome d'imposture ?
Dans cet atelier interactif, nous verrons ce que c'est, d'où ça vient et ce qu'on peut y faire.

Vous pourrez participer de manière anonyme dans un navigateur ou avec votre téléphone (j'utilise l'outil wooclap).

Orateur: Natacha Portier (ENS Lyon)

jeudi 10 juin

Présentations Doctorants: Présentations Doctorants 3

Président de session: Olivier Blazy

15 Algorithmes de fractions continues multidimensionnelle

Orateur: Dr Mélodie Andrieu-Estevez (Institut de Mathématiques de Marseille)

Verification Formelle: Analyse symbolique de protocoles cryptographiques, modélisation logique, et algorithme de vérification

Exposés longs de Vérification Formelle

Présidents de session: Dr Lucca Hirschi (Inria), Dr Vincent Cheval (Inria)

16 Analyse symbolique de protocoles cryptographiques, modélisation logique, et algorithme de vérification

Orateurs: Dr Lucca Hirschi (Inria), Dr Vincent Cheval (Inria)