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 $\Omega ({\sqrt {p}})$ , où $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[modifier | modifier le code]

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 $\mathbb {Z} /(n)$ est substantiellement différent d'un anneau générique^[9]^,^{[Note 5]}^,^[16].

Voir aussi[modifier | modifier le code]

Notes et références[modifier | modifier le code]

Notes[modifier | modifier le code]

↑ 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 $\mathbb {Z} /(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[modifier | modifier le code]

↑ ^{a et b} (en) Victor Shoup, « Lower Bounds for Discrete Logarithms and Related Problems », dans Advances in Cryptology — EUROCRYPT ’97, Springer Berlin Heidelberg, 1997 (ISBN 9783540629757, DOI 10.1007/3-540-69053-0_18, lire en ligne), p. 256–266
↑ (en) Ueli Maurer, « Abstract Models of Computation in Cryptography », dans Cryptography and Coding, Springer Berlin Heidelberg, 2005 (ISBN 9783540302766, DOI 10.1007/11586821_1, lire en ligne), p. 1–12
↑ (en) V. I. Nechaev, « Complexity of a determinate algorithm for the discrete logarithm », Mathematical Notes, vol. 55, n^o 2,‎ février 1994, p. 165–172 (ISSN 0001-4346 et 1573-8876, DOI 10.1007/bf02113297, lire en ligne, consulté le 18 août 2018)
↑ (en) Ueli Maurer et Stefan Wolf, « Lower bounds on generic algorithms in groups », dans Lecture Notes in Computer Science, Springer Berlin Heidelberg, 1998 (ISBN 9783540645184, DOI 10.1007/bfb0054118, lire en ligne), p. 72–84
↑ (en) Alexander May et Ilya Ozerov, « A Generic Algorithm for Small Weight Discrete Logarithms in Composite Groups », dans Selected Areas in Cryptography -- SAC 2014, Springer International Publishing, 2014 (ISBN 9783319130507, DOI 10.1007/978-3-319-13051-4_17, lire en ligne), p. 278–289
↑ (en) Alexander W. Dent, « Adapting the Weaknesses of the Random Oracle Model to the Generic Group Model », dans Lecture Notes in Computer Science, Springer Berlin Heidelberg, 2002 (ISBN 9783540001713, DOI 10.1007/3-540-36178-2_6, lire en ligne), p. 100–109
↑ ^{a et b} (en) Alfred Menezes et Neal Koblitz, « Another look at generic groups », Advances in Mathematics of Communications, vol. 1, n^o 1,‎ janvier 2007, p. 13–28 (ISSN 1930-5346, DOI 10.3934/amc.2007.1.13, lire en ligne, consulté le 18 août 2018)
↑ (en) Sandro Coretti, Yevgeniy Dodis et Siyao Guo, « Non-Uniform Bounds in the Random-Permutation, Ideal-Cipher, and Generic-Group Models », dans Lecture Notes in Computer Science, Springer International Publishing, 2018 (ISBN 9783319968834, DOI 10.1007/978-3-319-96884-1_23, lire en ligne), p. 693–721
↑ ^{a et b} (en) Tibor Jager et Jörg Schwenk, « On the Analysis of Cryptographic Assumptions in the Generic Ring Model », Journal of Cryptology, vol. 26, n^o 2,‎ 8 mars 2012, p. 225–245 (ISSN 0933-2790 et 1432-1378, DOI 10.1007/s00145-012-9120-y, lire en ligne, consulté le 18 août 2018)
↑ ^{a et b} (en) Divesh Aggarwal et Ueli Maurer, « Breaking RSA Generically Is Equivalent to Factoring », dans Advances in Cryptology - EUROCRYPT 2009, Springer Berlin Heidelberg, 2009 (ISBN 9783642010002, DOI 10.1007/978-3-642-01001-9_2, lire en ligne), p. 36–53
↑ (en) Dan Boneh et Richard J. Lipton, « Algorithms for Black-Box Fields and their Application to Cryptography », dans Advances in Cryptology — CRYPTO ’96, Springer Berlin Heidelberg, 1996 (ISBN 9783540615125, DOI 10.1007/3-540-68697-5_22, lire en ligne), p. 283–297
↑ (en) Tibor Jager et Andy Rupp, « The Semi-Generic Group Model and Applications to Pairing-Based Cryptography », dans Advances in Cryptology - ASIACRYPT 2010, Springer Berlin Heidelberg, 2010 (ISBN 9783642173721, DOI 10.1007/978-3-642-17373-8_31, lire en ligne), p. 539–556
↑ ^{a et b} (en) Daniel R. L. Brown, « Generic Groups, Collision Resistance, and ECDSA », Designs, Codes and Cryptography, vol. 35, n^o 1,‎ avril 2005, p. 119–152 (ISSN 0925-1022 et 1573-7586, DOI 10.1007/s10623-003-6154-z, lire en ligne, consulté le 18 août 2018)
↑ (en) Claus Peter Schnorr et Markus Jakobsson, « Security of Signed ElGamal Encryption », dans Advances in Cryptology — ASIACRYPT 2000, Springer Berlin Heidelberg, 2000 (ISBN 9783540414049, DOI 10.1007/3-540-44448-3_7, lire en ligne), p. 73–89
↑ (en) Dan Boneh et Xavier Boyen, « Short Signatures Without Random Oracles and the SDH Assumption in Bilinear Groups », Journal of Cryptology, vol. 21, n^o 2,‎ 11 septembre 2007, p. 149–177 (ISSN 0933-2790 et 1432-1378, DOI 10.1007/s00145-007-9005-7, lire en ligne, consulté le 18 août 2018)
↑ (en) Dan Boneh et Ramarathnam Venkatesan, « Breaking RSA may not be equivalent to factoring », dans Lecture Notes in Computer Science, Springer Berlin Heidelberg, 1998 (ISBN 9783540645184, DOI 10.1007/bfb0054117, lire en ligne), p. 59–71

Portail de la cryptologie

[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 $\mathbb {Z} /(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] {a et b} (en) Victor Shoup, « Lower Bounds for Discrete Logarithms and Related Problems », dans Advances in Cryptology — EUROCRYPT ’97, Springer Berlin Heidelberg, 1997 (ISBN 9783540629757, DOI 10.1007/3-540-69053-0_18, lire en ligne), p. 256–266

[4] (en) Ueli Maurer, « Abstract Models of Computation in Cryptography », dans Cryptography and Coding, Springer Berlin Heidelberg, 2005 (ISBN 9783540302766, DOI 10.1007/11586821_1, lire en ligne), p. 1–12

[5] (en) V. I. Nechaev, « Complexity of a determinate algorithm for the discrete logarithm », Mathematical Notes, vol. 55, n^o 2,‎ février 1994, p. 165–172 (ISSN 0001-4346 et 1573-8876, DOI 10.1007/bf02113297, lire en ligne, consulté le 18 août 2018)

[7] (en) Ueli Maurer et Stefan Wolf, « Lower bounds on generic algorithms in groups », dans Lecture Notes in Computer Science, Springer Berlin Heidelberg, 1998 (ISBN 9783540645184, DOI 10.1007/bfb0054118, lire en ligne), p. 72–84

[8] (en) Alexander May et Ilya Ozerov, « A Generic Algorithm for Small Weight Discrete Logarithms in Composite Groups », dans Selected Areas in Cryptography -- SAC 2014, Springer International Publishing, 2014 (ISBN 9783319130507, DOI 10.1007/978-3-319-13051-4_17, lire en ligne), p. 278–289

[9] (en) Alexander W. Dent, « Adapting the Weaknesses of the Random Oracle Model to the Generic Group Model », dans Lecture Notes in Computer Science, Springer Berlin Heidelberg, 2002 (ISBN 9783540001713, DOI 10.1007/3-540-36178-2_6, lire en ligne), p. 100–109

[:1-11] {a et b} (en) Alfred Menezes et Neal Koblitz, « Another look at generic groups », Advances in Mathematics of Communications, vol. 1, n^o 1,‎ janvier 2007, p. 13–28 (ISSN 1930-5346, DOI 10.3934/amc.2007.1.13, lire en ligne, consulté le 18 août 2018)

[12] (en) Sandro Coretti, Yevgeniy Dodis et Siyao Guo, « Non-Uniform Bounds in the Random-Permutation, Ideal-Cipher, and Generic-Group Models », dans Lecture Notes in Computer Science, Springer International Publishing, 2018 (ISBN 9783319968834, DOI 10.1007/978-3-319-96884-1_23, lire en ligne), p. 693–721

[:2-13] {a et b} (en) Tibor Jager et Jörg Schwenk, « On the Analysis of Cryptographic Assumptions in the Generic Ring Model », Journal of Cryptology, vol. 26, n^o 2,‎ 8 mars 2012, p. 225–245 (ISSN 0933-2790 et 1432-1378, DOI 10.1007/s00145-012-9120-y, lire en ligne, consulté le 18 août 2018)

[:3-14] {a et b} (en) Divesh Aggarwal et Ueli Maurer, « Breaking RSA Generically Is Equivalent to Factoring », dans Advances in Cryptology - EUROCRYPT 2009, Springer Berlin Heidelberg, 2009 (ISBN 9783642010002, DOI 10.1007/978-3-642-01001-9_2, lire en ligne), p. 36–53

[15] (en) Dan Boneh et Richard J. Lipton, « Algorithms for Black-Box Fields and their Application to Cryptography », dans Advances in Cryptology — CRYPTO ’96, Springer Berlin Heidelberg, 1996 (ISBN 9783540615125, DOI 10.1007/3-540-68697-5_22, lire en ligne), p. 283–297

[16] (en) Tibor Jager et Andy Rupp, « The Semi-Generic Group Model and Applications to Pairing-Based Cryptography », dans Advances in Cryptology - ASIACRYPT 2010, Springer Berlin Heidelberg, 2010 (ISBN 9783642173721, DOI 10.1007/978-3-642-17373-8_31, lire en ligne), p. 539–556

[:4-17] {a et b} (en) Daniel R. L. Brown, « Generic Groups, Collision Resistance, and ECDSA », Designs, Codes and Cryptography, vol. 35, n^o 1,‎ avril 2005, p. 119–152 (ISSN 0925-1022 et 1573-7586, DOI 10.1007/s10623-003-6154-z, lire en ligne, consulté le 18 août 2018)

[18] (en) Claus Peter Schnorr et Markus Jakobsson, « Security of Signed ElGamal Encryption », dans Advances in Cryptology — ASIACRYPT 2000, Springer Berlin Heidelberg, 2000 (ISBN 9783540414049, DOI 10.1007/3-540-44448-3_7, lire en ligne), p. 73–89

[19] (en) Dan Boneh et Xavier Boyen, « Short Signatures Without Random Oracles and the SDH Assumption in Bilinear Groups », Journal of Cryptology, vol. 21, n^o 2,‎ 11 septembre 2007, p. 149–177 (ISSN 0933-2790 et 1432-1378, DOI 10.1007/s00145-007-9005-7, lire en ligne, consulté le 18 août 2018)

[21] (en) Dan Boneh et Ramarathnam Venkatesan, « Breaking RSA may not be equivalent to factoring », dans Lecture Notes in Computer Science, Springer Berlin Heidelberg, 1998 (ISBN 9783540645184, DOI 10.1007/bfb0054117, lire en ligne), p. 59–71

[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]

v · m Sécurité prouvable en cryptologie
Modèles de sécurité	Modèle standard Modèle de l'oracle aléatoire (ROM) Modèle du groupe générique (GGM) Modèle du groupe algébrique (AGM) Modèle du chiffre idéal (ICM) Modèle de l'action de groupe à sens unique (OWGA) Transfert inconscient (OT) Fonction à perte extrême (ELF) Fonction pseudo-aléatoire (PRF) Permutation pseudo-aléatoire (PRP) Générateur pseudo-aléatoire (PRG) Groupe bilinéaire Application multilinéaire Modèle de la chaîne de référence commune (CRS) Fonction à sens unique (OWF) Fonction à trappe (TDF) Obfuscation indistinguable (iO) Composabilité universelle (UC)
Outils et techniques de preuve	Réduction Séparation Avantage Argument hybride Distance statistique Coefficient H Simulation Forking lemma Leftover hash lemma Lemme de Schwartz-Zippel Théorème de Luby-Rackoff Théorème des anniversaires Heuristique de Fiat-Shamir
Hypothèses calculatoires	Factorisation Problème RSA Problème RSA fort Problème du logarithme discret Problème de Diffie-Hellman (CDH et DDH) Problème de la résiduosité quadratique Problème de la résiduosité supérieure Navigation dans un graphe expanseur Problème LWE Problème NTRU Problèmes de réseau (SVP, CVP, SIS, SIVP)
Propriétés de sécurité	IND (indistingabilité) EF (forge existentielle) NM (non malléabilité) Résistance aux collisions (CR) CPR (résistance aux collisions à préfixe choisi) PIR (résistance aux préimages) SPIR (résistance aux secondes préimages) Divulgation nulle de connaissance (ZK)
Modèles d'attaques	Attaque sans message (NMA) Clairs/messages choisis (CPA/CMA) Chiffrés choisis (CCA) Chiffrés choisis de façon adaptative (CCA2) Attaque par sondes (ISW)