Consider the game-based security proofs, i.e. a game played between the challenger and a PPT adversary.

My question is... what is the source of random coins for the adversary? Is is valid to say that the challenger provides the coins to the adversary?

"If" the challenger is the one giving the coins to the adversary, then I assume it will be possible for the challenger to initialize the adversary on the "same" coins and expect a deterministic behaviour.

If someone has a link for further explanation it would be really healpul. Thanks a lot.


1 Answer 1


It certainly wouldn't make sense for the challenger to provide the coins. If you are working with non-uniform adversaries, then you can assume that the adversary is deterministic. This is due to the fact that $BPP \subset P/poly$. Intuitively, a non-uniform adversary can receive as "advice" the best random coins that maximize its probability of winning the game. However, if you are working with uniform adversaries, then you cannot assume that the adversary is deterministic.

Note, that as part of the proof, if you need to somehow simulate something for the adversary, then you can always fix its random tape to a uniformly chosen string and then work with an effectively deterministic adversary. However, this is different to having the "challenger" in the game provide the coins; that would make no sense.

  • $\begingroup$ Could you please elaborate on why it it is fine to fix the random tape to a uniformly chosen string (in the game-based proofs)? $\endgroup$
    – Lumlum
    Commented Dec 12, 2022 at 14:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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