# How to prove these two distributions are statistically/computationally indistinguishable

First we generate a key, $$k \leftarrow \{\, 0,1 \,\}^{n}$$ And we construct two PPT algorithms $A$ and $B$ as follow:

$$A_{k}\left( \cdot \right) \colon y_{A} \leftarrow k, \text{ return } y_{A}$$ and $$B_{k}\left( \cdot \right): y_{B} \leftarrow \{\, 0,1 \,\}^{n}, \text{ return } y_{B}$$

For fixed $k$, let $D_{A}$ be the distribution of $A$, and $D_{B}$ be the distribution of $B$. I want to know whether $D_{A}$ and $D_{B}$ are statistically indistinguishable or computationally indistinguishable.

In my opinion, $D_{A}$ is a one-point distribution and $D_{B}$ is a uniform distribution. Thus they are not statistically indistinguishable.

Let $$A^{\prime}\left( \cdot \right) \colon k \leftarrow \{\, 0,1 \,\}^{n}, y_{A^{\prime}} \leftarrow A_{k}\left( \cdot \right), \text{ return } y_{A^{\prime}}$$ and $$B^{\prime}\left( \cdot \right) \colon k \leftarrow \{\, 0,1 \,\}^{n}, y_{B^{\prime}}, \leftarrow B_{k}\left( \cdot \right), \text{ return } y_{B^{\prime}}$$ then $D_{A^{\prime}}$ and $D_{B^{\prime}}$ are statistically indistinguishable, thus they are also computationally indistinguishable.

Is my method correct? It looks strange and it seems that $k$ is not fixed when I show that they are computationally indistinguishable. Is there a better method from a clear view about the computationally indistinguishable and statistically indistinguishable?

Thanks for @D.W.♦'s answer, if $k$ is fixed, then $k$ is not a random variable anymore. Thus, there are 4 kinds of distributions.

Type (1)

For $k \leftarrow \{\, 0,1 \,\}^{n}$, $A_{k}$ and $B_{k}$ (given the knowledge of $k$) are computationally indistinguishable if for all PPT adversary $\mathcal{A}$ such that $$\left\vert \Pr \left[ k \leftarrow \{\, 0,1 \,\}^{n}; \mathcal{A} \left(k, A_{k} \left( \cdot \right) \right) = 1 \right] - \Pr \left[ k \leftarrow \{\, 0,1 \,\}^{n}; \mathcal{A} \left(k, B_{k} \left( \cdot \right) \right) = 1 \right] \right\vert < \varepsilon(n)$$

Type (2)

For $k \leftarrow \{\, 0,1 \,\}^{n}$, $A_{k}$ and $B_{k}$ are computationally indistinguishable if for all PPT adversary $\mathcal{A}$ such that $$\left\vert \Pr \left[ k \leftarrow \{\, 0,1 \,\}^{n}; \mathcal{A} \left( A_{k} \left( \cdot \right) \right) = 1 \right] - \Pr \left[ k \leftarrow \{\, 0,1 \,\}^{n}; \mathcal{A} \left( B_{k} \left( \cdot \right) \right) = 1 \right] \right\vert < \varepsilon (n)$$

Type (3)

For $k \in \{\, 0,1 \,\}^{n}$, $A_{k}$ and $B_{k}$ (given the knowledge of $k$) are computationally indistinguishable if for all PPT adversary $\mathcal{A}$ such that $$\left\vert \Pr \left[ \mathcal{A} \left(k, A_{k} \left( \cdot \right) \right) = 1 \right] - \Pr \left[ \mathcal{A} \left(k, B_{k} \left( \cdot \right) \right) = 1 \right] \right\vert < \varepsilon(n)$$

Type (4)

For $k \in \{\, 0,1 \,\}^{n}$, $A_{k}$ and $B_{k}$ are computationally indistinguishable if for all PPT adversary $\mathcal{A}$ such that $$\left\vert \Pr \left[ \mathcal{A} \left( A_{k} \left( \cdot \right) \right) = 1 \right] - \Pr \left[ \mathcal{A} \left( B_{k} \left( \cdot \right) \right) = 1 \right] \right\vert < \varepsilon (n)$$

To make it clear, I just want to know (4) holds true or not. And my original method confuses the definition between (2) and (4).

I think it may be helpful after we analyse the relation among these 4 types.

Obviously, "(1) holds true" $\Leftrightarrow$ "(3) holds true", since for all the PPT $\mathcal{A}$, $$\Pr \left[ \mathcal{A} \left(k, A_{k} \left( \cdot \right) \right) = 1 \right] = \Pr \left[ k \leftarrow \{\, 0,1 \,\}^{n}; \mathcal{A} \left(k, A_{k} \left( \cdot \right) \right) = 1 \right]$$

And "(1) holds true" $\Rightarrow$ "(2) holds true" is also easy to prove.

However I still cannot find a clear proof about the relation between (3) and (4).

I think your problem is in trying to insist that $k$ is fixed. That's getting you tied up in knots.

The statement "for fixed $k$, define $D_A$ to be the distribution..." makes no sense to me, because as you have previously defined $k$, $k$ isn't fixed -- $k$ is defined to be a random variable (that is uniformly distributed on $\{0,1\}^n$). So, it looks to me like you are contradicting yourself.

