Un argument hybride est une méthode de preuve en cryptographie permettant de montrer l'indistinguabilité calculatoire de deux distributions de probabilité.

Motivation modifier

Pour montrer que deux distributions   et   sont calculatoirement indistinguables, la stratégie habituelle est 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 succession de distributions   telle que   et  . Ainsi, en montrant que, pour tout  ,   est calculatoirement indistinguable de   (une preuve qui a pu être faite par le biais d'une réduction par exemple), on obtient que   et   sont calculatoirement indistinguables: c'est une conséquence de l'inégalité triangulaire.

En effet, pour tout adversaire efficace (qui fonctionne en temps polynomial probabiliste)  , l'avantage de   pour distinguer deux distributions   et   peut être défini par :

 

Ainsi, dans notre cas, l'application de l'inégalité triangulaire nous donne :

 

Comme   et   sont calculatoirement indistinguables pour tout  ,   est négligeable pour tout   et donc   est négligeable. Cependant, cet argument n'est valable que lorsque   est fixé et borné : si un nombre polynomial de distributions intermédiaires est nécessaire, l'inégalité triangulaire ne permet plus de conclure. En effet, une somme polynomiale de fonctions négligeables n'est pas nécessairement négligeable. Par exemple, si on prend   pour tout  , alors chaque   est négligeable en   et pourtant   n'est pas négligeable. Pour cette raison, on utilise à la place un argument hybride.

Énoncé modifier

Soient deux distributions   et   qui sont calculatoirement indistinguables, et soient deux distributions   et  . Pour fixer les idées,   peut être une distribution sur des suites arbitrairement longues de la forme   tandis que   serait une distribution sur des suites de la forme  . Pour montrer que les deux distributions sont calculatoirement indistinguables, l'idée est d'introduire une suite de distributions hybrides   telle que   (dans notre exemple,   serait une distribution sur des suites obtenue en faisant   copies de   puis des copies de  ), qui permet de transformer petit à petit la distribution   en la distribution  . Ainsi, pour tout adversaire polynomial  , on demande à ce qu'il existe un entier   au plus polynomial tel que  . Dans notre exemple, cela vient du fait que   ne peut lire que les   premiers éléments de la suite. Dans ce contexte, l'argument hybride permet de conclure. Il s'énonce comme suit [1]:

Argument hybride — Soient deux distributions calculatoirement indistinguables   et   et soit   une suite de distributions. Supposons qu'il existe un algorithme probabilistique polynomial   tel que, pour tout  , les distributions   et   (respectivement,   et  ) sont identiquement distribuées. Alors, pour tout adversaire efficace  , pour tout polynôme  , il existe un adversaire probabilistique polynomial   tel que  

Utilisations modifier

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 :

  • Si un générateur de bits est imprédictible, alors il s'agit d'un générateur pseudo-aléatoire [3].
  • 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 modifier

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.

Notes et références modifier

Notes modifier

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Hybrid argument » (voir la liste des auteurs).
  1. Les i premiers bits de la chaîne G(x).

Références modifier

Annexes modifier

Bibliographie modifier

Articles connexes modifier

Liens externes modifier

  • [Dodis 2008] (en) Yevgeniy Dodis, « Introduction to Cryptography » [« Cours d'introduction à la cryptographie »] [PDF], .