Modèle du groupe générique

En cryptologie, le modèle du groupe générique^{[Note 1]} est un cadre idéalisé dans lequel on peut prouver la sécurité de certains algorithmes cryptographiques, en particulier les signatures numériques. Il postule l'existence d'un oracle que les participants à un protocole cryptographique (signataire comme adversaire) peuvent interroger pour effectuer des opérations de groupe. Dans ce modèle, les éléments du groupe sont représentés par des chaînes de bits aléatoires, que seul l'oracle sait manipuler de manière cohérente. Ce modèle tente de capturer l'idée d'un groupe mathématique abstrait, indépendant d'un choix particulier de représentation.

Le modèle du groupe générique a été introduit en 1997 par le cryptologue Victor Shoup^[1]Modèle:,^{[Note 2]}Modèle:,^[2], étendant des travaux de Vassili Illich Nechaev^[3]. Il a notamment permis de montrer, dans ce modèle, que la difficulté de calculer un logarithme discret est $Ω (\sqrt{p})$ , où $p$ est l'ordre (premier) du groupe^{[Note 3]}Modèle:,^[1]Modèle:,^[4]Modèle:,^[5]. Cette borne est atteinte par des algorithmes connus, comme le rho de Pollard, qui sont donc optimaux dans le modèle du groupe générique.

Les groupes concrets, tels que les groupes multiplicatifs issus des corps finis, ne sont cependant pas des groupes génériques : il existe dans ces contextes des algorithmes strictement plus efficaces que la borne de Shoup, par exemple le crible du corps de nombres. Toutefois pour certains groupes concrets les algorithmes génériques sont les meilleurs connus à ce jour : c'est notamment le cas des groupes de points rationnels sur des courbes elliptiques. Cette observation est une des motivations derrière le développement de la cryptographie sur courbes elliptiques.

Une limitation du modèle du groupe générique est l'existence de schémas prouvés sûrs dans ce modèle, qui s'avèrent complètement cassés dès que le groupe générique est remplacé par n'importe quel groupe concret^[6]Modèle:,^{[Note 4]}Modèle:,^[7]. Une autre limitation est liée à l'existence d'adversaires non uniformes, c'est-à-dire capables d'effectuer un calcul préliminaire « hors ligne » avant de s'attaquer au cryptosystème. Face à de tels adversaires, les estimations de sécurité produites dans le modèle du groupe générique sont trop optimistes^[8]. La valeur de ce modèle est donc heuristique^[7]Modèle:,^[9].

Le modèle du groupe générique a été étendu à d'autres structures algébriques, comme les anneaux^[10] ou les corps^[11], et à d'autres contextes cryptographiques comme les « groupes bilinéaires » utilisés en cryptographie à base de couplages^[12].

Exemples importants

La sécurité des signatures ECDSA a été réduite à la difficulté du problème du logarithme discret sur une courbe elliptique et la résistance d'une certaine fonction de hachage cryptographique aux collisions^[13]. Le résultat ne s'applique pas à DSA cependant, car le groupe sous-jacent n'est pas générique^[13].
La sécurité des signatures d'ElGamal a été réduite à la difficulté du problème du logarithme discret dans une combinaison du modèle du groupe générique et de l'oracle aléatoire^[14].
La sécurité des signatures courtes de Boneh-Boyen a été réduite à la difficulté d'une variante du problème de Diffie-Hellman calculatoire dans le modèle du groupe générique^[15].
La sécurité du cryptosystème RSA a été réduite à la factorisation dans le modèle de l'anneau générique^[10]. L'importance de ce résultat est toutefois à relativiser, dans la mesure où l'anneau $ℤ / (n)$ est substantiellement différent d'un anneau générique^[9]Modèle:,^{[Note 5]}Modèle:,^[16].

Voir aussi

Notes et références

Notes

↑ Souvent abrégé GGM pour l'anglais generic group model.
↑ Un modèle a priori différent mais portant le même nom a été proposé par (Maurer 2005). Il est en fait équivalent au modèle de Shoup (Jager et Schwenk 2008).
↑ Si l'ordre du groupe est un nombre composé $n$ , alors des algorithmes spécialisés peuvent s'appliquer et sont généralement fonction de la racine du plus petit facteur de $n$ (comme l'algorithme de Pohlig-Hellman). Voir par exemple (May et Ozerov 2014) pour des algorithmes encore plus performants.
↑ Cette situation (et la manière dont sont construits les schémas affectés) est analogue à celle du modèle de l'oracle aléatoire. Pour une discussion, voir (Koblitz et Menezes 2007).
↑ Un autre exemple est le calcul du symbole de Jacobi d'un entier, qui est difficile dans le modèle de l'anneau générique, mais pour lequel il existe un algorithme efficace dans $ℤ / (n)$ . Voir (Jager et Schwenk 2012) pour une preuve et une discussion et (Boneh et Venkatesan 1998) pour des arguments heuristiques contre l'équivalence de RSA à la factorisation.

Références

Modèle:Références

Modèle:Palette

Modèle:Portail

[1] Souvent abrégé GGM pour l'anglais generic group model.

[3] Un modèle a priori différent mais portant le même nom a été proposé par (Maurer 2005). Il est en fait équivalent au modèle de Shoup (Jager et Schwenk 2008).

[6] Si l'ordre du groupe est un nombre composé $n$ , alors des algorithmes spécialisés peuvent s'appliquer et sont généralement fonction de la racine du plus petit facteur de $n$ (comme l'algorithme de Pohlig-Hellman). Voir par exemple (May et Ozerov 2014) pour des algorithmes encore plus performants.

[10] Cette situation (et la manière dont sont construits les schémas affectés) est analogue à celle du modèle de l'oracle aléatoire. Pour une discussion, voir (Koblitz et Menezes 2007).

[20] Un autre exemple est le calcul du symbole de Jacobi d'un entier, qui est difficile dans le modèle de l'anneau générique, mais pour lequel il existe un algorithme efficace dans $ℤ / (n)$ . Voir (Jager et Schwenk 2012) pour une preuve et une discussion et (Boneh et Venkatesan 1998) pour des arguments heuristiques contre l'équivalence de RSA à la factorisation.

[:0-2] 1,0 et ^1,1 Modèle:Chapitre

[4] Modèle:Chapitre

[5] Modèle:Article

[7] Modèle:Chapitre

[8] Modèle:Chapitre

[9] Modèle:Chapitre

[:1-11] 7,0 et ^7,1 Modèle:Article

[12] Modèle:Chapitre

[:2-13] 9,0 et ^9,1 Modèle:Article

[:3-14] 10,0 et ^10,1 Modèle:Chapitre

[15] Modèle:Chapitre

[16] Modèle:Chapitre

[:4-17] 13,0 et ^13,1 Modèle:Article

[18] Modèle:Chapitre

[19] Modèle:Article

[21] Modèle:Chapitre

[Note 1]

[1]

[Note 2]

[2]

[3]

[Note 3]

[4]

[5]

[6]

[Note 4]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[Note 5]

[16]

Modèle du groupe générique

Sommaire

Exemples importants

Voir aussi

Notes et références

Notes

Références

Menu de navigation

Modèle du groupe générique

Exemples importants

Voir aussi

Notes et références

Notes

Références

Menu de navigation

Rechercher