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)