# computationally indistinguishable

If $\{D_{n}\}_{n\in\mathbb{N}}$ and $\{E_{n}\}_{n\in\mathbb{N}}$ are distribution ensembles (on $\Omega$) then we say they are computationally indistinguishable if for any probabilistic, polynomial time algorithm $A$ and any polynomal function $f$ there is some $m$ such that for all $n>m$:

 $|\operatorname{Prob}_{A}(D_{n})=\operatorname{Prob}_{A}(E_{n})|<\frac{1}{p(n)}$

where $\operatorname{Prob}_{A}(D_{n})$ is the probability that $A$ accepts $x$ where $x$ is chosen according to the distribution $D_{n}$.

Title computationally indistinguishable ComputationallyIndistinguishable 2013-03-22 13:03:11 2013-03-22 13:03:11 Henry (455) Henry (455) 5 Henry (455) Definition msc 68Q30