Description
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
-
Verification of Rust Cryptographic Implementations with Aeneas
Speaker : Aymeric Fromherz - Inria
From secure communications to online banking, cryptography is the cornerstone of most modern secure applications. Unfortunately, cryptographic design and implementation is notoriously error-prone, with a long history of design flaws, implementation bugs, and high-profile attacks. To address this issue, several projects proposed the use of formal verification techniques to statically ensure the[…] -
On the average hardness of SIVP for module lattices of fixed rank
Speaker : Radu Toma - Sorbonne Université
In joint work with Koen de Boer, Aurel Page, and Benjamin Wesolowski, we study the hardness of the approximate Shortest Independent Vectors Problem (SIVP) for random module lattices. We use here a natural notion of randomness as defined originally by Siegel through Haar measures. By proving a reduction, we show it is essentially as hard as the problem for arbitrary instances. While this was[…] -
Lightweight (AND, XOR) Implementations of Large-Degree S-boxes
Speaker : Marie Bolzer - LORIA
The problem of finding a minimal circuit to implement a given function is one of the oldest in electronics. In cryptography, the focus is on small functions, especially on S-boxes which are classically the only non-linear functions in iterated block ciphers. In this work, we propose new ad-hoc automatic tools to look for lightweight implementations of non-linear functions on up to 5 variables for[…]-
Cryptography
-
Symmetrical primitive
-
Implementation of cryptographic algorithm
-
-
Algorithms for post-quantum commutative group actions
Speaker : Marc Houben - Inria Bordeaux
At the historical foundation of isogeny-based cryptography lies a scheme known as CRS; a key exchange protocol based on class group actions on elliptic curves. Along with more efficient variants, such as CSIDH, this framework has emerged as a powerful building block for the construction of advanced post-quantum cryptographic primitives. Unfortunately, all protocols in this line of work are[…] -
Endomorphisms via Splittings
Speaker : Min-Yi Shen - No Affiliation
One of the fundamental hardness assumptions underlying isogeny-based cryptography is the problem of finding a non-trivial endomorphism of a given supersingular elliptic curve. In this talk, we show that the problem is related to the problem of finding a splitting of a principally polarised superspecial abelian surface. In particular, we provide formal security reductions and a proof-of-concept[…]-
Cryptography
-