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

Europe/Paris
En Ligne

En Ligne

https://greenlight.lal.cloud.math.cnrs.fr/b/oli-yhz-7hx
Olivier Blazy, Philippe Gaborit (Université de Limoges)
Description

Logo GDR IM

 

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.

    • 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)
    • 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)
    • 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)
    • 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)