DDH : Decisional Diffie-Hellman
Cryptographie
DDH : Decisional Diffie-Hellman. « Diffie-Hellman décisionnel », par analogie avec un test à l'aveugle où l'on doit dire si le plat servi est le vrai ou une imitation tirée au hasard. C'est une hypothèse : face à (g^a, g^b, Z), impossible de décider mieux qu'à pile ou face si Z vaut g^ab ou une valeur aléatoire.
Hypothèse, pas protocole : Comme CDH, DDH ne s'implémente pas : on la suppose vraie dans un groupe donné, et les preuves de sécurité de nombreux schémas s'appuient dessus.
Plus forte que CDH : Savoir calculer g^ab permet évidemment de reconnaître g^ab, donc DDH implique CDH. L'inverse est faux : DDH demande en plus qu'aucun bit du secret ne se distingue du hasard.
Groupes où elle tombe : Dans le groupe multiplicatif entier modulo un premier, DDH est fausse car le symbole de Legendre trahit une information ; on travaille donc dans un sous-groupe d'ordre premier. Sur les courbes munies d'un couplage calculable, DDH devient facile alors que CDH peut rester difficile.
Pourquoi elle compte : Le chiffrement ElGamal n'est sémantiquement sûr que sous DDH. Choisir le groupe « parce qu'il était dans l'exemple de la doc » revient à parier sur une hypothèse sans avoir lu à quelles conditions elle tient.
Ce qui arrive si on s'en passe
Choisir un groupe sans vérifier que l'hypothèse DDH y tient prive de leur fondement toutes les preuves de sécurité qui s'appuient dessus. Dans le groupe multiplicatif entier modulo un premier, pris tout entier, le symbole de Legendre trahit une information sur le secret, et le chiffrement ElGamal perd sa sécurité sémantique : un observateur peut apprendre quelque chose du message chiffré, par exemple distinguer lequel de deux messages connus a été envoyé. Sur une courbe munie d'un couplage calculable, l'hypothèse tombe également. Le protocole continue de fonctionner parfaitement, et c'est bien le problème : une hypothèse fausse ne lève jamais d'exception.
Explication de la marmotte
Deux personnes fabriquent un secret commun en s'envoyant des messages publics. On sait déjà qu'un curieux ne peut pas recalculer ce secret. Ici, on va plus loin : on montre au curieux une valeur et on lui demande « est-ce le vrai secret, ou un nombre tiré au sort ? ». Si la réponse ne peut pas se deviner mieux qu'en lançant une pièce, alors le secret ne laisse échapper absolument rien, pas même un indice partiel. C'est une exigence plus sévère que la première, et elle n'est vraie que si l'on choisit bien l'ensemble de nombres dans lequel on calcule.
Où ce terme est utilisé
- Établir une clé : Diffie-Hellman, KEM et HPKE (2 occurrences)