AccueilđŸ‡«đŸ‡·Chercher

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

Bibliographie

Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplĂ©mentaires peuvent s’appliquer aux fichiers multimĂ©dias.