Suppose a verfier gets N independent random numbers from an untrusted guy. These random numbers can take values 0 or 1. An honest guy will send the verifier each random number with a probability p. So the expected total value the verifier receives is Np. However a dishonest guy can send these random numbers with probabilities different from p such that the total expected value is still Np. Can the verifier devise a test on all N or a subset of random numbers to distinguish honest guy from dishonest guy with a good enough probability?
$\begingroup$
$\endgroup$
3
-
$\begingroup$ What are your thoughts on the problem at hand? what have you tried so far?? $\endgroup$– The IntegratorMay 14, 2018 at 18:54
-
$\begingroup$ It is a problem to prove the security of a protocol which is dependent on how well I can distinguish the honest guy from the adversary. The honest case probability p = 1 - exp(-2|a|^2/2), where |a|^2 is typically very low(<0.5). The probability for a dishonest guy looks like p' = 2 - (exp(-|x-a|^2/2) + exp(-|x+a|^2/2)). It is easy to see for an honest guy, |a| = |x| for all N random numbers. But an adversary can play around with x. It is easy to distinguish the honest and adversary distributions for large |a| but not apparently not when |a| is very small. $\endgroup$– Niraj KumarMay 14, 2018 at 19:33
-
$\begingroup$ The problem is unclear as presently written. Are you saying that $p$ is the probability of getting the number one, or are you saying that it is the probability of "sending" either number to the verifier? Because if it is the latter, that does not give an expected total value of $Np$. $\endgroup$– BenFeb 9, 2020 at 20:28
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
When we reduce a distribution down to the mean (a single number) then we lose a lot of information about the distributions. In your case you have two distributions of numbers: the distribution of the numbers provided by the honest man, and the distribution of numbers provided by the adversarial man.
Though the means are the same, if we retain all of the numbers that we've been provided, we have a lot more information to work with. In particular, we could look at the histograms of the two sets of numbers that we receive. If they're significantly different, then we would suspect that the distributions come from different men. In statistics, we would say "We reject the null hypothesis, that the distributions come from the same population."
And here's where our statistical tests come in (e.g. t-test, f-test, anova, etc.) :) Find the right test and apply it to see if the distributions come from the same or different populations. The tests are not statements of certainty. Instead, you'll come to a conclusion that says something like "We can say that the populations are different with a probability of 95%."
