- 10:00. Martino Borello, Université Paris 8 – LAGA
The geometry of linear codes and some recent applications
It is well-known that a nondegenerate linear code of length n and dimension k can be associated with a set of n points (with multiplicities) in a projective space of dimension k-1. Some coding-theoretical properties can be interpreted geometrically. This perspective connects MDS codes to problems involving arcs in projective spaces (the famous MDS conjecture was initially formulated as a problem in projective geometry by Segre), covering problems to saturating sets, minimal codes to strong blocking sets, and so on. In this talk, we will illustrate some recent results obtained by using this geometrical approach for Hamming-metric codes and outline how this can be generalized to other metrics, such as the rank and sum-rank metrics.
La géométrie des codes linéaires et quelques applications récentes
Il est bien connu qu’un code linéaire non dégénéré de longueur n et de dimension k peut être associé à un ensemble de n points (avec multiplicités) dans un espace projectif de dimension k−1. Certaines propriétés des codes peuvent être interprétées géométriquement. Cette perspective relie les codes MDS aux problèmes impliquant des arcs dans les espaces projectifs (la fameuse conjecture MDS a été initialement formulée comme un problème de géométrie projective par Segre), les problèmes de recouvrement aux ensembles saturants, les codes minimaux aux ensembles bloquants forts, etc. Dans cette présentation, nous illustrerons certains résultats récents obtenus en utilisant cette approche géométrique pour les codes en métrique de Hamming et nous esquisserons à la fin comment cela peut être généralisé à d’autres métriques, telles que les métriques rang et somme-rang.
- 11:00. Antonin Leroux, DGA-MI et Université de Rennes
SQIsign2D-West The Fast, the Small, and the Safer
In this talk, we will present SQIsign2D-West, a variant of SQIsign using two-dimensional isogeny representations. SQIsignHD was the first variant of SQIsign to use higher dimensional isogeny representations with an unpractical eight-dimensional variant geared towards provable security, and a four-dimensional variant geared towards efficiency. In particular, it has significantly faster signing times than SQIsign, but slower verification owing to the complexity of the four dimensional representation.
A dimension 2 variant was already mentioned at the time but several obstacles remained to make it possible.
In this work, we introduce new algorithmic tools that make two-dimensional representations a viable alternative. These lead to a signature scheme with sizes comparable to SQIsignHD, slightly slower signing than SQIsignHD but still much faster than SQIsign, and the fastest verification of any known variant of SQIsign. We achieve this without compromising on the security proof: the assumptions behind SQIsign2D-West are similar to those of the eight-dimensional variant of SQIsignHD. Additionally, like SQIsignHD, SQIsign2D-West favourably scales to high levels of security. Concretely, for NIST level I we achieve signing times of 80 ms and verifying times of 4.5 ms, using optimised arithmetic based on intrinsics available to the Ice Lake architecture. For NIST level V, we achieve 470 ms for signing and 31 ms for verifying.
- 13:45. Cécile Pierrot, Inria / CNRS / Loria / Université de Lorraine
Y a-t-il encore, au XXI° siècle, de vieux documents historiques à déchiffrer ?
Aussi surprenant que cela puisse paraitre, oui. Il arrive que, dans un carton d’archives, l’historien butte soudainement sur un document chiffré resté tel qu’il a été envoyé. L’étonnant n’est pas de trouver ce genre de missive, et vous le savez-bien, nous chiffrons depuis des millénaires. Non, ce qui surprend, c’est que le destinataire officiel, soit n’ait pas procédé au déchiffrement, soit n’ait pas conservé et joint celui-ci. Les clefs des chiffres, également, ne sont pratiquement jamais jointes dans les archives, et si nous en trouvons encore avec émotion, elles ne comportent que rarement les mentions de leur propriétaire. De ce fait, de très nombreux documents historiques demeurent inexploités, car incompréhensibles. Ajoutez à ceci l’absence, pour le moment, de méthodes d’intelligence artificielle ad hoc capables de transcrire les dizaines de pages chiffrés par des glyphes propres à chaque auteur, ainsi que la perte des techniques de cryptanalyse au cours du temps, et enfin la difficulté à faire le pont entre plusieurs disciplines (histoire, linguistique, cryptographie, intelligence artificielle) ; vous comprendrez alors le chemin qu’il nous reste à parcourir. Cet exposé présentera des collaborations en cours à propos de lettres et de télégrammes du XVI° au XIX° siècle. Je vous emmènerai de l’Europe de Charles Quint à la guerre d’indépendance des Etats-Unis, en passant par les troubles post-indépendance du Brésil.
In the 21st century, are there still old historical documents to be deciphered?
Surprisingly, yes. Sometimes, in a box of archives, the historian suddenly comes across an encrypted document in the form in which it was sent. It’s not surprising to find this kind of missive – as you well know, we’ve been encrypting documents for thousands of years. No, what is surprising is that the official recipient either did not decrypt it, or did not keep it and attach it. The keys to the ciphers are almost never included in the archives, and if we still find some with emotion, they rarely include the name of their owner. As a result, many historical documents remain unexploited because they are incomprehensible. Add to this the absence, for the moment, of ad hoc artificial intelligence methods capable of transcribing the dozens of pages encrypted by glyphs specific to each author, as well as the loss of cryptanalysis techniques over time, and finally the difficulty of bridging several disciplines (history, linguistics, cryptography, artificial intelligence), and you will understand the road we still have to travel. This talk will present current collaborations on letters and telegrams from the 16th to the 19th century. I’ll be taking you from the Europe of Charles V to the American War of Independence, via the post-independence troubles in Brazil.
- 14:45. Jules Baudrin, Inria Paris.
Geometrical structures among known APN functions
An almost perfect non-linear (APN) function is a function offering optimal resistance against differential cryptanalysis, which is among the most powerful techniques to attack or assess the security of a block cipher. APN functions have therefore been carefully analyzed for many years but still remains under a cloud. As an example, only a few generic constructions of such functions are known, and connections between them are not well understood. Among them, the simpler APN monomials however seem to play an important role. In this presentation, we will first introduce all the necessary background knowledge, before moving on to our latest results. Those results bridge part of the gaps between the known constructions by observing that many of the infinite families of quadratic APN functions share a common geometrical structure known as “the subspace property”. This property was first observed on one of the most enigmatic APN function, the so-called “Kim mapping”, which is the only known APN function, with an even number of variables, that is CCZ-equivalent to a bijection. While attempts to find new APN functions having the subspace property were already carried out, this property was not clearly understood. We therefore clarify its nature by in particular pointing out its link with cyclotomic mappings, which generalize monomial functions. Joint work with Anne Canteaut & Léo Perrin.
