Table of contents

  • This session has been presented November 07, 2003.

Description

  • Speaker

    Magali Bardet - Université Pierre et Marie Curie

Pour de nombreuses applications dans le domaine de la cryptographie (par exemple pour des systèmes de chiffrement où la clef publique est un système polynômial comme HFE, ou des systèmes de registres filtrés), nous sommes amenés à résoudre des systèmes à coefficients dans le corps fini GF(2), pour lesquels les seules solutions intéressantes sont celles dans GF(2). On a donc à résoudre un système modulo 2 auquel on ajoute les équations de corps X^2+X sur chacunes des coordonnées. Nous nous intéressons au problème de la complexité du calcul d'une base de Gröbner pour des systèmes ``suffisamment génériques'' et surdéterminés, à coefficients dans GF(2) et comprenant les équations de corps. Notons que l'exemple de Mayr-Meyer, dont la complexité est doublement exponentielle, n'est pas ``générique'' et que la seule présence des équations de corps dans le système implique que le système n'a qu'un nombre fini de solutions sans multiplicités, la complexité globale est donc au pire simplement exponentielle. Le but de cet exposé est de donner des bornes fines sur cette complexité.<br/> Nous commençons l'exposé par des rappels sur les suites semi-régulières et sur leurs propriétés (pour tous les détails sur cette notion, voir l'exposé du séminaire de Calcul formel et Complexité par le même orateur). De manière informelle, une suite f_1,...,f_m est semi-régulière si les seules relations vérifiées par les f_i en dessous d'un certain degré, dit degré de régularité, sont les relations engendrées par les relations triviales f_if_j=f_jf_i. La définition de suite semi-régulière convient comme définition mathématique de ``suffisamment générique'', et dans ce cas la complexité du calcul d'une base de Gröbner est bien comprise. Pour de telles suites, on peut prévoir les tailles exactes de chaque matrice intervenant dans la version matricielle de l'algorithme de calcul de base de Gröbner F5 de Jean-Charles Faugère. Cela nous permet de calculer le degré de régularité, qui est lié au coût (arithmétique) global du calcul de la base de Gröbner, pour tout ordre gradué par le degré.<br/> Dans le cas de systèmes à coefficients dans GF(2) avec équations de corps, il n'existe aucune suite semi-régulière au sens précédent (à cause des relations f_i^2=f_i). Nous étendons donc la définition aux systèmes modulo 2 avec équations de corps, nous adaptons l'algorithme F5 (nouveau critère). A nouveau, les tailles des matrices dans l'algorithme F5 sont bien déterminées, ce qui nous permet de calculer exactement le degré de régularité de ces suites. En utilisant les mêmes techniques d'analyse asymptotique que pour les suites semi-régulières à coefficients entiers, nous calculons un développement asymptotique de ce degré en fonction du nombre de variables. Ainsi, pour une suite de n polynômes quadratiques en n variables modulo 2 avec équations de corps, le degré de régularité est D_reg \sim n/11.114 + 1.0034\,{\sqrt [3]{{n}}} + 94.775 + O\left( {\frac {1}{\sqrt [3]{{n}}}} \right). Cette estimation est très précise, elle coincide à 1 près avec la valeur exacte de D_reg dès n\ge 3. Nous donnons la valeur explicite de chaque coefficient, et le coût global du calcul est $\binom{n}{D_reg}}^L où L est le coefficient d'algèbre linéaire. Nous conjecturons que ``presque toute suite'' est une suite semi-régulière.

Next sessions

  • Post-quantum day of the cryptography seminar

    • November 20, 2026 (09:30 - 15:15)

    • Inria / IRISA - Room Aurigny (D165) - A map of the Beaulieu campus can be viewed at: https://www.univ-rennes.fr/en/beaulieu-campus-map (the building is south of the campus)

    A scientific day devoted to post-quantum cryptography, held in the wake of the European Cyber Week, with talks more technical than those presented at the ECW. To register for lunch, please do so before oct 30th using this link. The event has been moved to the IRISA / Inria building, Room Aurigny (D165). You will need an ID card to enter the building. 
  • Chiffrement homomorphe à l'aide des groupes après Nuida

    • November 27, 2026 (13:45 - 14:45)

    • IRMAR - Université de Rennes - Campus Beaulieu Bat. 22, RDC, Rennes - Amphi Lebesgue

    Speaker : Pierre Guillot - Ravel Technologies/Université de strasbourg

    Nuida et d'autres ont montré comment on peut obtenir un protocole de chiffrement pleinement homomorphe si l'on sait chiffrer les éléments d'un groupe G convenable, tout en sachant faire l'opération de G "en homomorphe". Les exemples étaient jusqu'à présent limités au chiffrement d'un bit à la fois, avec beaucoup d'opérations à effectuer pour "simuler" les portes logiques usuelles. Je vais[…]
    • Cryptography

  • Post-Quantum Signatures from Symmetric-Key-Friendly Techniques: From MPC-in-the-Head to VOLE-in-the-Head

    • December 04, 2026 (13:45 - 14:45)

    • IRMAR - Université de Rennes - Campus Beaulieu Bat. 22, RDC, Rennes - Amphi Lebesgue

    Speaker : Dung Bui - Northwestern University

    The MPC-in-the-Head (MPCitH) paradigm turns a secure multiparty computation protocol into a zero-knowledge proof and, via Fiat–Shamir, into a signature scheme whose security relies only on symmetric-key primitives. The framework of Katz, Kolesnikov and Wang (KKW, CCS18), which moves most of the MPC work into a committed preprocessing phase that the verifier checks by opening all-but-one of the[…]
  • Distinguishing and Attacking McEliece Cryptosystems Using GRS Codes with Higher-Weight Mask

    • December 11, 2026 (13:45 - 14:45)

    • IRMAR - Université de Rennes - Campus Beaulieu Bat. 22, RDC, Rennes - Amphi Lebesgue

    Speaker : Michael Schaller - University of Zürich, Applied Algebra group

    Due to the insecurity of McEliece cryptosystems instantiated with Generalized Reed-Solomon (GRS) codes, there have been several proposals of McEliece type systems that replace the permutation matrix by a matrix $M$ with larger row and column weight. In many of them, the secret key is still a GRS code.There have been successful attacks on some of those schemes with row and column weight between $1$[…]
  • Nouveaux doctorants

    • January 08, 2027 (13:45 - 14:45)

    • Salle Guernesey à l'ISTIC

    Exposés courts des nouveaux doctorants (Elouan, Quentin, Eliot)
Show previous sessions