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.