🔢 mathematics

Cryptanalysis of the Legendre Pseudorandom Function over Extension Fields

Cet article présente la première analyse cryptographique complète de la fonction pseudo-aléatoire de Legendre sur les corps d'extension, démontrant que des attaques structurelles efficaces permettent de récupérer la clé secrète dans les deux modèles de menace passif et actif, et établissant ainsi la nécessité d'utiliser des variantes de degré supérieur pour garantir une sécurité exponentielle.

Auteurs originaux : Daksh Pandey

Publié 2026-04-07

📖 5 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Daksh Pandey

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

🕵️‍♂️ L'Histoire : La Serrure Légende et le Nouveau Terrain de Jeu

Imaginez que vous avez une serrure mathématique très intelligente, appelée la "Fonction Pseudo-Aléatoire de Legendre". C'est une serrure utilisée pour protéger des secrets dans des systèmes très avancés (comme les preuves à divulgation nulle de connaissance ou le calcul multipartite).

Jusqu'à récemment, cette serrure fonctionnait sur un terrain plat et simple (les nombres entiers classiques, appelés "champs premiers"). Les experts savaient comment elle fonctionnait et savaient qu'elle était solide.

Mais les ingénieurs ont eu une idée : "Et si on utilisait cette serrure sur un terrain plus grand et plus complexe ?" Ce nouveau terrain, c'est un "champ d'extension" (noté $F_{p^r}$ ). C'est comme passer d'une grille de 10x10 cases à une grille infinie où chaque case est un petit polynôme (une équation avec des lettres).

L'auteur de l'article, Daksh Pandey, s'est demandé : "Est-ce que cette serrure est toujours sûre sur ce nouveau terrain ?"

La réponse est un grand NON. Il a découvert deux façons de la casser.

🔑 Le Problème : La "Fracture Sans Report"

Sur le terrain simple, si vous demandez à la serrure de s'ouvrir pour les numéros 1, 2, 3, 4... elle réagit de manière très prévisible et continue. C'est comme marcher sur un trottoir droit.

Sur le nouveau terrain complexe (les polynômes), il y a une règle bizarre : quand on ajoute 1, il n'y a pas de "report" de chiffre.

L'analogie : Imaginez un compteur de voiture où, au lieu de passer de 199 à 200 (avec un report), les roues tournent indépendamment. Si vous avez 199, le chiffre des unités passe à 0, mais le chiffre des dizaines reste 9. Le nombre devient 190, pas 200.
Cela crée une "fracture" : la séquence de nombres ne suit plus une ligne droite. Elle saute de manière étrange.

Les chercheurs pensaient que cette "fracture" était une super défense. Ils se disaient : "Les voleurs ne peuvent pas utiliser leurs vieilles méthodes de prédiction car la route est cassée !".

Mais Daksh a prouvé que c'était une fausse sécurité.

🛠️ L'Attaque 1 : Le Détective Passif (La méthode des "Empreintes")

Même si la route est "cassée", elle ne l'est pas au hasard. Elle suit un motif répétitif très précis, comme les vagues de l'océan.

L'astuce du détective : Daksh a inventé une technique appelée "Signature Différentielle". Imaginez que vous ne regardez pas les voitures une par une, mais que vous regardez la forme de leurs traces de pneus.
Le tri : Même si les voitures sautent, elles laissent toujours le même type de trace pour un même type de saut. Le détective peut donc grouper toutes les traces identiques dans des "paniers" (des buckets).
Le résultat : En triant ces traces, le détective peut reconstituer le chemin caché et trouver la clé secrète, même sans forcer la serrure. C'est comme si vous pouviez deviner le code d'une alarme en observant comment les lumières clignotent dans un ordre répétitif, même si elles clignotent de manière bizarre.

Résultat : On peut casser la serrure juste en regardant (attaque passive), mais cela prend un peu de temps.

🚀 L'Attaque 2 : Le Pirate Actif (La méthode Géométrique)

Si le voleur est plus agressif et peut choisir lui-même les numéros qu'il demande à la serrure (attaque active), c'est encore pire.

