Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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.

share|improve this question

2 Answers 2

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

share|improve this answer

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.

share|improve this answer
> 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? –  Dramal Nov 25 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)$. –  Guut Boy Nov 25 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. –  Guut Boy Nov 25 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. –  Dramal Nov 25 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$. –  Guut Boy Nov 25 at 23:16

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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