computationally indistinguishable


If {Dn}n and {En}n are distribution ensembles (on Ω) then we say they are computationally indistinguishable if for any probabilistic, polynomial timeMathworldPlanetmath algorithmMathworldPlanetmath A and any polynomal function f there is some m such that for all n>m:

|ProbA(Dn)=ProbA(En)|<1p(n)

where ProbA(Dn) is the probability that A accepts x where x is chosen according to the distributionPlanetmathPlanetmath Dn.

Title computationally indistinguishable
Canonical name ComputationallyIndistinguishable
Date of creation 2013-03-22 13:03:11
Last modified on 2013-03-22 13:03:11
Owner Henry (455)
Last modified by Henry (455)
Numerical id 5
Author Henry (455)
Entry type Definition
Classification msc 68Q30