1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$ Nov 16, 2022 at 20:39
  • $\begingroup$ 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. $\endgroup$
    – killertoge
    Nov 17, 2022 at 0:21

1 Answer 1

2
$\begingroup$

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").

$\endgroup$
1
  • $\begingroup$ 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). $\endgroup$
    – killertoge
    Nov 17, 2022 at 13:16

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.