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. $$

  • $\begingroup$ 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. $\endgroup$
    – Maeher
    Oct 16, 2020 at 9:51
  • $\begingroup$ @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. $\endgroup$
    – Myath
    Oct 16, 2020 at 10:19
  • 1
    $\begingroup$ Then your description is a bit lacking. It seemed very clear to me that you only get a single sample. $\endgroup$
    – Maeher
    Oct 16, 2020 at 11:34
  • $\begingroup$ @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. $\endgroup$
    – Myath
    Oct 16, 2020 at 23:10


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.