BEGIN:VCALENDAR VERSION:2.0 PRODID:-//Laboratoire de Mathématiques de Versailles - ECPv6.15.20//NONSGML v1.0//EN CALSCALE:GREGORIAN METHOD:PUBLISH X-WR-CALNAME:Laboratoire de Mathématiques de Versailles X-ORIGINAL-URL:https://lmv.math.cnrs.fr X-WR-CALDESC:Évènements pour Laboratoire de Mathématiques de Versailles REFRESH-INTERVAL;VALUE=DURATION:PT1H X-Robots-Tag:noindex X-PUBLISHED-TTL:PT1H BEGIN:VTIMEZONE TZID:Europe/Paris BEGIN:DAYLIGHT TZOFFSETFROM:+0100 TZOFFSETTO:+0200 TZNAME:CEST DTSTART:20180325T010000 END:DAYLIGHT BEGIN:STANDARD TZOFFSETFROM:+0200 TZOFFSETTO:+0100 TZNAME:CET DTSTART:20181028T010000 END:STANDARD BEGIN:DAYLIGHT TZOFFSETFROM:+0100 TZOFFSETTO:+0200 TZNAME:CEST DTSTART:20190331T010000 END:DAYLIGHT BEGIN:STANDARD TZOFFSETFROM:+0200 TZOFFSETTO:+0100 TZNAME:CET DTSTART:20191027T010000 END:STANDARD BEGIN:DAYLIGHT TZOFFSETFROM:+0100 TZOFFSETTO:+0200 TZNAME:CEST DTSTART:20200329T010000 END:DAYLIGHT BEGIN:STANDARD TZOFFSETFROM:+0200 TZOFFSETTO:+0100 TZNAME:CET DTSTART:20201025T010000 END:STANDARD BEGIN:DAYLIGHT TZOFFSETFROM:+0100 TZOFFSETTO:+0200 TZNAME:CEST DTSTART:20210328T010000 END:DAYLIGHT BEGIN:STANDARD TZOFFSETFROM:+0200 TZOFFSETTO:+0100 TZNAME:CET DTSTART:20211031T010000 END:STANDARD BEGIN:DAYLIGHT TZOFFSETFROM:+0100 TZOFFSETTO:+0200 TZNAME:CEST DTSTART:20220327T010000 END:DAYLIGHT BEGIN:STANDARD TZOFFSETFROM:+0200 TZOFFSETTO:+0100 TZNAME:CET DTSTART:20221030T010000 END:STANDARD BEGIN:DAYLIGHT TZOFFSETFROM:+0100 TZOFFSETTO:+0200 TZNAME:CEST DTSTART:20230326T010000 END:DAYLIGHT BEGIN:STANDARD TZOFFSETFROM:+0200 TZOFFSETTO:+0100 TZNAME:CET DTSTART:20231029T010000 END:STANDARD BEGIN:DAYLIGHT TZOFFSETFROM:+0100 TZOFFSETTO:+0200 TZNAME:CEST DTSTART:20240331T010000 END:DAYLIGHT BEGIN:STANDARD TZOFFSETFROM:+0200 TZOFFSETTO:+0100 TZNAME:CET DTSTART:20241027T010000 END:STANDARD BEGIN:DAYLIGHT TZOFFSETFROM:+0100 TZOFFSETTO:+0200 TZNAME:CEST DTSTART:20250330T010000 END:DAYLIGHT BEGIN:STANDARD TZOFFSETFROM:+0200 TZOFFSETTO:+0100 TZNAME:CET DTSTART:20251026T010000 END:STANDARD END:VTIMEZONE BEGIN:VEVENT DTSTART;TZID=Europe/Paris:20241105T103000 DTEND;TZID=Europe/Paris:20241105T120000 DTSTAMP:20260414T165825 CREATED:20241022T114704Z LAST-MODIFIED:20241108T090132Z UID:13274-1730802600-1730808000@lmv.math.cnrs.fr SUMMARY:CRYPTO : Chloé Hébant (Cosmian) - Recherche de mots-clés dans des données chiffrées DESCRIPTION:Dans cette présentation\, nous allons aborder les défis liés au chiffrement des grandes bases de données et à la recherche de mots-clés dans des données chiffrées. Les bases de données modernes offrent des performances élevées\, même en cas de forte concurrence\, en garantissant la scalabilité et la fiabilité tout en permettant la recherche par mots clés. Cependant\, ces performances sont possibles parce que les serveurs ont accès aux données en clair. Lorsque l’on chiffre les documents avant de les envoyer au serveur\, on résout le problème de confidentialité\, mais on perd la capacité de rechercher des informations.\n\n\nPour pallier ce problème\, des primitives cryptographiques comme les algorithmes de recherche sur données chiffrées (Symmetric Searchable Encryption\, SSE) ont été développées. Ces schémas permettent à un utilisateur de chiffrer des documents tout en créant un index sécurisé\, facilitant ainsi la recherche de mots-clés. Toutefois\, les constructions SSE actuelles se limitent à un seul utilisateur et un seul serveur et ne prennent donc pas en compte les requêtes concurrentes qui pourraient arriver. \nFindex propose une avancée majeure dans ce domaine. Cet article présente la première solution SSE qui définit clairement la correction et garantit la sécurité dans un environnement concurrent. L’article introduit notamment la notion de linéarisation comme critère standard de correction pour les SSE dans des contextes où plusieurs utilisateurs effectuent des requêtes simultanément. De plus\, il met en évidence l’impact de la concurrence sur la sécurité\, en proposant un nouveau modèle de sécurité appelé log-security\, qui protège contre les attaques liées aux logs de persistance\, comblant ainsi une lacune dans les modèles de sécurité basés sur des instantanés (snapshot). \n\n\nArticle : https://eprint.iacr.org/2024/1541\nGithub : https://github.com/Cosmian/findex/tree/eprint URL:https://lmv.math.cnrs.fr/evenenement/recherche-de-mots-cles-dans-des-donnees-chiffrees/ LOCATION:Bâtiment Fermat\, salle 4205 CATEGORIES:Séminaire CRYPTO END:VEVENT BEGIN:VEVENT DTSTART;TZID=Europe/Paris:20240118T110000 DTEND;TZID=Europe/Paris:20240118T120000 DTSTAMP:20260414T165825 CREATED:20240125T104210Z LAST-MODIFIED:20240125T104210Z UID:12398-1705575600-1705579200@lmv.math.cnrs.fr SUMMARY:CRYPTO: Sacha Servan-Schreiber (IRIF) : The power of subtractive secret sharing in secure computation DESCRIPTION:Surprisingly\, two-party computation protocols are occasionally more efficient than their three party computation counterparts. This is due to the fact that two-party protocols can use distributed point function (DPF) which are a very efficient building block. In this talk\, we will examine what mathematical tools are used to build efficient DPFs and we will go in details over a specific construction. This will help us understand why multi-party DPFs have been difficult to construct and what assumptions could allow us to circumvent this barrier in the future. URL:https://lmv.math.cnrs.fr/evenenement/crypto-sacha-servan-schreiber-irif-the-power-of-subtractive-secret-sharing-in-secure-computation/ LOCATION:Bâtiment Fermat\, salle 4205 CATEGORIES:Séminaire CRYPTO END:VEVENT BEGIN:VEVENT DTSTART;TZID=Europe/Paris:20231214T110000 DTEND;TZID=Europe/Paris:20231214T123000 DTSTAMP:20260414T165825 CREATED:20231116T131142Z LAST-MODIFIED:20231214T124045Z UID:12273-1702551600-1702557000@lmv.math.cnrs.fr SUMMARY:CRYPTO : Nicolas Bon (CryptoExperts) : Evaluation homomorphe de fonctions booléennes DESCRIPTION:Le chiffrement complètement homomorphe (ou FHE for Fully Homomorphic Encryption) est une technique cryptographique qui permet à un serveur d’effectuer des calculs sur des données chiffrées sans apprendre aucune information sur celles-ci. Après une présentation générale de la technologie et de l’état de l’art\, nous présenterons plus en détail TFHE\, l’un des chiffrements les plus performants actuellement. Nous introduirons ensuite une nouvelle méthode permettant d’évaluer des fonctions booléennes de manière plus efficace  avec TFHE et illustrerons les avantages de notre technique sur des cas concrets d’évaluations homomorphes de primitives cryptographiques. URL:https://lmv.math.cnrs.fr/evenenement/crypto-nicolas-bon-cryptoexperts-evaluation-homomorphe-de-fonctions-booleennes/ LOCATION:Bâtiment Fermat\, salle 4205 CATEGORIES:Séminaire CRYPTO END:VEVENT BEGIN:VEVENT DTSTART;TZID=Europe/Paris:20231123T110000 DTEND;TZID=Europe/Paris:20231123T120000 DTSTAMP:20260414T165825 CREATED:20231101T122601Z LAST-MODIFIED:20231125T101735Z UID:12240-1700737200-1700740800@lmv.math.cnrs.fr SUMMARY:CRYPTO : Jules Baudrin (Inria) : La cryptanalyse commutative\, une classe (pas trop) générale d'attaques DESCRIPTION:La cryptanalyse par diagramme commutatif\, unifie sous un même cadre la plupart des méthodes « classiques » d’analyse de chiffrements symétriques. Néanmoins depuis 20 ans\, cette généralisation n’a\, à notre connaissance\, jamais été utilisée\, ni pour bâtir des arguments de sécurité\, ni pour découvrir de nouveaux types d’attaques.\nDans cet exposé\, nous introduisons et développons un cas moins général\, la cryptanalyse commutative. Son principe : étant donnée une primitive E\, trouver un couple de bijections affines (A\,B) vérifiant l’égalité EoA = BoE avec grande probabilité. Ce cadre est à la fois suffisamment général pour englober certaines attaques déjà connues (notamment différentielles\, qui correspondent au cas A = Id + a\, B = Id + b)\, tout en permettant d’en découvrir de nouvelles\, de nature jusqu’alors inconnue.\nNous illustrerons les méthodes développées en étudiant notamment une version modifiée du chiffrement Midori. Pour celle-ci\, nous présenterons un tel couple (A\, B) qui\, lorsque la clé est faible\, vérifie l’égalité avec probabilité 1 et distingue la primitive d’une permutation aléatoire avec un seul couple clair-chiffré. Enfin\, la relation entre ce distingueur et son interprétation différentielle sera aussi discutée: lorsque la clé est faible\, il existe des différentielles dont la très haute probabilité est indépendante du nombre de tours. URL:https://lmv.math.cnrs.fr/evenenement/crypto-jules-baudrin-inria-la-cryptanalyse-commutative-une-classe-pas-trop-generale-dattaques/ LOCATION:Bâtiment Fermat\, salle 4205 CATEGORIES:Séminaire CRYPTO END:VEVENT BEGIN:VEVENT DTSTART;TZID=Europe/Paris:20231109T110000 DTEND;TZID=Europe/Paris:20231109T120000 DTSTAMP:20260414T165825 CREATED:20231031T054720Z LAST-MODIFIED:20231110T095823Z UID:12238-1699527600-1699531200@lmv.math.cnrs.fr SUMMARY:CRYPTO: Balthazar Bauer (LMV) : Monnaies numériques transférables\, et modèle du groupe algébrique. DESCRIPTION:Dans cette présentation\, on s’intéressera au monnaies numériques\ntransférable et on regardera en particulier pourquoi définir la\nconfidentialité des transactions n’est pas chose triviale.\nPuis dans un second temps\, et après avoir posé un paradigme important de\nla sécurité prouvée\, on étudiera de nombreuses hypothèses cryptographiques\nasymétriques dans le modèle du groupe algébrique dans lequel on choisit\nvolontairement de considérer des adversaires aux capacités de calcul\nrestreintes. URL:https://lmv.math.cnrs.fr/evenenement/crypto-balthazar-bauer-lmv-monnaies-numeriques-transferables-et-modele-du-groupe-algebrique/ LOCATION:Bâtiment Fermat\, salle 4205 CATEGORIES:Séminaire CRYPTO END:VEVENT BEGIN:VEVENT DTSTART;TZID=Europe/Paris:20230223T112000 DTEND;TZID=Europe/Paris:20230223T122000 DTSTAMP:20260414T165825 CREATED:20230112T075914Z LAST-MODIFIED:20230224T084328Z UID:11470-1677151200-1677154800@lmv.math.cnrs.fr SUMMARY:CRYPTO : Alain Couvreur (Inria Saclay) : On a recent attack on SIKE DESCRIPTION:In this talk\, after recalling some general results on elliptic curves and isogenies\, I will present\, the various key exchange techniques based on isogenies between\, namely Couveignes-Rostovtsev-Stolbunov\, SIKE and CSIDH.\nThen\, I give a description of the main ideas that led Decru and Castryck to a devastating attack on SIKE. This talk is *not* the presentation of personal results. URL:https://lmv.math.cnrs.fr/evenenement/crypto-alain-couvreur-inria-saclay-on-a-recent-attack-on-sike/ LOCATION:Bâtiment Fermat\, salle 4205 CATEGORIES:Séminaire CRYPTO END:VEVENT BEGIN:VEVENT DTSTART;TZID=Europe/Paris:20221201T110000 DTEND;TZID=Europe/Paris:20221201T120000 DTSTAMP:20260414T165825 CREATED:20221128T092841Z LAST-MODIFIED:20221128T092841Z UID:11079-1669892400-1669896000@lmv.math.cnrs.fr SUMMARY:CRYPTO : Kévin Carrier (CY Cergy-Paris Université) : Faster Dual Lattice Attacks by Using Coding Theory DESCRIPTION:We present a faster dual lattice attack on the Learning with\nErrors (LWE) problem\, based on ideas from coding theory. Basically\, it\nconsists in revisiting the most classical dual attack by replacing\nmodulus switching by a decoding algorithm. This replacement achieves a\nreduction from small LWE to plain LWE with a very significant reduction\nof the secret dimension. We also replace the enumeration part of this\nattack by betting that the secret is zero on the part where we want to\nenumerate it and iterate this bet over other choices of the enumeration\npart.We estimate the complexity of this attack by making the optimistic\,\nbut realistic guess that we can use polar codes for this decoding task. We\nshow that under this assumption the best attacks on Kyber and Saber\ncan be improved by 1 and 6 bits. URL:https://lmv.math.cnrs.fr/evenenement/crypto-kevin-carrier-cy-cergy-paris-universite-faster-dual-lattice-attacks-by-using-coding-theory/ LOCATION:Bâtiment Fermat\, salle 4205 CATEGORIES:Séminaire CRYPTO END:VEVENT BEGIN:VEVENT DTSTART;TZID=Europe/Paris:20221124T110000 DTEND;TZID=Europe/Paris:20221124T120000 DTSTAMP:20260414T165825 CREATED:20221116T081232Z LAST-MODIFIED:20230509T133324Z UID:11066-1669287600-1669291200@lmv.math.cnrs.fr SUMMARY:CRYPTO : Augustin Bariant (INRIA) : Algebraic Attacks against Some Arithmetization-Oriented Symmetric Cryptographic Algorithms DESCRIPTION:In some recent advanced protocols\, like Zero-Knowledge Proofs (allowing a prover to convince a verifier that he knows a secret without revealing it)\, or Multi Party Computation\, algorithms do not process bit-oriented information\, but rather elements of big finite fields Z/qZ. In that regard\, the only operations allowed in such algorithms are additions and multiplications in the field. These protocols therefore require cryptographic algorithms that are not optimized for usual bit-oriented platforms (desktop computers\, servers\, microcontrollers\, RFID tags…)\, but rather for their short implementation in Z/qZ. These are called arithmetization-oriented cryptographic algorithms. \nSince 2016\, several arithmetization-oriented algorithms have been presented. Their security highly depends on the complexity of polynomial root-finding and Groebner basis algorithms\, which define a special class of attacks: algebraic attacks. In 2021\, the Ethereum Foundation launched a series of challenges on this new class of ciphers\, aiming at better understanding the threat of algebraic attacks. We took that opportunity to perform a thorough study of univariate and multivariate polynomial solving algorithms in big fields. \nIn this talk\, we present an overview of existing algebraic attacks and analysis\, along with new theoretical and experimental results on several ciphers. URL:https://lmv.math.cnrs.fr/evenenement/crypto-augustin-bariant-inria-algebraic-attacks-against-some-arithmetization-oriented-symmetric-cryptographic-algorithms/ LOCATION:Bâtiment Fermat\, salle 4205 CATEGORIES:Séminaire CRYPTO END:VEVENT BEGIN:VEVENT DTSTART;TZID=Europe/Paris:20221020T110000 DTEND;TZID=Europe/Paris:20221020T120000 DTSTAMP:20260414T165825 CREATED:20221011T190230Z LAST-MODIFIED:20221021T135943Z UID:10937-1666263600-1666267200@lmv.math.cnrs.fr SUMMARY:CRYPTO : Léo Perrin (Inria) : La cryptographie orientée arithmétisation : pourquoi et comment ? DESCRIPTION:La cryptographie symétrique traite de fonctions ordinairement définies sur des (chaînes de) bits en utilisant éventuellement des sous-fonctions définies sur de petits corps finis (comme l’AES et sa boîte-S définie sur GF(256)). Néanmoins\, de nouveaux protocoles sophistiqués\, par exemple de preuve à échange nul de connaissance\, nécessitent désormais des primitives symétriques dites « orientées arithmétisation » qui doivent satisfaire un cahier des charges très différent de celui auquel les cryptographes symétriques sont habitués. En effet\, il devient nécessaire de considérer des fonctions de bas degré définies sur de grands corps premiers\, ce qui est à l’antipode des usages dans ce domaine.\n\nDans cette présentation\, nous étudierons ce que l’orientation arithmétisation implique concrètement\, ce qui imposera un détour par des concepts mathématiques non triviaux issus de la théorie des fonctions Booléennes vectorielles. En particulier\, nous verrons que l’équivalence CCZ s’avère jouer un rôle prépondérant dans ce nouveau contexte. Nous verrons ensuite la famille de permutations appelées « Anemoi » dont la construction est basée sur la-dite équivalence\, de l’idée à la base de sa conception jusqu’aux performance de son implémentation finale. URL:https://lmv.math.cnrs.fr/evenenement/crypto-leo-perrin-inria-la-cryptographie-orientee-arithmetisation-pourquoi-et-comment/ LOCATION:Bâtiment Descartes\, salle 301 CATEGORIES:Séminaire CRYPTO END:VEVENT BEGIN:VEVENT DTSTART;TZID=Europe/Paris:20221013T110000 DTEND;TZID=Europe/Paris:20221013T120000 DTSTAMP:20260414T165825 CREATED:20221009T210632Z LAST-MODIFIED:20221013T105400Z UID:10927-1665658800-1665662400@lmv.math.cnrs.fr SUMMARY:CRYPTO : Patrick Derbez (Université Rennes 1) : MILP appliqué à la cryptographie DESCRIPTION:Rechercher les meilleures attaques et les meilleurs distingueurs contre les primitives cryptographiques a toujours été une tâche difficile. Depuis une dizaine d’années\, l’utilisation de solveurs MILP pour résoudre ce type de problèmes s’est largement démocratisée. Dans cette présentation nous discuterons de différentes techniques de cryptanalyse et des modélisations MILP associées. Nous aborderons les limites de ces modèles et certaines des solutions proposées pour les contourner. URL:https://lmv.math.cnrs.fr/evenenement/crypto-patrick-derbez-universite-rennes-1-milp-applique-a-la-cryptographie/ LOCATION:Bâtiment Descartes\, salle 301 CATEGORIES:Séminaire CRYPTO END:VEVENT BEGIN:VEVENT DTSTART;TZID=Europe/Paris:20220224T111000 DTEND;TZID=Europe/Paris:20220224T123000 DTSTAMP:20260414T165825 CREATED:20220216T150035Z LAST-MODIFIED:20220303T094358Z UID:9994-1645701000-1645705800@lmv.math.cnrs.fr SUMMARY:CRYPTO : Pierre Galissant (UVSQ) : Resisting Key-Extraction and Code-Compression: a Secure Implementation of the HFE Signature Scheme in the White-Box Model DESCRIPTION:Cryptography is increasingly deployed in applications running on open devices in which the software is extremely vulnerable to attacks\, since the attacker has complete control over the execution platform and the software implementation itself. This creates a challenge for cryptography: design implementations of cryptographic algorithms that are secure\, not only in the black-box model\, but also in this attack context that is referred to as the white-box adversary model. Moreover\, emerging applications such as mobile payment\, mobile contract signing or blockchain-based technologies have created a need for white-box implementations of public-key cryptography\, and especially of signature algorithms. \nHowever\, while many attempts were made to construct white-box implementations of block-ciphers\, almost no white-box implementations have been published for what concerns asymmetric schemes. We present here a concrete white-box implementation of the well-known HFE signature algorithm for a specific set of internal polynomials. For a security level $2^{80}$\, the public key size is approximately 62.5 MB and the white-box implementation of the signature algorithm has a size approximately 256 GB. \nThe talk will be based on joint work with Louis Goubin. A preprint is available here :  https://eprint.iacr.org/2022/138 URL:https://lmv.math.cnrs.fr/evenenement/crypto-pierre-galissant-uvsq-resisting-key-extraction-and-code-compression-a-secure-implementation-of-the-hfe-signature-scheme-in-the-white-box-model/ LOCATION:Bâtiment Descartes\, salle 301 CATEGORIES:Séminaire CRYPTO END:VEVENT BEGIN:VEVENT DTSTART;TZID=Europe/Paris:20220210T110000 DTEND;TZID=Europe/Paris:20220210T120000 DTSTAMP:20260414T165825 CREATED:20220131T121449Z LAST-MODIFIED:20220211T133509Z UID:9921-1644490800-1644494400@lmv.math.cnrs.fr SUMMARY:CRYPTO : Yann Rotella (UVSQ) : Cryptanalyse des algorithmes GEA-1 et GEA-2 pour la communication GPRS DESCRIPTION:Dans cette présentation\, nous présenterons l’article publié à Eurocrypt 2021 [BDLLRRRS21]. Nous montrerons comment retrouver l’état interne dans ces deux chiffrements\, encore utilisés dans la communication 2G. Notre attaque nécessite 44 GB de mémoire et peut se faire avec un nombre réduit de couples clairs / chiffrés\, en utilisant principalement l’interaction entre deux registres de l’état interne. De plus\, nous montrerons que cette interaction est peu probable et que cela indique que la faiblesse aurait pu être introduite intentionnellement. \nNous montrerons aussi comment attaquer GEA-2\, en combinant plusieurs techniques de cryptanalyse. \nhttps://link.springer.com/chapter/10.1007/978-3-030-77886-6_6 \nhttps://eprint.iacr.org/2021/819.pdf \n  \nLe séminaire aura lieu en hybride (via Zoom).  URL:https://lmv.math.cnrs.fr/evenenement/crypto-yann-rotella-uvsq-cryptanalysis-of-the-gprs-encryption-algorithms-gea-1-and-gea-2/ LOCATION:Bâtiment Descartes\, salle 301 CATEGORIES:Séminaire CRYPTO END:VEVENT BEGIN:VEVENT DTSTART;TZID=Europe/Paris:20210708T110000 DTEND;TZID=Europe/Paris:20210708T120000 DTSTAMP:20260414T165825 CREATED:20210705T064537Z LAST-MODIFIED:20210709T090047Z UID:9401-1625742000-1625745600@lmv.math.cnrs.fr SUMMARY:CRYPTO: Luca De Feo (IBM): On the (in)security of ElGamal in OpenPGP DESCRIPTION:Do you think you know ElGamal encryption? Think twice. \nWe uncover vulnerabilities in the OpenPGP ecosystem stemming from confusion about the definition of ElGamal encryption (and the lack of an unequivocable standard). The first vulnerability leads to practical plaintext recovery in a limited number of cases. The second one\, combined with side-channel leakage we found in some popular OpenPGP libraries\, leads to feasible key recovery\, in relatively rare cases. \nJoint work with B. Poettering and A. Sorniotti URL:https://lmv.math.cnrs.fr/evenenement/crypto-luca-de-feo-ibm-on-the-insecurity-of-elgamal-in-openpgp/ LOCATION:Bâtiment Descartes\, salle 301 CATEGORIES:Séminaire CRYPTO END:VEVENT BEGIN:VEVENT DTSTART;TZID=Europe/Paris:20210624T110000 DTEND;TZID=Europe/Paris:20210624T120000 DTSTAMP:20260414T165825 CREATED:20210603T115047Z LAST-MODIFIED:20210625T081003Z UID:9336-1624532400-1624536000@lmv.math.cnrs.fr SUMMARY:CRYPTO : Kevin Deforth and Mariya Georgieva (Inpher) : Manticore: Efficient Framework for Scalable Secure Multiparty Computation Protocols DESCRIPTION:In this talk we will present a novel MPC framework\, Manticore\, with full threshold and semi-honest security model\, supporting a combination of real number arithmetic (arithmetic shares)\, Boolean arithmetic (Boolean shares) and garbled circuits (Yao shares). We establish a parallel between the plaintext encodings used to represent boolean\, integer and fixed-point numbers between Chimera-FHE and Manticore-MPC\, and show that many notions like level\, depth\, lift/bootstrapping are in common between these two privacy preserving techniques. \nWe explain how to achieve the base arithmetic on bits and numbers in MPC. \n\nThe talk is based on: https://eprint.iacr.org/2021/200.pdf URL:https://lmv.math.cnrs.fr/evenenement/crypto-kevin-deforth-and-mariya-georgieva-inpher-manticore-efficient-framework-for-scalable-secure-multiparty-computation-protocols/ LOCATION:Bâtiment Descartes\, salle 301 CATEGORIES:Séminaire CRYPTO END:VEVENT BEGIN:VEVENT DTSTART;TZID=Europe/Paris:20210617T110000 DTEND;TZID=Europe/Paris:20210617T120000 DTSTAMP:20260414T165825 CREATED:20210517T143153Z LAST-MODIFIED:20210618T070722Z UID:9289-1623927600-1623931200@lmv.math.cnrs.fr SUMMARY:CRYPTO : Léo Perrin (Inria) : Testing the equivalence of quadratic vectorial Boolean functions DESCRIPTION:Vectorial Boolean functions map n bits to m. These functions and their properties are of particular interest to cryptographers since they correspond to the S-boxes used in block ciphers\, to the filter functions of stream ciphers\, etc. \nQuadratic functions are especially interesting for two reasons. From the implementation perspective\, they ease the use of some counter-measures against side-channel attacks. From a theoretical stand-point\, they play a big role in the ongoing investigation of the big APN problem (an APN function is one with optimal differential properties). In this talk\, I will present some tools that allow an efficient investigation of the equivalence class in which a given function lives. The focus will be on CCZ-equivalence\, including the particular case of extended-affine equivalence. \nTwo approaches will be presented.\n1. The one relies on the Jacobian matrix of the function\, and allows recovering the specifics of the extended-affine relation between two functions (if it exists). It is a joint work with Anne Canteaut and Alain Couvreur.\n2. The other can very efficiently « label » the extended-affine equivalence class of a quadratic APN function\, and thus its CCZ-class. As an illustration of the latter\, I will present a significantly large number of new quadratic APN functions found by a team from Bochum\, and then quickly mention some fun functions in this set that I investigated with them. URL:https://lmv.math.cnrs.fr/evenenement/crypto-leo-perrin-inria-testing-the-equivalence-of-quadratic-vectorial-boolean-functions/ LOCATION:Bâtiment Descartes\, salle 301 CATEGORIES:Séminaire CRYPTO END:VEVENT BEGIN:VEVENT DTSTART;TZID=Europe/Paris:20210610T110000 DTEND;TZID=Europe/Paris:20210610T123000 DTSTAMP:20260414T165825 CREATED:20210603T085623Z LAST-MODIFIED:20210611T064752Z UID:9334-1623322800-1623328200@lmv.math.cnrs.fr SUMMARY:CRYPTO : Ilaria Chillotti (Zama) : Improved Programmable Bootstrapping with Larger Precision and Efficient Arithmetic Circuits for TFHE DESCRIPTION:Fully Homomorphic Encryption (FHE) schemes enable to compute over encrypted data. Among them\, TFHE has the great advantage of offering an efficient method for bootstrapping noisy ciphertexts\, i.e.\, reduce the noise. Indeed\, homomorphic computation increases the noise in ciphertexts and might compromise the encrypted message. TFHE bootstrapping\, in addition to reducing the noise\, also evaluates (for free) univariate functions expressed as look-up tables. It however requires to have the most significant bit of the plaintext to be known a priori\, resulting in the loss of one bit of space to store messages. Furthermore it represents a non negligible overhead in terms of computation in many use cases.\nIn this presentation\, we show a solution to overcome this limitation\, that we call Programmable Bootstrapping Without Padding (WoP-PBS). This approach relies on two building blocks. The first one is the multiplication à la BFV that we incorporate into TFHE. This is possible thanks to a thorough noise analysis showing that correct multiplications can be computed using practical TFHE parameters. The second building block is the generalization of TFHE bootstrapping introduced in this paper. It offers the flexibility to select any chunk of bits in an encrypted plaintext during a bootstrap. It also enables to evaluate many LUTs at the same time when working with small enough precision.\n\nThis is a joint work with Damien Ligier\, Jean-Baptiste Orfila and Samuel Tap. URL:https://lmv.math.cnrs.fr/evenenement/crypto-ilaria-chillotti-zama-improved-programmable-bootstrapping-with-larger-precision-and-efficient-arithmetic-circuits-for-tfhe/ LOCATION:Bâtiment Descartes\, salle 301 CATEGORIES:Séminaire CRYPTO END:VEVENT BEGIN:VEVENT DTSTART;TZID=Europe/Paris:20210408T110000 DTEND;TZID=Europe/Paris:20210408T120000 DTSTAMP:20260414T165825 CREATED:20210402T123218Z LAST-MODIFIED:20210409T102552Z UID:9130-1617879600-1617883200@lmv.math.cnrs.fr SUMMARY:CRYPTO : Geoffroy Couteau (IRIF) : LPN a densité variable\, et fonctions faiblement pseudoaléatoires dans des classes de complexité basses DESCRIPTION:Les fonctions faiblement pseudoaléatoires (WPRFs) sont des\nfonctions F_K indistinguables d’une fonction totalement aléatoire à\npartir de paires (x\, F_K(x)) pour des x aléatoires. Ces fonctions ont\ndiverses applications en cryptographie symétrique – elles permettent par\nexemple de construire des MACs\, ou des systèmes de chiffrement à flot –\net l’existence de telles fonctions dans des classes de complexité basses\nest une question fondamentale en théorie de l’apprentissage. Dans ce\npapier\, nous étudions l’existence de WPRFs dans une classe de complexité\nparticulièrement faible : les circuits booléens de taille polynomiale et\nde profondeur 2\, avec une rangée de portes ET (de degré entrant\narbitraire)\, et une unique porte XOR avant la sortie. Le choix de cette\nclasse particulière est aussi motivé par une application surprenante au\ndomaine du calcul sécurisé : nous démontrons que l’existence d’une WPRF\ndans cette classe permet d’améliorer radicalement l’efficacité de la\nphase de précalcul d’essentiellement tous les protocoles de calcul\nsécurisé modernes. \nNous introduisons une nouvelle variante de l’hypothèse LPN (qui\nconjecture la difficulté de décoder des mots de codes bruités dans un\ncode linéaire aléatoire)\, où la matrice génératrice du code et le\nvecteur de bruit ont tous deux une densité variable. Nous montrons que\nsous cette nouvelle hypothèse\, il est possible de construire une WPRF\ncalculable avec une rangée de ET\, et un unique XOR. Nous étudions\nensuite la sécurité de cette nouvelle construction\, sous l’angle d’une\nvariante de LPN\, et sous l’angle des fonctions booléennes. Nous\ndémontrons que de nombreuses classes d’attaques (attaques linéaires\,\nattaques algébriques\, attaques par requêtes statistiques\, cryptanalyse\nlinéaire\, et attaques AC0) ne peuvent pas asymptotiquement invalider\ncette hypothèse. \nBasé sur des travaux joints avec Elette Boyle\, Niv Gilboa\, Yuval Ishai\,\nLisa Kohl\, et Peter Scholl\, présentés à FOCS 2021. \nL’événement aura lieu en ligne via Zoom. \nhttps://uvsq-fr.zoom.us/j/91963933158?pwd=MnlRVHRGTTQwOEdVUEdJMFZoa1pRQT09 URL:https://lmv.math.cnrs.fr/evenenement/crypto-geoffroy-couteau-irif-lpn-a-densite-variable-et-fonctions-faiblement-pseudoaleatoires-dans-des-classes-de-complexite-basses/ CATEGORIES:Séminaire CRYPTO END:VEVENT BEGIN:VEVENT DTSTART;TZID=Europe/Paris:20210311T110000 DTEND;TZID=Europe/Paris:20210311T123000 DTSTAMP:20260414T165825 CREATED:20210217T142928Z LAST-MODIFIED:20210311T154135Z UID:8978-1615460400-1615465800@lmv.math.cnrs.fr SUMMARY:CRYPTO : Antonin Leroux (Inria Saclay) : SQISign: Compact Post-Quantum Signature from Quaternions and Isogenies DESCRIPTION:We introduce a new signature scheme\, SQISign\, (for Short Quaternion and Isogeny Signature)  from isogeny graphs of supersingular elliptic curves. The signature scheme is derived from a new one-round\, high soundness\, interactive identification protocol. Targeting the post-quantum NIST-1 level of security\, our implementation results in signatures of 204 bytes\, secret keys of 16 bytes and public keys of 64 bytes. In particular\, the signature and public key sizes combined are an order of magnitude smaller than all other post-quantum signature schemes. On a modern workstation\, our implementation in C takes 0.6s for key generation\, 2.5s for signing\, and 50ms for verification.\nWhile the soundness of the identification protocol follows from classical assumptions\, the zero-knowledge property relies on the second main contribution of this paper.\nWe introduce a new algorithm to find an isogeny path connecting two given supersingular elliptic curves of known endomorphism rings.\nA previous algorithm to solve this problem\, due to Kohel\, Lauter\, Petit and Tignol\, systematically reveals paths from the input curves to a `special’ curve. This leakage would break the zero-knowledge property of the protocol. Our algorithm does not directly reveal such a path\, and subject to a new computational assumption\, we prove that the resulting identification protocol is zero-knowledge. URL:https://lmv.math.cnrs.fr/evenenement/crypto-antonin-leroux-inria-saclay-sqisign-compact-post-quantum-signature-from-quaternions-and-isogenies/ LOCATION:Bâtiment Descartes\, salle 301 CATEGORIES:Séminaire CRYPTO END:VEVENT BEGIN:VEVENT DTSTART;TZID=Europe/Paris:20201217T095000 DTEND;TZID=Europe/Paris:20201217T124500 DTSTAMP:20260414T165825 CREATED:20201210T155312Z LAST-MODIFIED:20201218T083310Z UID:8831-1608198600-1608209100@lmv.math.cnrs.fr SUMMARY:CRYPTO : Séminaire special dédié au concours du NIST sur la cryptographie légère DESCRIPTION:The last event of the crypto seminar will be dedicated to the ongoing NIST competition on lightweight cryptography. We plan to have different speakers to present both some second round candidates to the competition while also to expose some recent cryptanalysis results on some of the candidate ciphers. \nThe program of the event is as follows: \n\n9h50 – 10h: Opening remarks\, Yann Rotella and Christina Boura (UVSQ)\n10h – 10h15: Introduction to lightweight cryptography\, Léo Perrin (Inria)\n10h15 – 11h25: Presentation of  2-round candidates\n\n10h15 – 10h25: Forkcipher\, Virginie Lallemand (Loria)\n10h25 – 10h35: Saturnin\, André Schrottenloher (Inria)\n10h35 – 10h45: Sparkle\, Léo Perrin (Inria)\n10h45 – 10h55: Spook\, Sébastien Duval (UVSQ)\n10h55 – 11h05: Subterranean\, Yann Rotella (UVSQ)\n\n\n11h05 – 11h25: Questions\, discussions\, break\n11h25 – 12h15: Cryptanalysis\n\n11h25-11h45: MixFeed and the AES key schedule\, Clara Pernot (Inria)\n11H45-12H05: Cryptanalysis of Gimli\, Antonio Florez Gutierrez (Inria)\n12h05-12h15: Cryptanalysis ideas for Xoodyak\, Yann Rotella (UVSQ)\n\n\n12h15 – 12h45: Questions\, discussions\, closing remarks\n\nThe event will take place online on Zoom. The link to connect is: \nhttps://uvsq-fr.zoom.us/j/95522238525?pwd=YWJaUXA0MmF5MEhESkw4SVlPNTlzQT09 URL:https://lmv.math.cnrs.fr/evenenement/crypto-seminaire-special-dedie-au-concours-du-nist-sur-la-cryptographie-legere/ CATEGORIES:Séminaire CRYPTO END:VEVENT BEGIN:VEVENT DTSTART;TZID=Europe/Paris:20201210T110000 DTEND;TZID=Europe/Paris:20201210T123000 DTSTAMP:20260414T165825 CREATED:20201202T165153Z LAST-MODIFIED:20201211T163341Z UID:8784-1607598000-1607603400@lmv.math.cnrs.fr SUMMARY:CRYPTO : Sébastien Duval (UVSQ) : Exploring Crypto-Physical Dark Matter and Learning with Physical Rounding DESCRIPTION:Fresh re-keying is a recent and promising direction to handle side-channel attacks in cryptographic solutions. It is a simple\, plug-in\, efficient function that handles the core of side-channel protection directly on the secret key of cryptographic computations. State-of-the-art re-keying schemes can be viewed as a tradeoff between efficient but heuristic solutions based on binary field multiplications\, that are only secure if implemented with a sufficient amount of noise\, ans formal but more expensive solutions based on weak pseudorandom functions\, that remain secure if the adversary accesses their output in full. Recent results on “crypto dark matter” (TCC 2018) suggest that low-complexity pseudorandom functions can be obtained by mixing linear functions over different small moduli. In this paper\, we conjecture that by mixing some matrix multiplications in a prime field with a physical mapping similar to the leakage functions exploited in side-channel analysis\, we can build efficient re-keying schemes based on “crypto-physical dark matter”\, that remain secure against an adversary who can access noise-free measurements. We propose linear re-keying functions which are both more secure and cheaper than previous solutions\, and are meant to handle the core part of side-channel resistance in cryptographic functions. \nLe séminaire aura lieu en ligne via la plateforme Zoom : \nhttps://uvsq-fr.zoom.us/j/91206750927?pwd=bFR4N0pqaVVqNGZHK1hDWWZpaytjZz09 \nVeuillez contacter les organisateurs pour avoir le code de la réunion. URL:https://lmv.math.cnrs.fr/evenenement/crypto-sebastien-duval-uvsq-exploring-crypto-physical-dark-matter-and-learning-with-physical-rounding/ CATEGORIES:Séminaire CRYPTO END:VEVENT BEGIN:VEVENT DTSTART;TZID=Europe/Paris:20201119T110000 DTEND;TZID=Europe/Paris:20201119T120000 DTSTAMP:20260414T165825 CREATED:20201106T062850Z LAST-MODIFIED:20201120T141448Z UID:8708-1605783600-1605787200@lmv.math.cnrs.fr SUMMARY:CRYPTO : Nagarjun Dwarakanath (UVSQ et ATOS) : Some improvements to the FermatFHE cryptosystem DESCRIPTION:In 2019\, Antoine Joux proposed a FHE based on Fermat numbers\, with an aim to express all cryptographic functions in simple operations on the ciphertext components and their binary decompositions. We use recent results on sub-Gaussian variables to find better bounds on the errors in the cryptosystem leading to smaller parameters. We also adapt the concept of k-bit encryption and functional bootstrapping proposed by Gao to the FHE. With this variant\, we can extract the XOR and AND gates (and all other basic gates) in a single bit extraction. For larger values of k\, we also discuss possibilities of evaluating commonly used activation functions in neural networks using this mechanism. \nLe séminaire aura lieu en ligne via la plateforme Zoom : \nhttps://uvsq-fr.zoom.us/j/96588261994?pwd=YVZLYm04R2dUOFQvS25lb2QzVm9Ydz09 \nVeuillez contacter les organisateurs pour avoir le code de la réunion. URL:https://lmv.math.cnrs.fr/evenenement/crypto-nagarjun-dwarakanath-uvsq-et-atos-some-improvements-to-the-fermatfhe-cryptosystem/ CATEGORIES:Séminaire CRYPTO END:VEVENT BEGIN:VEVENT DTSTART;TZID=Europe/Paris:20201105T110000 DTEND;TZID=Europe/Paris:20201105T120000 DTSTAMP:20260414T165825 CREATED:20200930T082322Z LAST-MODIFIED:20201106T082224Z UID:8475-1604574000-1604577600@lmv.math.cnrs.fr SUMMARY:CRYPTO : Dmitrii Koshelev (LMV UVSQ) : Hashing to elliptic curves y^2 = x^3 + b provided that b is a quadratic residue. DESCRIPTION:Let Fq be a finite field and E_b : y^2 = x^3 + b be an ordinary elliptic Fq-curve of j-invariant 0 such that sqrt(b) is in Fq. In particular\, this condition is fulfilled for the curve BLS12-381 and for one of sextic twists of the curve BW6-761 (in both cases b=4). These curves are very popular in pairing-based cryptography. The article provides an efficient constant-time hashing h: Fq -> E_b(Fq) of an absolutely new type for which at worst Im(h) ~ q/6. The main idea of our hashing consists in extracting in Fq a cubic root instead of a square root as in the well known (universal) SWU hashing and in its simplified analogue. Besides\, the new hashing can be implemented without quadratic and cubic residuosity tests (as well as without inversions) in Fq. Thus in addition to the protection against timing attacks\, h is much more efficient than the SWU hashing\, which generally requires to perform two quadratic residuosity tests in Fq. For instance\, in the case of BW6-761 this allows to avoid at least approximately 2 * 761 ~ 1500 field multiplications. \nMis à jour : Suite aux récentes annonces gouvernementales\, le séminaire se tiendra en ligne via la plateforme Zoom : \nhttps://uvsq-fr.zoom.us/j/94460729478?pwd=Mk1POGxnV04vRUh1WnJUa0hyc2U0dz09 \nMot de passe :985413 URL:https://lmv.math.cnrs.fr/evenenement/crypto-dmitrii-koshelev-lmv-uvsq-hashing-to-elliptic-curves-y2-x3-b-provided-that-b-is-a-quadratic-residue/ LOCATION:Bâtiment Descartes\, salle 301 CATEGORIES:Séminaire CRYPTO END:VEVENT BEGIN:VEVENT DTSTART;TZID=Europe/Paris:20201022T103000 DTEND;TZID=Europe/Paris:20201022T123000 DTSTAMP:20260414T165825 CREATED:20201006T080745Z LAST-MODIFIED:20201023T101253Z UID:8511-1603362600-1603369800@lmv.math.cnrs.fr SUMMARY:CRYPTO : Édouard Rousseau (LMV UVSQ) : Trisymmetric multiplication formulas in finite fields DESCRIPTION:Finite fields have a central role in cryptography\, since many protocols use them\nas their foundation. Therefore\, it is crucial to have efficient arithmetic\noperations\, e.g. multiplication and addition\, over finite fields. Multiplication is usually quite\nexpensive\, hence there has been extensive research to find Karatsuba-like\nformulas reducing the number of multiplications involved when computing a bilinear\nmap over a finite field. The minimal number of multiplications in such formulas is\ncalled the bilinear complexity\, and it is also of theoretical interest to\nasymptotically understand it. Moreover\, when the bilinear maps admit some kind of\ninvariance\, it is also desirable to find formulas keeping the same invariance. In this talk\, we study\ntrisymmetric\, hypersymmetric\, and Galois invariant multiplication formulas\nover finite fields\, and we give an algorithm to find such formulas.\nWe also generalize the result that the bilinear complexity and symmetric\nbilinear complexity of the two-variable multiplication in an extension field\nare linear in the degree of the extension\, to trisymmetric bilinear\ncomplexity\, and to the complexity of t-variable multiplication for any t ≥ 3. URL:https://lmv.math.cnrs.fr/evenenement/crypto-edouard-rousseau-lmv-uvsq-trisymmetric-multiplication-formulas-in-finite-fields/ LOCATION:Bâtiment Descartes\, salle 301 CATEGORIES:Séminaire CRYPTO END:VEVENT BEGIN:VEVENT DTSTART;TZID=Europe/Paris:20201008T100000 DTEND;TZID=Europe/Paris:20201008T113000 DTSTAMP:20260414T165825 CREATED:20200928T152803Z LAST-MODIFIED:20201009T094028Z UID:8470-1602151200-1602156600@lmv.math.cnrs.fr SUMMARY:CRYPTO : Rachelle Heim (ANSSI) : Cryptanalyse de petits Keccak DESCRIPTION:Keccak est une fonction de hachage conçue par Guido Bertoni\, Joan Daemen\, Michaël Peeters et Gilles Van Assche dans le cadre de la compétition du NIST pour la standardisation d’un nouvel algorithme de hachage cryptographique. En 2012\, Keccak remporte cette compétition et certaines de ces instances sont standardisées sous le nom de SHA-3.\n\nDepuis sa conception\, Keccak a été l’objet de nombreuses cryptanalyses. Ces études sont essentielles afin de garantir la sécurité cryptographique des fonctions de hachage. Cependant\, les efforts de la communauté cryptographique se sont concentrés sur les versions standardisées. Pour motiver l’étude des autres instances de Keccak\, ses concepteurs ont organisé le Crunchy contest\, une compétition qui propose des challenges de cryptanalyse. Les organisateurs du concours ont alors remarqué que les challenges portant sur les versions de Keccak ayant un petit état (et donc non standardisées) étaient moins souvent réussis. En outre\, des candidats du second tour de la compétition Lightweight Cryptography du NIST utilisent ces petites versions. Il semble donc de plus en plus important de les étudier.\n\nC’est dans ce contexte que Yann Rotella et moi-même proposons une cryptanalyse de ces petites versions. Lors de notre étude\, nous avons montré que ces instances nécessitent une analyse spécifique\, et en particulier distincte de celle qui existe pour les versions standardisées. En utilisant des techniques de cryptanalyse souvent réservées aux attaques en pré-image\, nous avons conçue la première attaque en collision sur Keccak[40\,160]\, Keccak[72\,128] et Keccak[144\,256] réduites à deux tours. Cet exposé a pour but de présenter notre attaque. URL:https://lmv.math.cnrs.fr/evenenement/crypto-rachelle-heim-anssi-cryptanalyse-de-petits-keccak/ LOCATION:Bâtiment Descartes\, salle 301 CATEGORIES:Séminaire CRYPTO END:VEVENT BEGIN:VEVENT DTSTART;TZID=Europe/Paris:20201001T103000 DTEND;TZID=Europe/Paris:20201001T123000 DTSTAMP:20260414T165825 CREATED:20200917T122711Z LAST-MODIFIED:20201002T141813Z UID:8428-1601548200-1601555400@lmv.math.cnrs.fr SUMMARY:CRYPTO : Daniel Coggia (Inria Paris) : Efficient MILP Modelings for Sboxes and Linear Layers of SPN ciphers DESCRIPTION:Mixed Integer Linear Programming (MILP) solvers are regularly used by designers for providing security arguments and by cryptanalysts for searching for new distinguishers. For both applications\, bitwise models are more refined and permit to analyze properties of primitives more accurately than word-oriented models. Yet\, they are much heavier than these last ones. In this talk\, we first propose many new algorithms for efficiently modeling any subset of $F_2^n$ with MILP inequalities. This permits\, among others\, to model differential or linear propagation through Sboxes. We manage notably to represent the differential behaviour of the AES Sbox with three times less inequalities than before. Then\, we present two new algorithms inspired from coding theory to model complex linear layers without dummy variables. This permits us to represent many diffusion matrices\, notably the ones of Skinny-128 and AES in a much more compact way. Finally\, we demonstrate the impact of our new models on the solving time with different experiments. \n\nThis is a joint work with Christina Boura. URL:https://lmv.math.cnrs.fr/evenenement/crypto-daniel-coggia-inria-paris-efficient-milp-modelings-for-sboxes-and-linear-layers-of-spn-ciphers/ LOCATION:Bâtiment Descartes\, salle 301 CATEGORIES:Séminaire CRYPTO END:VEVENT BEGIN:VEVENT DTSTART;TZID=Europe/Paris:20200312T103000 DTEND;TZID=Europe/Paris:20200312T120000 DTSTAMP:20260414T165825 CREATED:20200306T100641Z LAST-MODIFIED:20200313T085200Z UID:7544-1584009000-1584014400@lmv.math.cnrs.fr SUMMARY:CRYPTO : Yann Rotella (UVSQ LMV) : On generating collisions in blinded keyed hashing DESCRIPTION:In this work\, we analyze keyed-hashing modes with respect to collision resistance in a blinded keyed hashing model for the attacker in both serial and parallel constructions to do compression functions in cryptography. \nThe serial construction is used in CBC-MAC for blockcipher-based or DonkeySponge for Permutation-based\, while the parallel one is used in P-MAC (blockcipher-based) or Farfalle (Permutation-based). \nWe try to obtain collisions in this setting by using differential trails existing in the inner permutation (or underlying blockcipher). Eventually\, we mount two different attack strategies for both constructions\, by using a single trail core. Our attack takes use of a huge set of trails\, all sharing the same trail core. \nMore precisely\, the expected number of inputs that we need to take into account for finding a collision is 2^W where W is defined as the sum of the weoghts of the round differentials starting from the 2nd round and where the weight of the last round is divided by 2. Also\, in the case of the parallel construction\, W is twice as large as in the case of the serial construction. \nSo in the case of a collision attack based on a single trail core\, under reasonable assumptions the parallel construction offers twice the security level than the serial construction. \nThis is joint work with Joan Daemen and Jonathan Fuchs. URL:https://lmv.math.cnrs.fr/evenenement/crypto-yann-rotella-uvsq-lmv-on-generating-collisions-in-blinded-keyed-hashing/ LOCATION:Bâtiment Descartes\, salle 301 CATEGORIES:Séminaire CRYPTO END:VEVENT BEGIN:VEVENT DTSTART;TZID=Europe/Paris:20200305T103000 DTEND;TZID=Europe/Paris:20200305T120000 DTSTAMP:20260414T165825 CREATED:20200225T131809Z LAST-MODIFIED:20200306T084500Z UID:7482-1583404200-1583409600@lmv.math.cnrs.fr SUMMARY:CRYPTO : Pierre Briaud (ENS de Lyon - Inria Paris) : An Algebraic Attack on Rank Metric Code-Based Cryptosystems DESCRIPTION: /The Rank metric decoding problem is the main problem considered in cryptography based on codes in the rank metric. Very efficient schemes based on this problem or quasi-cyclic versions of it have been proposed recently\, such as those in the submissions ROLLO and RQC currently at the second round of the NIST Post-Quantum Cryptography Standardization Process. While combinatorial attacks on this problem have been extensively studied and seem now well understood\, the situation is not as satisfactory for algebraic attacks\, for which previous work essentially suggested that they were ineffective for cryptographic parameters. In this paper\, starting from Ourivski and Johansson’s algebraic modelling of the problem into a system of polynomial equations\, we show how to augment this system with easily computed equations so that the augmented system is solved much faster via Grobner bases. This happens because the augmented system has solving degree r\, r +1 or r+2 depending on the parameters\, where r is the rank weight\, which we show by extending results from Verbel et al. (PQCrypto 2019) on systems arising from the MinRank problem. We give complexity bounds for this approach as well as practical timings of an implementation using magma. This improves upon the previously known complexity estimates for both Grobner basis and (non-quantum) combinatorial approaches\, and for example leads to an attack in 200 bits on ROLLO-I-256 whose claimed security was 256 bits. \nThis is a joint work with Magali Bardet\,  Maxime Bros\, Philippe Gaborit\, Vincent Neiger\, Olivier Ruatta and Jean-Pierre Tillich. URL:https://lmv.math.cnrs.fr/evenenement/crypto-pierre-briaud-ens-de-lyon-inria-paris-an-algebraic-attack-on-rank-metric-code-based-cryptosystems/ LOCATION:Bâtiment Descartes\, salle 301 CATEGORIES:Séminaire CRYPTO END:VEVENT BEGIN:VEVENT DTSTART;TZID=Europe/Paris:20200227T103000 DTEND;TZID=Europe/Paris:20200227T120000 DTSTAMP:20260414T165825 CREATED:20200221T101510Z LAST-MODIFIED:20200302T083447Z UID:7466-1582799400-1582804800@lmv.math.cnrs.fr SUMMARY:CRYPTO : Matthieu Lequesne (Inria Paris) : « Decoding challenge : une nouvelle série de challenges pour la cryptographie basée sur les codes correcteurs » DESCRIPTION:La cryptographie basée sur les codes correcteurs d’erreur est une des approches prometteuses pour obtenir des primitives cryptographiques qui résistent à l’ordinateur quantique. Un tiers des algorithmes proposés pour la standardisations post-quantique sont basés sur cette famille de problèmes.\nLes cryptosystèmes à base de code reposent majoritairement sur le principe suivant. On choisit un code correcteur qui possède une certaine structure algébrique\, qui permet de corriger beaucoup d’erreurs. Pour chiffrer un message\, on l’encode puis on ajoute des erreurs. Une personne qui ne connaît pas la structure du code ne peut pas corriger les erreurs\, donc ne peut pas déchiffrer le message. La clé publique est donc la donnée du code\, mais sous une forme qui ne révèle pas sa structure. La clé privée est la donnée du code sous sa forme structurée\, pour permettre le décodage.\nPour attaquer un tel système de chiffrement\, deux approches sont possibles. Soit l’attaquant arrive à retrouver la structure algébrique cachée du code\, puis corrige les erreurs comme s’il avait la clé privée. Dans ce cas\, cela signifie qu’il arrive à distinguer le code de la clé publique d’un code aléatoire. Soit l’attaquant ne cherche pas à retrouver la structure du code\, considère qu’il s’agit d’un code totalement aléatoire\, et essaie simplement de corriger toutes les erreurs avec ce code. On parle alors d’attaques génériques (car elle ne dépendent pas de la famille de codes choisie).\nOn s’intéresse ici au second cas. Pour juger le niveau de sécurité d’un cryptosystème\, il est important de comprendre la complexité du problème de décodage générique. Depuis plusieurs décennies\, une série de travaux propose des algorithmes de plus en plus performants pour essayer de réduire la complexité de ce problème. Mais les études de complexité s’intéressent principalement à l’exposant asymptotique et ces algorithmes ont rarement été implémentés. Pour mieux comprendre la sécurité de ce problème en pratique\, nous avons lancé en août 2019 un site internet « Decoding Challenge » qui propose des instances de difficulté croissante du problème de décodage générique.\nDans cet exposé\, on expliquera les principales approches pour résoudre ce problème et l’état actuel des connaissances sur la complexité du problème de décodage générique en pratique. \nLe site internet : http://decodingchallenge.org/ \nCet exposé était initialement prévu le 12 décembre 2019 mais a été annulé suite aux grèves de transport. URL:https://lmv.math.cnrs.fr/evenenement/crypto-matthieu-lequesne-inria-paris-decoding-challenge-une-nouvelle-serie-de-challenges-pour-la-cryptographie-basee-sur-les-codes-correcteurs-2/ LOCATION:Bâtiment Descartes\, salle 301 CATEGORIES:Séminaire CRYPTO END:VEVENT BEGIN:VEVENT DTSTART;TZID=Europe/Paris:20191212T103000 DTEND;TZID=Europe/Paris:20191212T120000 DTSTAMP:20260414T165825 CREATED:20191202T201038Z LAST-MODIFIED:20191213T083647Z UID:7036-1576146600-1576152000@lmv.math.cnrs.fr SUMMARY:CRYPTO : Matthieu Lequesne (Inria Paris) : "Decoding challenge : une nouvelle série de challenges pour la cryptographie basée sur les codes correcteurs" DESCRIPTION:La cryptographie basée sur les codes correcteurs d’erreur est une des approches prometteuses pour obtenir des primitives cryptographiques qui résistent à l’ordinateur quantique. Un tiers des algorithmes proposés pour la standardisations post-quantique sont basés sur cette famille de problèmes.\nLes cryptosystèmes à base de code reposent majoritairement sur le principe suivant. On choisit un code correcteur qui possède une certaine structure algébrique\, qui permet de corriger beaucoup d’erreurs. Pour chiffrer un message\, on l’encode puis on ajoute des erreurs. Une personne qui ne connaît pas la structure du code ne peut pas corriger les erreurs\, donc ne peut pas déchiffrer le message. La clé publique est donc la donnée du code\, mais sous une forme qui ne révèle pas sa structure. La clé privée est la donnée du code sous sa forme structurée\, pour permettre le décodage.\nPour attaquer un tel système de chiffrement\, deux approches sont possibles. Soit l’attaquant arrive à retrouver la structure algébrique cachée du code\, puis corrige les erreurs comme s’il avait la clé privée. Dans ce cas\, cela signifie qu’il arrive à distinguer le code de la clé publique d’un code aléatoire. Soit l’attaquant ne cherche pas à retrouver la structure du code\, considère qu’il s’agit d’un code totalement aléatoire\, et essaie simplement de corriger toutes les erreurs avec ce code. On parle alors d’attaques génériques (car elle ne dépendent pas de la famille de codes choisie).\nOn s’intéresse ici au second cas. Pour juger le niveau de sécurité d’un cryptosystème\, il est important de comprendre la complexité du problème de décodage générique. Depuis plusieurs décennies\, une série de travaux propose des algorithmes de plus en plus performants pour essayer de réduire la complexité de ce problème. Mais les études de complexité s’intéressent principalement à l’exposant asymptotique et ces algorithmes ont rarement été implémentés. Pour mieux comprendre la sécurité de ce problème en pratique\, nous avons lancé en août 2019 un site internet « Decoding Challenge » qui propose des instances de difficulté croissante du problème de décodage générique.\nDans cet exposé\, on expliquera les principales approches pour résoudre ce problème et l’état actuel des connaissances sur la complexité du problème de décodage générique en pratique. \nLe site internet : http://decodingchallenge.org/ URL:https://lmv.math.cnrs.fr/evenenement/crypto-matthieu-lequesne-inria-paris-decoding-challenge-une-nouvelle-serie-de-challenges-pour-la-cryptographie-basee-sur-les-codes-correcteurs/ LOCATION:Bâtiment Descartes\, salle 301 CATEGORIES:Séminaire CRYPTO END:VEVENT BEGIN:VEVENT DTSTART;TZID=Europe/Paris:20191128T110000 DTEND;TZID=Europe/Paris:20191128T120000 DTSTAMP:20260414T165825 CREATED:20191108T195114Z LAST-MODIFIED:20191202T082827Z UID:6843-1574938800-1574942400@lmv.math.cnrs.fr SUMMARY:CRYPTO : Robin Larrieu (LMV/UVSQ) : Arithmétique rapide pour des corps finis (répétition de soutenance de thèse) DESCRIPTION:La multiplication de polynômes est une opération fondamentale en théorie de la complexité.\nEn effet\, pour de nombreux problèmes d’arithmétique\, la complexité des algorithmes s’exprime habituellement en fonction de la complexité de la multiplication. Un meilleur algorithme de multiplication permet ainsi d’effectuer les opérations concernées plus rapidement. Un résultat de 2016 a établi une meilleure complexité asymptotique pour la multiplication de polynômes dans des corps finis. Cet article constitue le point de départ de la thèse ; l’objectif est d’étudier les conséquences à la fois théoriques et pratiques de la nouvelle borne de complexité. \nLa première partie s’intéresse à la multiplication de polynômes à une variable. Cette partie présente deux nouveaux algorithmes censés accélérer le calcul en pratique (plutôt que d’un point de vue asymptotique). S’il est difficile dans le cas général d’observer l’amélioration prévue\, certains cas précis sont particulièrement favorables. En l’occurrence\, le second algorithme proposé\, spécifique aux corps finis\, conduit à une meilleure implémentation de la multiplication dans F_2[X]\, environ deux fois plus rapide que les logiciels précédents. \nLa deuxième partie traite l’arithmétique des polynômes à plusieurs variables modulo un idéal\, telle qu’utilisée par exemple pour la résolution de systèmes polynomiaux. Ce travail suppose une situation simplifiée\, avec seulement deux variables et sous certaines hypothèses de régularité. Dans ce cas particulier\, la deuxième partie de la thèse donne des algorithmes de complexité asymptotiquement optimale (à des facteurs logarithmiques près)\, par rapport à la taille des entrées/sorties. L’implémentation pour ce cas spécifique est alors nettement plus rapide que les logiciels généralistes\, le gain étant de plus en plus marqué lorsque la taille de l’entrée augmente. URL:https://lmv.math.cnrs.fr/evenenement/crypto-robin-larrieu-lmv-uvsq-arithmetique-rapide-pour-des-corps-finis-repetition-de-soutenance-de-these/ LOCATION:Bâtiment Descartes\, salle 301 CATEGORIES:Séminaire CRYPTO END:VEVENT END:VCALENDAR