Le changement de stratégie : Au lieu de demander les numéros 1, 2, 3... (addition), le pirate demande des nombres qui se multiplient : 1, 2, 4, 8, 16... (une suite géométrique).
La magie des mathématiques : Sur ce terrain complexe, la multiplication se comporte beaucoup mieux que l'addition. Elle conserve une propriété magique appelée "homomorphisme".
Le résultat : Cette astuce annule complètement la "fracture" bizarre. La serrure se comporte comme si elle était sur le terrain simple d'origine. Le pirate peut alors utiliser une méthode de collision (comparer des tables de données) pour trouver la clé très rapidement, beaucoup plus vite que la première méthode.

C'est comme si le pirate trouvait un passage secret qui court-circuite toute la complexité du terrain.

💡 La Solution : La Serrure à Plusieurs Niveaux

Alors, faut-il abandonner cette serrure ? Non, mais il faut la renforcer.

L'article explique que la version actuelle (degré 1, une seule équation) est trop faible. Pour être sûr, il faut passer à une serrure à plusieurs niveaux (degré $d \ge 2$ ).

L'analogie : Au lieu d'avoir une seule équation simple ( $x + K$ ), on utilise une équation complexe avec plusieurs termes ( $x^2 + K_1x + K_0$ ).
Cela brise la magie de la multiplication géométrique. Le pirate ne peut plus séparer les variables pour trouver la clé facilement. C'est comme passer d'une porte simple à un coffre-fort avec trois combinaisons différentes qui doivent être tournées en même temps.

📝 En Résumé

