Question on notation of random variables in probability ensembles

us flag

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.

jp flag

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


Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.