I am reading Professor Lindell's "How To Simulate It - A Tutorial on the Simulation Proof Technique" paper, which is very enlightening.

I am trying to follow through the proof of the security of Blum's coin-tossing protocol and have some questions: in the end of page 41 it says ": Let $b_1$ be the value committed in the commitment $c$ sent by $A$ (since $A$ is deterministic and this is the first message, this is a fixed value)."

  1. I don't understand why we can assume $A$ is deterministic?
  2. In general, should the security proof work for probabilistic adversaries?

1 Answer 1


Actually, a probabilistic adversary $A$ can be viewed as a deterministic adversary with a random tape: $A$ just picks a random string in the beginning and then run deterministically according to that fixed string. In the proof, the simulator $S$ uses the real-world adversary $A$ as a black box but can control its random tape (because a random tape always contains fair random strings that can be generated by anyone). So, $S$ can simulate the output of a probabilistic adversary $A$ by first choosing a random string $r$ then dealing with the resulting deterministic adversary $A'=A(r)$.


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.