Le constat : La version simple de la serrure "Legendre" sur les grands terrains mathématiques (champs d'extension) est cassable.
La raison : La "fracture" due à l'absence de report de chiffres n'est pas une vraie protection ; elle est trop prévisible.
L'attaque : On peut la casser soit en observant patiemment (passif), soit en forçant des questions spécifiques (actif) pour annuler la complexité.
Le conseil : Pour que ce système soit sûr dans le futur (pour la cryptographie quantique ou le calcul privé), il faut utiliser des versions plus complexes avec des équations de degré supérieur (au moins 2).

C'est une leçon importante en sécurité : la complexité apparente ne garantit pas la sécurité. Parfois, c'est la structure cachée derrière la complexité qui trahit le système.

Titre de l'article

Cryptanalyse de la Fonction Pseudo-Aléatoire de Legendre sur les Corps d'Extension
Auteur : Daksh Pandey (IIT Roorkee)

1. Problématique et Contexte

La Fonction Pseudo-Aléatoire (PRF) de Legendre est une primitive cryptographique efficace, largement utilisée dans les protocoles de Calcul Multi-Parties (MPC) et de Preuves à Connaissance Zéro (ZKP) en raison de sa faible complexité multiplicative. Historiquement, sa sécurité a été étudiée sur des corps premiers $\mathbb{F}_p$ . Cependant, pour optimiser le débit dans certains protocoles, l'attention s'est portée vers son instantiation sur des corps d'extension $\mathbb{F}_{p^r}$ .

Le problème central abordé dans cet article est l'absence d'analyse de sécurité complète pour la variante de Legendre de degré unique ( $d=1$ ) sur ces corps d'extension. Les auteurs postulent que le passage de l'arithmétique scalaire (sur $\mathbb{F}_p$ ) à l'arithmétique polynomiale (sur $\mathbb{F}_{p^r}$ ) modifie fondamentalement le comportement des requêtes séquentielles, créant potentiellement de nouvelles vulnérabilités structurelles ou, à l'inverse, une fausse impression de sécurité due à la rupture des attaques par collision classiques.

2. Méthodologie et Fondements Mathématiques

L'étude se base sur la représentation des éléments de $\mathbb{F}_{p^r}$ comme des polynômes de degré au plus $r-1$ à coefficients dans $\mathbb{F}_p$ .

Encodage des Entrées : Les entiers $n$ sont mappés vers des polynômes via une expansion en base $p$ . Une propriété cruciale est que l'addition de polynômes dans $\mathbb{F}_{p^r}$ se fait coefficient par coefficient sans retenue (no-carry) vers les degrés supérieurs.
Symbole de Legendre Généralisé : La fonction évalue le symbole de Legendre généralisé $L(A(x)) = A(x)^{\frac{p^r-1}{2}} \pmod{I(x)}$ , où $I(x)$ est un polynôme irréductible.
Modèles de Menace :
1. Passif : L'attaquant observe une séquence de bits générée par des requêtes séquentielles (compteur incrémental).
2. Actif (Requête Choisie) : L'attaquant peut interroger l'oracle avec des séquences spécifiques (géométriques).

3. Contributions Clés et Résultats

L'article présente deux attaques majeures démontrant l'insécurité de la variante $d=1$ sur $\mathbb{F}_{p^r}$ .

A. Attaque Passive : La « Fracture Sans Retenue » et les Signatures Différentielles

Dans les corps premiers, les attaques par collision utilisent la continuité de la différence entre entrées successives ( $\Delta = 1$ ). Sur $\mathbb{F}_{p^r}$ , l'addition de 1 à un entier $n$ provoque des « retenues » dans l'arithmétique entière, mais pas dans l'arithmétique polynomiale.

Observation : Cela crée une « fracture asynchrone » où la différence $\Delta_n$ n'est pas constante mais prend des valeurs dans l'ensemble $\{x^k + 1\}$ , dépendant de la valuation $p$ -adique de $n$ .
Vulnérabilité : Bien que cela brise les fenêtres glissantes classiques, la séquence de ces différences est déterministiquement périodique.
Nouvelle Méthode : Les auteurs introduisent une technique de « bucketing » (regroupement) basée sur les Signatures Différentielles. En regroupant les fenêtres de la séquence de bits selon la forme structurelle de leurs différences polynomiales, l'attaquant peut contourner la défense « sans retenue ».
Résultat : Récupération passive de la clé secrète avec une complexité de $O(U \cdot p^r / M)$ , où $U$ est la distance d'unicité et $M$ le nombre de bits observés.

B. Attaque Active : Séquences Géométriques et Homomorphisme Multiplicatif

L'attaquant actif contourne totalement les limitations additives en choisissant des requêtes non pas additives, mais multiplicatives.

Stratégie : L'attaquant interroge l'oracle avec une suite géométrique $g^i$ générée par un générateur primitif $g$ du groupe multiplicatif $\mathbb{F}_{p^r}^*$ .
Réduction Algébrique : Grâce à la propriété multiplicative du symbole de Legendre, l'évaluation $L(g^i + K)$ se factorise :
$L(g^i + K) = L(K) \cdot L(g^{i+j} + 1)$
où $j$ est un décalage discret lié à la clé $K$ .
Résultat : Cela transforme le problème en une recherche de décalage pur sur une séquence de référence universelle. L'attaquant peut généraliser l'attaque par collision de table d'état de l'art pour extraire la clé en $O(p^r / M)$ opérations, éliminant ainsi toute sécurité structurelle pour la variante $d=1$ .

4. Implications et Limites de Sécurité

Insécurité de la Variante $d=1$ : Les résultats prouvent formellement que la PRF de Legendre de degré 1 sur les corps d'extension est brisée tant en mode passif qu'actif. La « fracture sans retenue » ne suffit pas à garantir la sécurité.
Nécessité des Variants de Degré Supérieur ( $d \ge 2$ ) :
- Pour contrer l'attaque géométrique, les auteurs suggèrent d'utiliser des clés composées de polynômes de degré $d \ge 2$ (ex: $x^2 + K_1x + K_0$ ).
- Dans ce cas, la factorisation algébrique n'est plus possible car les termes intermédiaires ( $K_1x$ ) empêchent l'isolement de la clé.
- Cependant, des attaques avancées (comme les attaques « Meet-in-the-Middle » sur des formes réduites) pourraient encore réduire la complexité de $O(p^{dr})$ à $O(p^{\lfloor d/2 \rfloor r})$ .
Recommandation : Pour une sécurité exponentielle robuste contre les réductions structurelles dans $\mathbb{F}_{p^r}$ , il est impératif d'utiliser des variantes de degré $d \ge 3$ ou $4$.

5. Signification et Conclusion

Cet article constitue la première analyse cryptographique complète de la PRF de Legendre sur les corps d'extension. Il démontre que le changement de domaine (de $\mathbb{F}_p$ à $\mathbb{F}_{p^r}$ ) n'apporte pas une sécurité intrinsèque supplémentaire, mais introduit au contraire des vulnérabilités structurelles exploitables par des attaques passives et actives sophistiquées.

La conclusion principale est que les implémentations futures de la PRF de Legendre pour le MPC et le ZKP sur des corps d'extension doivent abandonner la variante de degré 1 et adopter des variantes de degré supérieur ( $d \ge 2$ , idéalement $d \ge 3$ ) pour maintenir une marge de sécurité exponentielle. Les auteurs ont également rendu publics leurs codes sources (Python) pour valider ces attaques.