I am given an oracle $A$ that takes input samples from two distributions $\chi_1$ and $\chi_2$.

Suppose we have $Pr_{x \sim \chi_1}[A(x) = 1] = p_1$ and $Pr_{x \sim \chi_2}[A(x) = 1] = p_2$, where $p_1 \neq p_2$.

In general, how can we use $A$ to construct a distinguisher to determine whether the input samples are from $\chi_1$ or $\chi_2$? And how good is the running time of such distinguisher?

Thank you very much! :)


Hint: Run $A$ on lots of samples $x_1,\ldots,x_n$ and compute the average $(A(x_1)+\cdots+A(x_n))/n$.

| cite | improve this answer | |

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.