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],[Note 2],[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 ${\displaystyle \Omega ({\sqrt {p}})}$, où ${\displaystyle p}$ est l'ordre (premier) du groupe^{[Note 3],[1],[4],[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],[Note 4],[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],[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 ${\displaystyle \mathbb {Z} /(n)}$est substantiellement différent d'un anneau générique^{[9],[Note 5],[16]}.

Voir aussi

• Modèle du chiffre idéal
• Modèle de l'oracle aléatoire