Fisher hypothesis

2013-09-18T10:51:07Z

145.107.99.106:

In [[computational complexity]], if <math>\scriptstyle\{ D_n \}_{n \in \mathbb{N}}</math> and <math>\scriptstyle\{ E_n \}_{n \in \mathbb{N}}</math> are two [[distribution ensemble]]s indexed by a [[security parameter]] ''n'' (which usually refers to the length of the input), then we say they are '''computationally indistinguishable''' if for any [[Uniformity (complexity)|non-uniform]] probabilistic [[polynomial time]] [[algorithm]] ''A'', the following quantity is a [[negligible function (cryptography)|negligible function]] in ''n'':

: <math>\delta(n) = \left| \Pr_{x \gets D_n}[ A(x) = 1] - \Pr_{x \gets E_n}[ A(x) = 1] \right|.</math>

denoted <math>D_n \approx E_n\!\,</math>.<ref>[http://www.cs.princeton.edu/courses/archive/spr10/cos433/lec4.pdf Lecture 4 - Computational Indistinguishability, Pseudorandom Generators]</ref> In other words, every efficient algorithm ''A'''s behavior does not significantly change when given samples according to ''D''<sub>''n''</sub> or ''E''<sub>''n''</sub> in the limit as <math>n\to \infty</math>. Another interpretation of computational indistinguishability, is that polynomial-time algorithms actively trying to distinguish between the two ensembles cannot do so: That any such algorithm will only perform negligibly better than if one were to just guess.

Implicit in the definition is the condition that the algorithm, <math>A</math>, must decide based on a single sample from one of the distributions. One might conceive of a situation in which the algorithm trying to distinguish between two distributions, could access as many samples as it needed. Hence two ensembles that cannot be distinguished by polynomial-time algorithms looking at multiple samples are deemed '''indistinguishable by polynomial-time sampling'''<ref name=Goldreich>[[Oded Goldreich|Goldreich, O.]] (2003). Foundations of cryptography. Cambridge, UK: Cambridge University Press.</ref>{{rp|107}}. It turns out that if the polynomial-time algorithm can generate samples in polynomial time, or has access to [[random oracle]] that generates samples for it, then indistinguishable by polynomial-time sampling is equivalent to computational indistinguishability<ref name=Goldreich></ref>{{rp|108}}.

== References ==
<references/>
* Donald Beaver and [[Silvio Micali]] and [[Phillip Rogaway]], The Round Complexity of Secure Protocols (Extended Abstract), 1990, pp. 503—513
* [[Shafi Goldwasser]] and [[Silvio Micali]]. Probabilistic Encryption. JCSS, 28(2):270–299, 1984
* [[Oded Goldreich]]. Foundations of Cryptography: Volume 2 – Basic Applications. Cambridge University Press, 2004.
* [[Jonathan Katz]], [[Yehuda Lindell]], "Introduction to Modern Cryptography: Principles and Protocols," Chapman & Hall/CRC, 2007

==External links==
* [[Yehuda Lindell]]. [http://u.cs.biu.ac.il/~lindell/89-656/main-89-656.html Introduction to Cryptography]

{{PlanetMath attribution|id=3457|title=computationally indistinguishable}}

[[Category:Algorithmic information theory]]

{{comp-sci-theory-stub}}
{{crypto-stub}}

formulasearchengine - User contributions [en]

Fisher hypothesis