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 '20 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 '20 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 '20 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 '20 at 23:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.