Score:1

Definition of Polynomial-Time Indistinguishability

lk flag

We call two ensembles $X$ and $Y$ indistinguishable in polynomial time if for every probabilistic polynomial-time algorithm $D$ and for every positive polynomial $p(\cdot)$, and all sufficiently large n's we have $$|Pr[D(X_n,1^n)=1]-Pr[D(Y_n,1^n)=1]| < \frac{1}{p(n)}$$.

One question I didn't confront with at the beginning is, does the definition imply that $|X_n|=|Y_n|$?

After a little bit of thinking I came to the following conclusion which I want to verify. $X_n$ can be distributed over $\{0,1\}^{poly_1(n)}$ while $Y_n$ is distributed over $\{0,1\}^{poly_2(n)}$. For sufficiently large $n$ the polynomials grow monotonously and one could use the length as a distinguishing attack. We know there exists a distinguisher that makes by coincidence use of the very exact same polynomial $p_1$ or $p_2$ and can easily compare the lengths of the input with its hardwired polynomial. We would require that an $N$ exists such that $|X_n|=|Y_n|$ is true for all $n>N$ (which would imply the polynomials to be equal), else we will never be able to find such ensembles.

Marc Ilunga avatar
tr flag
Generally speaking, it would seem like a distinguishing notion for distributions over different sets would be somewhat tricky or perhaps meaningless? It may well be that the effective support of one RV is different (probability 0 for one element). But otherwise we may have trivial distinguishing strategies like the one you mentioned.
killertoge avatar
lk flag
That was my thought. Like definitions like statistically close would make no sense unless you say the elements that do not exist in one sets appear with probability 0.
Score:2
ng flag

One can have $|X_n|\neq |Y_n|$, or even $|X_n| = f(n) \neq \infty = |Y_n|$ for some function $f(n)$. This occurs in practice, namely in lattice-based cryptography, where $X_n$ is some (ideal) discrete Gaussian, while $Y_n$ is some approximation to it of finite support (so one can sample from it in constant-time). For a discrete gaussian of mean $\mu$ and standard deviation $\sigma$, one can replace it with that same gaussian conditioned to being in the interval $[\mu-10\sigma, \mu+10\sigma]$ or something.

What I think you're missing is that being "distinguishable" vs "indistinguishable" is not a binary. If one ignores pseudorandomness for a bit (and talks about purely statistics), then often the total variation distance (or statistical distance)

$$\Delta(X, Y) = \frac{1}{2}\sum_{x\in\mathsf{supp}(X)\cup\mathsf{supp}(Y)}|\Pr[X = x]-\Pr[Y = x]|.$$

This (essentially) measures how hard it is to distinguish $X$ and $Y$. For example, if $\Delta(X,Y)\leq \epsilon$, then it takes $O(1/\epsilon^2)$ samples from an unknown distribution to reliably (say with probability close to 1) distinguish between the cases of the samples coming from $X$ or $Y$. So if $\epsilon \approx 2^{-n}$, one can say they cannot be distinguished with polynomially many samples.

There are other times that one may want to say it is hard to distinguish distributions that have $|X_n|\neq |Y_n|$. For example, let $X_n$ be uniform over all functions $F: \{0,1\}^n\to\{0,1\}^n$. Let $Y_n$ be uniform over all invertible functions with this domain/range. Then $|X_n|\neq |Y_n|$, but one can bound the statistical distance between these distributions provided one gets at most $q$ queries (this is called "PRP-PRF Switching Lemma").

killertoge avatar
lk flag
I mean the ensembles can still have same cardinality but are just distributing their mass probability over segments that are not identical. The encoding of both functions should have the same length for a proper challenge. It is not contradicting my thought yet if I am not mistaken. Whether you use it in practise is a different world. But I can think of more than my trivial strategies. Its enough to find a distinguisher that uses a polynom that is sandwiched by $p_1,p_2$. (which might be very impractical).
I sit in a Tesla and translated this thread with Ai:

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.