Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|improve this question
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. – fkraiem Jun 21 '14 at 18:35
The last line was the answer. Thank you very much! – Solid Snake Jun 21 '14 at 19:24
Okay, I'll turn that into an answer. – fkraiem Jun 21 '14 at 19:25
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. – hakoja Jun 22 '14 at 12:15
up vote 2 down vote accepted

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.

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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