Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
Let $X$ denote one distribution. Let $f,g, \text{ and } h$ denote three functions. If we have the results: $g(X)$ is within a negligible statistical distance of $h(X)$. Is it possible to prove
$$(f(X),g(X)) \text{ is within negligible statistical distance of } (f(X),h(X))$$
I was struggling with this problem for a long time. Any hints are welcomed.
No, you cannot prove that, since it is not generally true. Consider the following counter example.
Let $X$ be a distribution over $\{0,1\}$ with $$\Pr_{b\gets X}[b=0] = \Pr_{b\gets X}[b=1]=\frac{1}{2}.$$ Let $f,g,h : \{0,1\} \to \{0,1\}$ be defined as $$f : b \mapsto b,\quad g : b \mapsto b, \quad \text{and} \quad h : b \mapsto b\oplus 1.$$
The statistical distance between the distributions $g(X)$ and $h(X)$ is zero and thereby negligible.
\begin{align}&\frac{1}{2} \sum_{b\in \{0,1\}} \left|\Pr_{b'\gets X}[g(b')=b] - \Pr_{b'\gets X}[h(b')=b]\right|\\ =&\frac{1}{2} \sum_{b\in \{0,1\}} \left|\Pr_{b'\gets X}[b'=b] - \Pr_{b'\gets X}[b'\oplus 1=b]\right|\\ =&\frac{1}{2} \sum_{b\in \{0,1\}} \left|\frac{1}{2} - \frac{1}{2}\right| = 0 \end{align}
However, the support of the two distributions $$(f(X),g(X)) \in \{(0,0),(1,1)\}\quad \text{and} \quad (f(X),h(X)) \in \{(0,1),(1,0)\}$$ are completely disjoint and their statistical distance is thus $1$ which is non-negligible.
