2
$\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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\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}$).

Improve this answer
$\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 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 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 at 20:35
  • $\begingroup$ very clear thank you $\endgroup$
    – kodlu
    Jan 24 at 0:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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