Indistinguabilité calculatoire

Deux familles de distributions ${\displaystyle (D_{n})_{n\in \mathbb {N} }}$ et ${\displaystyle (E_{n})_{n\in \mathbb {N} }}$ sont calculatoirement indistinguables si pour tout algorithme probabiliste en temps polynomial ${\displaystyle {\mathcal {A}}}$ possède un avantage négligeable en fonction de ${\displaystyle n}$[3] pour distinguer les distributions ${\displaystyle D_{n}}$ et ${\displaystyle E_{n}}$. Autrement dit, pour tout exposant ${\displaystyle k\in \mathbb {N} }$, il existe une borne ${\displaystyle N\in \mathbb {N} }$ telle que pour tout indice ${\displaystyle n\geq N}$ on ait

${\displaystyle {\mathsf {Adv}}_{\mathcal {A}}(n)=\left|\Pr _{x\gets D_{n}}[{\mathcal {A}}(x)=1]-\Pr _{x\gets E_{n}}[{\mathcal {A}}(x)=1]\right|\leq {\frac {1}{n^{k}}}.}$