# Computation indistinguishability questions

The definition I have is:

Two probability ensembles $X = \{X_n\}_{n \in \mathbf{N}}$ and $X = \{Y_n\}_{n \in \mathbf{N}}$ are computationally indistinguishable if for every probabilistic polynomial-time algorithm $D$, every positive polynomial $p(\cdot)$, and all sufficiently large $n$ we have $$|P(D(X_n, 1^n) = 1) - P(D(Y_n, 1^n) = 1) | < \frac{1}{p(n)}.$$

I'm having trouble digesting some ideas and the notation here.

Does $X = \{X_n\}_{n \in \mathbf{N}}$ mean $X = X_1, X_2, \ldots$ where each $X_i$ comes from the same distribution? So if our $X$ distribution is $0-1$ coin flips, then $X$ is an infinite sequences of $0$s and $1$s ?

A note says "typically, each $X_n$ ranges over strings of length $poly(n)$". What does this mean? The distribution will take $n$ as some sort of input? In my coin-flipping example each $X_i$ gives us back just one bit...

I also want to ask why the $1^n$ is necessary as input to the distinguisher $D$, but I should probably understand the answers to my above questions first.

No, $X = \{X_n\}_{n \in \mathbf{N}}$ means $X = X_1, X_2, \ldots$ where each $X_i$ is a distribution.
So one could let each $X_i$ be the uniform distribution on strings of length $i$.

That means there is a polynomial $q$ such that for all $n$ and $x$, if $X_n$
assigns non-zero probability to $x$ then the length of $x$ is at most $q(i\hspace{.02 in})$.
The distributions do "take $n$ as some sort of input".

See these two questions for $1^n$.

• Xn is the distribution technically and Xi is the individual element that summates to the Xn distribution Dec 29 '14 at 15:51
• While this is not a constructive comment, I think that the theory of cryptography suffers from cumbersome notation, with unfortunately no obvious way of fixing this problem, as evidenced by the answers to this question. Jan 26 '15 at 23:29
• It should be "cumbersome but necessary notation". When people use informal language and logical arguments, the problem of implicit knowledge and implicit assumptions can lead to inaccuracies or that proofs turn out to be wrong. If a proof is subject to interpretation, then it doesn't have much meaning. Therefore, notations can contain things, which are clear for everyone, but required to be formally correct.
– tylo
Feb 24 '15 at 14:19

$P(D(X_n, 1^n) = 1)$ means the probability that the following algorithm returns $1$:

1. Sample $x$ according to $X_n$.
2. Run $D(x, 1^n)$.
3. Output whatever $D$ outputs.

Say for example that $X_n$ is the uniform distribution on $\{1,2,3,4\}$, and $D(x,1^n)$ is the following:

1. If $x$ is odd, output $x$ or $x+1$, each with probability $1/2$.
2. If $x$ is even, output $x$.

Then $P(D(X_n, 1^n)=1)$ is $1/8$ (we need to pick $x=1$, which happens with probability $1/4$, and then output $x$ with probability $1/2$).

I don't think your example where each $X_i$ is defined on $\{0,1\}$ will be very enlightening. Generally, $X_n$ is the output of some algorithm on input $n$, for example the key generation algorithm of a cryptosystem where $n$ is the desired key length. Then the length of the strings $X_i$ is defined over really is $\mathsf{poly}(i)$.

In this case where $X_i$ and $Y_i$ are the outputs of algorithms, the idea of the definition is that $D$ is unable to reliably tell whether the string it gets has been "produced" by $X$ or by $Y$.

The $X_i$ could be distributed differently, but does not have to be. The idea of an ensemble is just that the distributions are related somehow. A way to think of this is that, $X_i$ could be the distribution of the output from some randomized algorithm given input $i$. Consider, for example, the algorithm that on input $i$ outputs a uniformly random bit-string of length $i$. We can now describe the outputs of this algorithm as the ensemble $X = \{X_i\}_{i \in \mathbb{N}}$, where $X_i$ follows the distribution of uniformly random strings.

Of course in general the algorithm could do all sorts of things. You could also think of $X_i$ as following the distribution of $i$-bit keys for some encryption scheme (generated by a particular key generation algorithm) or whatever you want.

