Let's consider this definition of computational indistinguishability.

Computational indistinguishability. A probability ensemble $X=\{X(a, n)\}_{a \in\{0,1\}^{*} ; n \in \mathbb{N}}$ is an infinite sequence of random variables indexed by $a \in\{0,1\}^{*}$ and $n \in \mathbb{N}$. In the context of secure computation, the value $a$ will represent the parties' inputs and $n$ will represent the security parameter. Two probability ensembles $X=\{X(a, n)\}_{a \in\{0,1\}^{*} ; n \in \mathbb{N}}$ and $Y=\{Y(a, n)\}_{a \in\{0,1\}^{*} ; n \in \mathbb{N}}$ are said to be computationally indistinguishable, denoted by $X \stackrel{c}{\equiv} Y$, if for every non-uniform polynomial-time algorithm $D$ there exists a negligible function $\mu(\cdot)$ such that for every $a \in\{0,1\}^{*}$ and every $n \in \mathbb{N}$, $$ |\operatorname{Pr}[D(X(a, n))=1]-\operatorname{Pr}[D(Y(a, n))=1]| \leq \mu(n) $$

From my understanding $D$ is the distinguishing algorithm, e.g. the adversary in security proofs. An instance of the random variable $X(a,n)$ is considered as the encryption algorithm. However from my understanding only the output of the encryption algorithm, e.g. the ciphertext, is passed to $D$. For people coming from mathematical background this is a bit confusing because random variable is a function $X:Ω \rightarrow Ε$ where $Ω$ is the σ-algebra of the events space and $E$ is a measurable space.

Can someone help me clarify the notation and the definition that is used? Thanks in advance.


1 Answer 1


An instance of the random variable 𝑋(𝑎,𝑛) is considered as the encryption algorithm.

I believe an instance of the variable $X(a,n)$ would usually refer to an encryption of a corresponding input $a$. ($X(a,n)$ is the encryption of $a$ with security parameter $n$)

Intuitively, this definition says that if you are given an element from either $X$ or $Y$, it is hard to distinguish which where it came from.

The distinguisher $D$ is given either an element from $X$ or $Y$, and the probability $|\operatorname{Pr}[D(X(a, n))=1]-\operatorname{Pr}[D(Y(a, n))=1]|$ indicates the ability for the distinguisher $D$ to distinguish these. Consider, as an example, if $$|\operatorname{Pr}[D(X(a, n))=1]-\operatorname{Pr}[D(Y(a, n))=1]| = 1,$$ what would this imply about $D$, $X$ and $Y$?


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.