# Why we need to consider a probability ensemble and not just a probability distribution in the definition of Security under Simulation?

I'm currently reading this classic paper "How To Simulate It" and on most of the definitions it is using the term probability ensemble to represent the message space. From my understanding a probability ensemble is like a stochastic process and a probability distribution is an instance of a stochastic process. For example, if we have $$\{X_n\}_{n \in \mathbb{N}}$$ then we can consider it equivalent to $$X(n)$$ where $$n \in \mathbb{N}$$ and $$X(5)$$ for example is an instance of the probability ensemble, a probability distribution.

I'm kind of confused about why we need to consider this structure for the plaintext space. Actually, it would make more sense to me since we consider a non-uniform $$PPT$$ to consider this structure as the ciphertext space, but probably this isn't the case. Can you help me clarify this?

As for $$\{X_n\}_n$$ vs $$X(n)$$, I would just say one reason to not consider probability ensambles as stochastic processes is that there is no reason to expect $$X(n)$$ and $$X(n-1)$$ to be connected in some way (say be martingale, or have any other property a stochastic process might typically have). The main property you want from whatever way you formalize things as is a mapping from integers to probability distributions, so you can coherently use the notion of "negligible" functions (where $$f(n)\in\mathsf{negl}(n)$$ if $$f(n) = n^{-\omega(1)}$$), which are very useful for analysis. This is really only relevant for asymptotic security though, for concrete security you'll typically set $$n = 128$$, and not work with arbitrary neglible functions (such as $$f_0(n) = 2^{-(\log n)^2}$$), and instead work with explicit inverse exponential functions ($$f_1(n) = 2^{-n}$$).
• A question, what is $n^{-\omega(1)}$? I am familiar with $\Omega(1)$ denoting a quantity that grows at least like a constant with increasing $n.$ Just confused about the lowercase omega. Also I don't understand your distinction between the two functions given as arbitrary vs explicit. Did you mean to have a negative in the first exponent? Even assuming that my confusion remains since both have $n$ explicitly in the expression. Jan 23 at 13:17
• @kodlu $\omega(1)$ is a super-constant quantity, i.e. $>$ rather than $\geq$, similarly to how $O(1)$ and $o(1)$ are $\leq$ constant and $<$ constant. Formally $n^{-\omega(1)}$ are the functions that are of the form $(1/\mathsf{poly}(n))^{c(n)}$ for some super-constant $c(n)$, i.e. negligible functions.
• @kodlu for $f_0$ and $f_1$, the point is that both are perfectly good negligible functions. But a security bound of the form $f_0$ is incredibly weak. An adversary that runs in $1/f_0(n)$ running time is not technically "efficient" (as this quantity is super-poly), but for an instance size $n = 2^{10}$ one has that $1/f_0(n) = 2^{100}$ running time, i.e. even for a relatively large instance size of $n\approx 1000$ it does not require $2^{128}$ running time.