# Is there distinguisher?

Are these distributions computationally indistinguishable ?

$$f:\{0,1\}^n \to \{0,1\}^n$$

$$\{X_n\}_{n\in N}$$ : uniform distribution for function which $$f(0^n)=0^n$$ and for other function probability is zero.

$$\{Y_n\}_{n\in N}$$ : uniform distribution for function which $$f(0^n) \neq 0^n$$ and for other function probability is zero.

• What is meant by "under function which [...]"? – dkaeae Dec 22 '18 at 10:14
• @dkaeae I mean, for all functions$f (0^n) = 0^n$, the distribution of $\{X_n\}$ is uniform and for other functions distribution $\{X_n\}$ is non-uniform , and the probability of choosing these (other) functions is zero. – Lukas Garlo Dec 22 '18 at 15:22
• @lkowalcz , thank you. If $\{Y_n\}_{n \in N}$ be a uniform distribution , then $\{X_n\}$ and $\{Y_n\}$ are indistinguishable? I think it's true. Is it true? – Lukas Garlo Dec 23 '18 at 8:34

Consider the following families of distributions over functions from $$\{0,1\}^{n} \to \{0,1\}^{n}$$:
$$\{X_n\}, \text{ where } X_n \text{ is the uniform distribution over the set of functions } f : \{0,1\}^{n} \to \{0,1\}^{n} \text{ such that } f(0^{n}) = 0^{n}$$
$$\{Y_n\}, \text{ where } X_n \text{ is the uniform distribution over the set of functions } f : \{0,1\}^{n} \to \{0,1\}^{n} \text{ such that } f(0^{n}) \neq 0^{n}$$
I claim they are computationally distinguishable, assuming that each function can be evaluated on input $$0^{n}$$ efficiently. Consider the following distinguisher, which on input $$f$$ computes $$f(0^{n})$$ and outputs $$X$$ if $$f(0^{n}) = 0^{n}$$ and $$Y$$ otherwise. By the definition of $$\{X_n\}$$, if $$f$$ is drawn from this family, this distinguisher will output $$X$$. By the definition of $$\{Y_n\}$$, if $$f$$ is drawn from this family, this distinguisher will output $$Y$$.