In the Cornell lecture notes, computational indistinguishability is defined as

Definition 69.4 (Computational Indistinguishability). Let $\{X_n\}_n$ and $\{Y_n\}_n$ be ensembles where $X_n$,$Y_n$ are distributions over $\{0, 1\}^{l(n)}$ for some polynomial $l(·)$. We say that $\{X_n\}_n$ and $\{Y_n\}_n$ are computationally indistinguishable if for all non-uniform p.p.t. $D$ (called the “distinguisher”), there exists a negligible function $e(·)$ such that $∀n ∈ N$

$Pr[t ← X_n, D(t) = 1] − Pr[t ← Y_n, D(t) = 1] < e(n)$

My question is, why do we need ensembles of distribution? Why not just define it over two distributions $X$ and $Y $?


1 Answer 1


Why not just define it over two distributions $X$ and $Y$?

Because this is an asymptotic definition (using a negligible function explicitly).
If you were to only consider two fixed distributions, there would be no scaling with the security parameter (and thus the involved lengths) possible. This is why we use ensembles, parametrized by the value of the security parameter $n$.


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.