Indistinguabilité calculatoire
En informatique fondamentale, lâindistinguabilitĂ© calculatoire permet dâexprimer la similaritĂ© de deux distributions de probabilitĂ©s en prenant en compte des notions de complexitĂ© algorithmique. On dit que deux distributions de probabilitĂ©s sont calculatoirement indistinguables[1] sâil nâexiste pas dâalgorithme efficace qui puisse les discerner de maniĂšre significative.
Elle peut ĂȘtre vue comme une relaxation de la notion dâindistinguabilitĂ© statistique, dont les dĂ©finitions coĂŻncident lorsque la puissance de calcul des algorithmes cherchant Ă distinguer les deux distributions nâest plus limitĂ©e. On peut alors voir que la notion dâefficacitĂ© du distingueur peut ĂȘtre dĂ©finie de diffĂ©rentes maniĂšres, amenant un spectre de dĂ©finitions plus ou moins fortes[2].
En cryptologie et en complexitĂ© algorithmique, lâefficacitĂ© du distingueur est souvent dĂ©finie comme celle d'un algorithme (possiblement probabiliste) terminant en temps polynomial, dĂ©crite dans le modĂšle des machines de Turing.
Définition
Deux familles de distributions et sont calculatoirement indistinguables si pour tout algorithme probabiliste en temps polynomial possÚde un avantage négligeable en fonction de [3] pour distinguer les distributions et . Autrement dit, pour tout exposant , il existe une borne telle que pour tout indice on ait
Notes et références
- Fondements ThĂ©oriques de la cryptographie. Cours de l'Ăcole Normale SupĂ©rieure..
- Berman et Haitner. From Non-adaptive to Adaptive Pseudorandom Functions. Les auteurs y définissent une notion d'indistinguabilité face à un distingueur superpolynomial..
- Boaz Barak. Computational Indistinguishability, Pseudorandom Generators..
Bibliographie
- Hieu Phan et Philippe Guillot, Fondements thĂ©oriques de la cryptographie, Ăcole Normale SupĂ©rieure (Paris), , 117 p. (lire en ligne)
- (en) Boaz Barak, Computational Indistinguishability, Pseudorandom Generators, Princeton University, , 6 p. (lire en ligne)
- (en) Itay Berman et Iftach Haitner, « From Non-adaptive to Adaptive Pseudorandom Functions », Journal of Cryptology, no 28,â , p. 297â311 (lire en ligne)