On p.2, Example 1.1 (in this paper), there is a description of a coin tossing protocol with bias 1/4. In the paragraph below the example, they note that for a protocol with $r$ rounds (assume for the sake of clarity it is $poly(n)$) there's a bias of $\frac{1}{r}=\frac{1}{poly(n)}$.

I am quite new to Cryptography, and since the paper they cite in this context is quite old and very different to their example, I'm left with two questions:

  1. How can their example (Example 1.1) be adapted to a $poly(n)$ round coin-toss protocol with bias at most $\frac{1}{poly(n)}$?

  2. How is the final outcome in a multi-round coin toss determined? (i.e., we tossed more than one coin each, so what is the final result?)



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy