3
$\begingroup$

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?

$\endgroup$

3 Answers 3

2
$\begingroup$

I don't understand your plaintext space/ciphertext space distinction here. Could you try to clarify that part of your question?

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

$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$
    – kodlu
    Jan 23, 2023 at 13:17
  • 1
    $\begingroup$ @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. $\endgroup$
    – Mark
    Jan 23, 2023 at 20:31
  • 1
    $\begingroup$ @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. $\endgroup$
    – Mark
    Jan 23, 2023 at 20:35
  • $\begingroup$ very clear thank you $\endgroup$
    – kodlu
    Jan 24, 2023 at 0:24
0
$\begingroup$

It was explained by Rafael Pass and Abhi Shelat in "A Cource in Cryptography", [PS2010'Section 3.1: Computational Indistinguishability]


enter image description here

$\endgroup$
0
$\begingroup$

Your understanding of an ensemble in this context is incorrect. An ensemble in this context is a sequence of probability distributions.

Given two probability distributions $X, Y$, you can consider the best-possible distinguishing probability (for distinguishers running in some bounded time) between a random sample from $X$ and a random sample from $Y$. You will get a number, and that is fine for concrete security. But if you want to consider asymptotic security, then you need to consider two infinite sequences of probability distributions $\{X_i\}_{i =1, \ldots}, \{Y_i\}_{i =1, \ldots}$ where the distributions are indexed by the security parameter.

I suggest looking at Katz-Lindell, "Introduction to Modern Cryptography (3rd edition)." They discuss this issue in Section 3.1 and more formally in Chapter 8 (especially Section 8.8).

$\endgroup$

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.