0
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ What is meant by "under function which [...]"? $\endgroup$ – dkaeae Dec 22 '18 at 10:14
  • $\begingroup$ @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. $\endgroup$ – Lukas Garlo Dec 22 '18 at 15:22
  • $\begingroup$ @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? $\endgroup$ – Lukas Garlo Dec 23 '18 at 8:34
2
$\begingroup$

It looks like you're asking the following:

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} $

Are these families of distributions computationally indistinguishable?

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.