Score:1

"randomized" indistinguishability vs "deterministic" indistinguishability

cn flag

Let $X$ be a measurable space. For each $n\in\mathbb N$, let $P_n$ and $Q_n$ be probabilities on $X$. We say that $(P_n)_{n\in\mathbb N}$ and $(Q_n)_{n\in\mathbb N}$ are statistically indistinguishable iff for all measurable set $E\subseteq X$, the function \begin{equation} n\mapsto |P_n(E) - Q_n(E)| \end{equation} is negligible.

But what if we allow "randomness"? Let's say that $(P_n)_{n\in\mathbb N}$ and $(Q_n)_{n\in\mathbb N}$ are randomly statistically indistinguishable (I just made up this terminology) iff for all measurable space $Y$, all probability family $(R_n)_{n\in\mathbb N}$ on $Y$, and all measurable set $E\subseteq X\times Y$, the function \begin{equation} n\mapsto |(P_n\times R_n)(E) - (Q_n\times R_n)(E)| \end{equation} is negligible.

Random statistical indistinguishability clearly implies statistical indistinguishability. But is the converse true?

us flag
Possible duplicate of https://crypto.stackexchange.com/questions/73108/statistical-closeness-implies-computational-indistinguishability
Mark avatar
ng flag
From my reading it seems like you are asking that if two probability distributions have marginals that are close, it implies the distributions are close (which is clearly false). Am I misunderstanding something?
kelalaka avatar
in flag
[Cross-posted with math.se](https://math.stackexchange.com/q/4403008/338051)
Score:2
ng flag

Big caveat that I'm not a probabilist, and your answer really doesn't include much cryptography, so might be better suited for asking a probabilist somewhere (say on math.se or something).

As mentioned in the comments, this is easily false. Let $P_n, Q_n$ both be distributed as any symmetric distribution, and let $R_n\sim \{-1,1\}$ be uniform. Define the joint distributions $P_n\times R_n$ and $Q_n\times R_n$ as follows --- the marginals on both $X$ and $Y$ are fixed as above, but

$$\Pr[(P_n\times R_n)\in E] = \Pr[(P_n\times R_n)\in E\mid R_n = b]\Pr[R_n = b].$$

Now, as we are discussing symmetry, write $X = X_1\cup X_{-1}$. Assume the symmetry swaps these two components. We now define the conditional distributions

$$\Pr[(P_n\times R_n)\in E\mid R_n = b] = \begin{cases}0 & E\cap X_{b}\neq \emptyset \\ 2\Pr[P_n(E_X)]&\text{else} \end{cases}.$$

This is to say the conditional distribution is defined such that a random variable with $R_n = b$ is in $X_b$, e.g. the components $P_n, R_n$ are "perfectly correlated". For $Q_n$, do the same, but reverse the roles of $X_1, X_{-1}$, e.g. have $Q_n, R_n$ be "perfectly anti-correlated".

It is straightforward to see these random variables have identical marginals, and are therefore perfectly indistinguishable (and statistically indistinguishable as well). It is also straightforward to see that the joint distributions $P_n\times R_n$ and $Q_n\times R_n$ have disjoint supports, so

$$0 = \Delta(P_n, Q_n) \leq \Delta(P_n\times R_n, Q_n\times R_n) = 1,$$

and therefore they are not randomly statistically indistinguishable.

Note that if you assume $P_n, R_n$ are independent (in your language $E$ factors as $E_X\times E_Y$ I think), the answer is easily true. As a sketch of the proof, by the data-processing inequality we have that $\Delta(P_n, Q_n) \geq \Delta(f(P_n), f(Q_n))$ for any randomized $f$, including $f : X\to X\times Y$ that samples $R_n$ independently, and outputs $f(x) = (x, R_n)$. This isn't what you asked, but its still useful to note.

mangohost

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.