Instead, let me suggest a better way to think about indistinguishability. Think about indistinguishability as a random experiment. There is a formal definition of indistinguishability. In that definition, we define an experiment. The experiment works by running some algorithms that we have fully specified, and then observing the result. As part of this you will need to fully specify the probability space and the event you care about. For instance, if $F,G$ are two algorithms that depend only on a key $k$, then we might define them to be computationally indistinguishable if there does not exist a polynomial-time algorithm $A$ such that

$$|\Pr[k \leftarrow \{0,1\}^n ; A(F(k)) = 1] - \Pr[k \leftarrow \{0,1\}^n ; A(G(k)) = 1]|$$

is non-negligible. That's a standard definition of computational indistinguishability. Notice that the event $k \leftarrow \{0,1\}^n ; A(F(k)) = 1$ (and corresponding probability space) is fully defined, by defining some algorithms and then asking about the probability that it outputs 1. Everything can be expressed as a statement about some random variable, where the random variable is defined by executing a well-specified algorithm (i.e., in pseudocode). There is no step halfway along that says "fix $k$" (it's not even clear to me what that would mean).

The idea here is that we want to make a statement about the probability of some event. That event is defined in terms of running a randomized algorithm and checking its output. This is a well-defined and precise way to define an event in some probability space. Once you start trying to add "fix $k$" in the middle of that, we lose that property and it's not clear what you mean.

So, stick with the standard definitions, and try to apply them as is. Don't try to create your own definition. Or, if you insist on it, first translate your idea to a statement about a probability of some event where the event is defined in terms of a well-specified randomized algorithm. You should be able to write pseudocode for each step of your algorithm, without needing English (like "fix $k$"). If you try to do that for your idea, probably you'll find that at one step along the way your pseudocode assigns to $k$ (say, by picking a random value from $\{0,1\}^n$), and then $k$ is whatever it is (if it is picked randomly, then it's not fixed; it's a random variable).

For example, here is one fact that is true. If we define $X$ by $k \leftarrow \{0,1\}^n; X \leftarrow k$ and $Y$ by $k \leftarrow \{0,1\}^n; Y \leftarrow \{0,1\}^n$, then $X,Y$ are computationally indistinguishable and statistically indistinguishable (just apply the definition and see what you get). Same if you define algorithms $A,B$ as in your question and define $X$ by $k \leftarrow \{0,1\}^n; X \leftarrow A_k()$ and $Y$ by $k \leftarrow \{0,1\}^n; X \leftarrow B_k()$.

However, if you give the adversary knowledge of $k$, they are no longer distinguishable. Thus, for instance,

$$|\Pr[k \leftarrow \{0,1\}^n ; \mathcal{A}(A_k()) = 1] - \Pr[k \leftarrow \{0,1\}^n ; \mathcal{A}(B_k()) = 1]|$$

is negligible for all adversaries $\mathcal{A}$, but

$$|\Pr[k \leftarrow \{0,1\}^n ; \mathcal{A}(k,A_k()) = 1] - \Pr[k \leftarrow \{0,1\}^n ; \mathcal{A}(k,B_k()) = 1]|$$

is not.

As an aside, often we use $A$ to represent the adversary/attacker, so using $A$ to represent some other algorithm can potentialy get a little confusing.

• As for $k$, there are two characters you mention. "$k$ is or not is a random variable" and "the adversary knows or do not know $k$". So there are 4 kinds of distributions, right? The form of the equations are $\Pr [k \leftarrow \{0,1\}^n;\mathcal{A}(k,A_{k}()) = 1]$, $\Pr [k \leftarrow \{0,1\}^n;\mathcal{A}(A_{k}()) = 1]$, $\Pr [ \mathcal{A}(k, A_{k}()) = 1]$ and $\Pr [ \mathcal{A}(A_{k}()) = 1]$. (1) and (3) are not computationally distinguishable; (2) is computationally distinguishable . How about (4)? – TeamBright Mar 6 '18 at 18:36
• @TeamBright, That sounds about right. I think we're on the same page. For (3),(4), the probability depends on the choice of $k$. If you fix $k$, then there does exist polytime $\mathcal{A}$ such that $|\Pr[\mathcal{A}(A_k())=1] - \Pr[\mathcal{A}(B_k())=1]|$ is non-negligible: by choosing $\mathcal{A}$ appropriately, this difference can be as large as $1-2^{-n}$. This is true for all $k$. – D.W. Mar 6 '18 at 22:47
• For (1) and (3), since the adversary knows $k$, that $k$ is or is not a random variable is not important anymore. Actually, my original question is (4). $k$ is fixed, but $\mathcal{A}$ does not know it. I cannot image an adversary who can distinguish them. I thought (2) and (4) are equivalence. But it seems wrong. I have no idea now. Why do you think (4) is not computationally distinguishable. The adversary does not know $k$ even if $k$ is fixed. – TeamBright Mar 7 '18 at 0:51
• @TeamBright, if $k$ is fixed, then effectively $\mathcal{A}$ can know it. In particular, we'll have a situation where $k$ is fixed and then we ask whether there exists $\mathcal{A}$; so surely there exists an $\mathcal{A}$ that has that particular value of $k$ hardcoded in. This sounds a bit philosophical, which is why you need to write out the specific definition in the precise way I talk about in the question, and then maybe you'll see what I mean. – D.W. Mar 7 '18 at 2:24
• So, you mean (3) and (4) are the totally same? – TeamBright Mar 7 '18 at 11:53