Of course, algorithms do not have to give output of increasing length for increasing input $i$. And the same goes for the corresponding ensemble $X = \{X_i\}_{i \in \mathbb{N}}$, the $X_i$ do not have to follow a distribution of strings of increasing length.

So in your bit-flipping example you could think of $i$ as some input to your bit-flipping algorithm (or protocol), that makes it produce one bit of output. My guess is that your bit-flipping protocol takes some kind of security parameter. Typically the higher the security parameter the closer to uniformly random the output of the bit-flip will be. So you could describe the output of the protocol as the ensemble $X = \{X_i\}_{i \in \mathbb{N}}$, where $X_i$ is the output of the protocol when using security parameter $i$. Now, consider an other ensemble $U = \{U_i\}_{i \in \mathbb{N}}$, where all $U_i$ is a truly random bit. If $U$ and $X$ are computationally indistinguishable according to your definition, this then roughly means that if you use a high enough security parameter then no one will be able to distinguish the output from your bit-flipping algorithm apart from a truly random bit-flip.

Now the the second part of the question. This is kind of a technicality. $1^n$ is a way to write the number $n$ in unary notation. I.e., $1^n$ just means $n$ ones (so, e.g., $1^2 = 11$, $1^3 = 111$ and so on). Why would you do that? Because if you give an algorithm the input $n$ in binary then the input is only of size $log(n)$. Thus, if the algorithm runs in time $poly(n)$ then you have an exponential time algorithm*! However, in cryptography we often want to give an algorithm a security parameter $n$ and then have the algorithm run in time $poly(n)$, but we also want to call such an algorithm poly-time. So by using unary notation, we can cheat a little bit and get what we want. So your bit-flipping protocol would take the security parameter $i$ as $1^i$ and $X_i$ would be the distribution of output on input $1^i$.

*Because in computer science in general when we call something an exponential time algorithm, we mean exponential in the length of the input.

• > Because if you give an algorithm the input n in binary then the input is only of size log(n). Thus, if the algorithm runs in time poly(n) then you have an exponential time algorithm! But if $X_n$ is of length $n$ then this isn't a problem... I thought the "technically bad case" was when, say the length of $X_n$ is logarithmic in $n$. Then if we didn't provide $1^n$ the distinguisher has less time than it usually would be allowed? Nov 25 '14 at 22:52
• $X_n$ is not the input. It is the distribution of output. As I point out the length of the output does not have to be proportional the input in anyway. The problem is, as I state, that if you want an algorithm that runs in $poly(n)$ time to be a poly-time, and you only give the algorithm $n$ in binary as input, then the input is of size $log(n)$. Nov 25 '14 at 22:59
• @Dramal Sorry, I think I get what you were asking in your comment now. You are right, in case of the distinguisher we want to give it the security parameter to allow it to run on $poly(n)$ regardless of the size of the output. Otherwise, in your bit-flipping protocol, for example, the distinguisher would always only get a 1 bit input, and thus only be allowed to run in constant time. However, I hope you see that we could not just give the distinguisher $n$ in binary, because then it would also have to little time to run. Nov 25 '14 at 23:08
• If $X_n$ is just a distribution then how does D sample from it in order to decide whether it accepts or rejects? I'm confused now as to how to you can even give a distribution as input to an algorithm. Nov 25 '14 at 23:11
• I think this is a case of slightly abusive notation. Think of $P(D(X_n, 1^n)=1)$ as the probability of $D$ outputing $1$ when its input is sampled from $X_n$. Nov 25 '14 at 23:16

I see a few small nuanced errors in all the above explanations and they are easy to make for any of us.

Let me clarify this in as straight forward but detailed manner as I can:

$I$ is a countable set and the probability ensemble indexed by $I$ is a collection of random variables denoted as: ${X_i}\in I$. I can either take the form of the natural numbers or an efficiently computable subset (Katz & Lindell, 2008). $X_n$ is the distribution and $X_i$ is the collection of elements. When we see $I = N$ the ensemble is a sequence of random variables $X_1, X_2, X_3,\ldots$

Next all we are doing is taking the differences between the $X_n$ distribution and the running of said distribution.

Then we see pseudo-randomness is just a special case of computational indistinguishability. All this means the difference epsilon is very small or negligible or trivial if you will; not exactly the same.