7
$\begingroup$

I've been reading this question where a detailed description of mine is given, I've understood that a polynomial-time adversary is an adversary for which the only feasible strategy are those that take polynomial time to run; anyway, I just can't understand why do we require the adversary to be probabilistic.

In Katz' book is explained that this is natural because the honest parties are required to be probabilistic (in order to generate random keys and so on), actually this isn't very natural for me (the fact that the honest parties are probabilistic shouldn't imply we must consider adversaries to be probabilistic too).

Also, they say that this is useful because the ability to toss coins may provide additional power, and therefore if the scheme is secure against PPT adversaries, then is secure against deterministic polynomial-times adversaries.

Please, someone can explain me why is this a valid argument? Thank you very much!.

|improve this question
$\endgroup$
  • 3
    $\begingroup$ Why is this not a valid argument? Or in other words, what argument do you have against allowing adversaries to be probabilistic? Certainly, any reasonable adversary would know about the rand() function... Of course, an adversary is not required to actually use his randomness source. $\endgroup$ – fkraiem Jun 21 '14 at 18:35
  • $\begingroup$ The last line was the answer. Thank you very much! $\endgroup$ – Daniel Jun 21 '14 at 19:24
  • $\begingroup$ Okay, I'll turn that into an answer. $\endgroup$ – fkraiem Jun 21 '14 at 19:25
  • 1
    $\begingroup$ Regarding the last question. Within the field of computational complexity theory it's commonly believed that the class of problems solvable by probabilistic PT machines is strictly larger than the class of problems solvable by deterministic PT machines. That is, we strongly believe (note, however, that this is not formally proved) that P $\subsetneq$ BPP, hence, if we can prove something secure against an attacker in BPP, we've also automatically shown it secure against an attacker in P. $\endgroup$ – hakoja Jun 22 '14 at 12:15
  • 1
    $\begingroup$ @hakoja Actually, the fact that P $\subseteq$ BPP implies by itself that it suffices to consider probabilistict adversaries to rule out deterministic ones (this is basically fkraiem's argument, no need of the conjecture here). What the additional condition P $\subsetneq$ BPP would imply is that this is "necessary", in the sense that taking away the randomness source of the attacker would lead to weaker adversaries and would not rule out practical/real attacks, where randomness sources exist. $\endgroup$ – Daniel Mar 11 '17 at 11:46
7
$\begingroup$

An algorithm being probabilistic means that it is allowed to "throw coins", and use the results of the coin throws in its computations. This is reasonable because a realistic adversary has access to certain pseudo-randomness sources (such as the C rand() function). Of course, a probabilistic algorithm is not required to use its randomness source (i.e., throw coins), but even if it were, it could just ignore the results.

|improve this answer
$\endgroup$

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.