Bienvenue L'IRIF est une unité mixte de recherche (UMR 8243) entre le CNRS et l'Université Paris Cité, et héberge une équipe-projet Inria. Les recherches menées à l'IRIF reposent sur l’étude et la compréhension des fondements de toute l’informatique, afin d’apporter des solutions innovantes aux défis actuels et futurs des sciences numériques. L'IRIF regroupe près de deux cents personnes. Sept de ses membres ont été lauréats de l'European Research Council (ERC), trois sont membres de l'Institut Universitaire de France (IUF), deux sont membres de l'Academia Europæa, et un est membre de l'Académie des sciences. Notion du jour Réseaux Sociaux Suivez nous sur LinkedIn, Bluesky et Mastodon : Actualités 14.3.2025 Le troisième épisode du podcast “Qu'est ce que tu cherches ?” du CNRS a invité Geoffroy Couteau pour parler de son sujet de recherche : la protection des données privées, les calculs sécurisés, les protocoles sécurisés. Vous pourrez également découvrir sa journée type, le moment où il fait le plus de sciences (et non, ce n'est pas forcément pendant la journée !), les stéréotypes liés à son domaine. (Ré)Écoutez cet épisode : 10.3.2025 Félicitations à Florian Horn, co-auteur de Revelations: A Decidable Class of POMDPs with Omega-Regular Objectives, papier récompensé par le prix “Outstanding Paper Awards” à AAAI 2025. 18.2.2025 A l'occasion du colloque du CNRS intitulé « L'optimisation, au cœur des défis des sciences informatiques », David Saulpic, chargé de recherche CNRS à l'IRIF, a réalisé une présentation Flash'Opti de trois minutes sur le Big Data. Les présentations Flash'Opti sont un concept original du CNRS visant à présenter un sujet de recherche en trois minutes, à l'aide d'une seule image. Revisionnez son intervention: 18.2.2025 A l'occasion du colloque du CNRS intitulé « L'optimisation, au cœur des défis des sciences informatiques », Simon Apers, chargé de Recherche CNRS à l'IRIF a réalisé une présentation Flash'Opti de trois minutes sur l'apport des algorithmes quantiques à l'optimisation. Les présentations Flash'Opti sont un concept original du CNRS visant à présenter un sujet de recherche en trois minutes, à l'aide d'une seule image. Revisionnez son intervention: 17.2.2025 La vulgarisation scientifique, pour tous les âges ! Sophie Laplante, professeure à l'IRIF, a contribué au numéro 425 de Science & Vie Junior, qui consacre un article au quantique. Après une BD introductive, place aux explications pour mieux comprendre l’ordinateur quantique et démystifier ses promesses. Chiffrement, clés, données, calculs et bits… Ces concepts sont expliqués de façon accessible, pour permettre à tous, petits et grands, d’explorer les mystères du quantique en toute simplicité ! À découvrir dans Science & Vie : 30.1.2025 Félicitations à Esaïe Bauer et Alexis Saurin dont le papier à été accepté pour la conférence FoSSaCS 2025 ! 22.1.2025 Le troisième Paris ACTS, aura lieu à l'IRIF, le mercredi 29 janvier. P-ACTS est une série de séminaires centrés sur les connexions entre la théorie des automates et la théorie de la concurence, partagés entre l'EPITA, l'IRIF et le LIX. Les deux intervenants seront Laetitia Laversa et Glynn Winskel. Les conférences seront également diffusées sur Zoom. Pour les résumés et plus d'informations sur le séminaire, voir cette page: 10.2.2025 Félicitations à Adrian Vladu, membre de l'IRIF, dont l'article a été accepté à STOC 2025, une conférence ACM : edit toutes les anciennes actualités (Ces actualités sont présentées selon un classement mêlant priorité et aléatoire.) Agenda Sémantique Mardi 18 mars 2025, 15 heures, Salle 3071 Vladimir Zamdzhiev (LMF, Inria Saclay) Operator Spaces, Linear Logic and the Heisenberg-Schrödinger Duality of Quantum Theory In this talk we recall how quantum operations (also known as channels) are modelled mathematically in both the Heisenberg and Schrödinger pictures of quantum theory. The two pictures are dual to each other and we recall how the theory of operator spaces can be used to describe this duality in mathematical terms. Operator spaces, studied in noncommutative geometry, are the noncommutative (or quantum) analogue of Banach spaces. We prove that the category OS (operator spaces with complete contractions as morphisms) is locally countably presentable and a model of Intuitionistic Linear Logic in the sense of Lafont. We then describe a model of Classical Linear Logic, based on OS, whose duality is compatible with the Heisenberg-Schrödinger duality of quantum theory. In the later model, the mathematical descriptions of systems in the Heisenberg picture correspond to formulas with negative logical polarity, whereas those in the Schrödinger picture correspond to formulas with positive logical polarity. Time permitting, we can also cover other interesting features of the model(s). Joint work with Bert Lindenhovius. Soutenances de thèses Mardi 18 mars 2025, 16 heures 30, Amphithéâtre Turing, Bâtiment Sophie Germain Dung Bui (IRIF) Efficient Secure Computation from Correlated Pseudorandomness In this thesis, we put forward advancements in Multi-Party Computation (MPC), enabling parties to jointly compute arbitrary functions while preserving the privacy of their inputs. Our focus is on MPC with correlated randomness, where efficiency is improved through correlations generated using preprocessing. We investigate two key paradigms for generating such randomness: Pseudorandom Correlation Generators (PCGs) and Pseudorandom Correlation Functions (PCFs). First, we propose new PCG-based constructions for Private Set Intersection (PSI), achieving either tighter security or improved performance. We then explore the applications of PCGs and PCFs in Zero-Knowledge Proofs (ZKPs), addressing both interactive and non-interactive settings. For interactive ZKPs, we design a privately verifiable protocol for circuit satisfiability with sublinear communication and efficient computation. In the non-interactive setting, we introduce a new designated-verifier ZKP (DV-NIZK) leveraging PCF with a public-key structure (PK-PCF). Finally, we introduce a novel MPC framework for binary circuits, utilizing a PCG optimized for small fields. One world numeration seminar Mardi 18 mars 2025, 14 heures, Online Valentin Ovsienko (CNRS, Université de Reims-Champagne-Ardenne) From Catalan numbers to integrable dynamics: continued fractions and Hankel determinants for q-numbers The classical Catalan and Motzkin numbers have remarkable continued fraction expansions, the corresponding sequences of Hankel determinants consist of -1, 0 and 1 only. We find an infinite family of power series corresponding to q-deformed real numbers that have very similar properties. Moreover, their sequences of Hankel determinants turn out to satisfy Somos and Gale-Robinson recurrences. (Partially based on a joint work with Emmanuel Pedon.) Algorithmes et complexité Mercredi 19 mars 2025, 11 heures, Salle 3052 Carsten Baum (Technical University of Denmark) VOLEs and Digital Signatures In the past decade and largely in response to the NIST standardization effort for post-quantum cryptography, many new designs for digital signatures have been proposed. Among those, the FAEST digital signature scheme (Baum et al., CRYPTO 2023) stands out due to its interesting security-performance trade-off. It only relies on well-tested symmetric-key cryptographic primitives, as it constructs a digital signature from a Zero-Knowledge (ZK) proof of knowledge of an AES key. To achieve this, it uses the VOLE-in-the-head ZK proof system. FAEST simultaneously has relatively small signature size and competitive sign and verify times. In this talk, I will describe how VOLE-in-the-head and FAEST works. Additionally, I will present recent improvements to both the security and practical efficiency of FAEST by revisiting the evaluation of the AES block cipher in ZK. This talk is based on (recent) joint work with Ward Beullens, Lennart Braun, Cyprien Delpech de Saint Guilhem, Michael Klooß, Christian Majenz, Shibam Mukherjee, Emmanuela Orsini, Sebastian Ramacher, Christian Rechberger, Lawrence Roy, and Peter Scholl. Preuves, programmes et systèmes Jeudi 20 mars 2025, 10 heures 30, Salle 3052 Marie Kerjean (LIPN, Université Sorbonne Paris Nord, CNRS) δ is for Dialectica Automatic Differentiation is the study of the efficient computation of differentials. While the first automatic differentiation algorithms are concomitant with the birth of computer science, the specific backpropagation algorithm has been brought to a modern light by its application to neural networks. This work unveils a surprising connection between backpropagation and Gödel's Dialectica interpretation, a logical translation that realizes semi-classical axioms. This unexpected correspondence is exploited through different logical settings. In particular, we show that the computational interpretation of Dialectica translates to the differential λ-calculus and that Differential Linear Logic subsumes the logical interpretation of Dialectica. Séminaire des membres non-permanents Jeudi 20 mars 2025, 16 heures, Salle 3052 Roman Edenhofer Non encore annoncé. Soutenances de thèses Jeudi 20 mars 2025, 16 heures, Amphithéâtre Turing, Bâtiment Sophie Germain Eliana Carozza (IRIF) Code-Based Post-Quantum Signature Schemes: from MPC-in-the-Head to Threshold Signatures This manuscript focuses on defining and optimizing code-based cryptographic primitives, with a particular emphasis on digital signatures derived through the Fiat-Shamir transformation of zero-knowledge proofs of knowledge. It presents three main contributions. The first contribution introduces a five-round zero-knowledge proof of knowledge protocol based on the RSD problem, employing an advanced witness conversion technique. The protocol is then transformed into a digital signature scheme using the Fiat-Shamir heuristic, adapted for post-quantum security. Performance is further optimized through a novel hypercube technique, achieving competitive speeds relative to existing schemes. The second contribution focuses on improving the efficiency of the MPC-in-the-Head paradigm by defining multi-instance puncturable pseudorandom functions (PPRFs) specifically designed for code-based protocols: replacing traditional hash-based approaches with fixed-key block ciphers, the proposed PPRFs reduce signing and verification times by up to 55×, establishing new performance benchmarks for MPC-in-the-Head-based schemes. The third contribution extends the initial digital signature scheme into a threshold signature framework, addressing the challenges of efficiently adapting MPC-based schemes for multi-user collaborative signing. The proposed methodology minimizes the trade-off between signature size and user count, outperforming naive concatenation techniques. Applied to the earlier code-based signature scheme, this approach results in a practical and efficient threshold signature solution. In conclusion, this manuscript presents significant advancements in code-based post-quantum cryptography by addressing fundamental challenges in security and efficiency. Combining rigorous theoretical design with practical relevance, the contributions align with the goals of the NIST standardization process and address emerging needs such as blockchain and decentralized systems. Catégories supérieures, polygraphes et homotopie Vendredi 21 mars 2025, 14 heures, Salle 1013 Moana Jubert From (higher) descent to indexed presheaves Descent theory is a set of ideas for reconstructing global structures from local data. The typical example is that we can define a continuous function by recollecting its restrictions on a family of openings covering the base space. On the other hand, a presheaf is usually defined as the data of a functor from a base category into Set. This approach makes the choice of presentation of the base category somehow “invisible”, and if you happen to be a type theorist, it is sorely lacking in “dependent” flavor. The aim of this presentation is to explain my ongoing work on how descent theory inspires me to give another way of defining presheaves—the so-called “indexed presheaves”. The first part of the talk will be a brief introduction to descent theory, and its 2-categorical version. The second part, less rigorous, will present my current ideas and plans. Automates Vendredi 21 mars 2025, 14 heures, Salle 3052 Pascal Weil Non encore annoncé. Algorithmique distribuée et graphes Mardi 25 mars 2025, 15 heures, 3052 Diana Sasaki (Rio de Janeiro State University) The total coloring problem and its variants A total coloring of a graph G is an assignment of colors to the vertices and edges of G such that adjacent vertices or edges receive different colors, and each vertex has a different color from its incident edges. Determining the minimum number of colors required for a total coloring of a graph, known as the total chromatic number, plays a fundamental role in the total coloring problem. Currently, its main conjecture, called the Total Coloring Conjecture, has remained open for almost 60 years and has inspired the development of various coloring variants of this problem. In this talk, several open problems arising from the total coloring problem will be presented. A joint work with Mauro Nigro.