# Are these two assumptions equivalent?

Let $$f_a : S \to R$$ is a family of functions indexed by $$a\in P$$.

Consider the assumption that $$(a, f_a(x))$$ is indistinguishable from uniform, over the distribution of $$a\leftarrow U$$ (uniform) and $$x\leftarrow D$$ (some efficiently sampleable distribution).

Is this assumption equivalent to, for all but a negligible fraction of $$a$$, $$f_a(x)$$ is indistinguishable from uniform over the distribution of $$x$$?

I'm inclined to think they are. But I'm not very sure and would like a proof.

EDIT: to make this more clear. Let $$A$$ be a random variable with uniform distribution $$U$$ over $$P$$, and $$X$$ be an independent random variable with some efficiently sampleable distribution $$D$$ over $$S$$. Also, let $$Y$$ be an independent uniformly random variable over the codomain $$R$$.

The 1st assumption says for any polynomial-time distinguisher $$M$$, consider the random variable $$M(A, f_A(X))$$ and $$M(A, Y)$$, then $$|Pr[M(A, f_A(X))=1] - Pr[M(A, Y)=1]| \le negl.$$

The 2nd assumption says, there exists a subset $$Q \subseteq P$$ with $$1-|Q|/|P|$$ negligible, such that for any $$a \in Q$$, for any polynomial-time distinguisher $$N$$, $$|Pr[N(f_a(X)) = 1] - Pr[N(Y)=1]| \le negl.$$

• What about $f_{a\Vert b}(x) = g_a(x)\Vert b$? If $g$ is say a prf, the second assumption should be true, but the first is not. Oct 16 '20 at 9:51
• @Maeher The 2nd assumption is not true for that example. Once you've fixed $(a,b)$, $g_a(x)||b$ is not indistinguishable from uniform over the probability of $x$ because the last bits are always $b$, constant. Oct 16 '20 at 10:19
• Then your description is a bit lacking. It seemed very clear to me that you only get a single sample. Oct 16 '20 at 11:34
• @Maeher The definition of a distinguisher always takes as input only a single sample. But then we consider the input as a random variable and then look at the distribution of the output random variable. Oct 16 '20 at 23:10