Ceci est une version archivée de cette page, en date du 16 mars 2022 à 06:18 et modifiée en dernier par AméliorationsModestes(discuter | contributions). Elle peut contenir des erreurs, des inexactitudes ou des contenus vandalisés non présents dans la version actuelle.
Pour montrer que deux distributions et sont calculatoirement indistinguables, il est parfois possible d'exhiber une réduction d'un problème difficile à la sécurité du cryptosystème. Néanmoins, cette méthode n'est pas toujours facilement utilisable, et il existe des cas où il est plus facile d'exhiber une suite polynomialement bornée de distributions (dites hybrides) telles que et telles que pour tout , on ait qui soit calculatoirement indistinguable de (une preuve qui a pu être faite par le biais d'une réduction par exemple).
L'argument hybride est alors la conséquence de l'inégalité triangulaire, puisque pour n'importe quel adversaire efficace (qui fonctionne en temps polynomial probabiliste) , l'avantage de pour distinguer deux distributions et est défini par:
Ainsi dans notre cas, l'application de l'inégalité triangulaire nous donne que :
Ainsi il existe nécessairement un indice tel que :
Comme est polynomialement borné (par hypothèse), alors si on peut montrer que l'avantage de n'importe quel adversaire fonctionnant en temps polynomial pour distinguer deux distributions hybrides successives est négligeable, alors l'avantage de n'importe quel adversaire pour distinguer les deux distributions initiales et est lui-même négligeable [1].
Utilisations
Il existe des exemples de l'utilisation de l'argument hybride en cryptographie [2], généralement présenté sous forme de preuves par jeux. On peut citer parmi celles-ci les preuves simples suivantes :
On peut étendre un générateur pseudo-aléatoire pour construire un générateur pseudo-aléatoire dont la sortie est polynomialement plus grande que l'entrée [4].
Prédicteur à partir d'un distingueur pour un générateur pseudo-aléatoire
La sécurité d'un générateur pseudo-aléatoire est donnée par l'indistinguabilité de la distribution « » de la distribution uniforme sur les chaînes de longueur [5]. Une définition alternative est donnée par l'imprédictabilité du bit suivant, c'est-à-dire qu'il n'existe pas d'algorithme efficace permettant de prédire sachant [note 1] avec une probabilité significativement différente de 1/2.
Andrew Yao a montré en 1982 que ces deux définitions sont équivalentes [3], on donne dans la suite une preuve de l'implication qui fait intervenir l'argument hybride.
Démonstration
Ainsi si les bits de sont indistinguables de l'uniforme, alors il ne peut exister de prédicteur. Cela se fait par la construction de distributions hybrides, en posant les distributions hybrides , qui est telle que et .
L'argument hybride donne donc l'existence d'un indice tel que
Par conséquent, un distingueur entre la distribution et la distribution uniforme sur les chaînes de bits de longueur n est aussi un distingueur entre les distributions et .
On construit ensuite le prédicteur suivant qui utilise de manière boîte noire un distingueur entre les distributions et la distribution uniforme sur n bits:
Il ne reste plus qu'à calculer la probabilité pour notre prédicteur d'avoir donné le bon bit.
Ce qui donne une borne inférieure sur la distance de cette probabilité comme par , qui est non négligeable si le distingueur a un avantage significatif.
[Katz et Lindell 2014] (en) Jonathan Katz et Yehuda Lindell, Introduction to Modern Cryptography, 2nd Edition, Boca Raton, Chapman and Hall, , 583 p. (ISBN978-1-4665-7026-9, BNF44284474), « Constructions of Pseudorandom Generators ».
[Shoup 2004] (en) Victor Shoup, « Sequences of games: a tool for taming complexity in security proofs », ePrint Reports, (lire en ligne).