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$
3
  • 1
    $\begingroup$ What is meant by "under function which [...]"? $\endgroup$
    – dkaeae
    Commented Dec 22, 2018 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$ Commented Dec 22, 2018 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$ Commented Dec 23, 2018 at 8:34

1 Answer 1

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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