Gordon, D., Katz, J.: Partial fairness in secure two-party computation. In: Proceedings of the 39th Annual ACM Symposium on Theory of computing, pp. Katz, J.: On achieving the “best of both worlds” in secure multiparty computation. Cambridge University Press, Cambridge (2004) Goldreich, O.: Foundations of Cryptography: Basic Applications, vol. 2. 364–369 (1986)Īverbuch, B., Blum, M., Chor, B., Silvio Micali, S.G.: How to implement Bracha’s O(log n) byzantine agreement algorithm (manuscript, 1985) In: Proceedings of the 18th Annual ACM Symposium on Theory of Computing, pp. 230–235 (1989)Ĭleve, R.: Limits on the security of coin flips when half the processors are faulty. In: Proceedings of the 30th Annual IEEE Symposium on Foundations of Computer Science, pp. Impagliazzo, R., Luby, M.: One-way functions are essential for complexity based cryptography. Naor, M.: Bit commitment using pseudorandomness. Håstad, J., Impagliazzo, R., Levin, L.A., Luby, M.: A pseudorandom generator from any one-way function. In: Proceedings of the 25th IEEE Computer Society International Conference, pp. 1–10 (1988)īlum, M.: Coin flipping by telephone - A protocol for solving impossible problems. In: Proceedings of the 20th Annual ACM Symposium on Theory of Computing, pp. This process is experimental and the keywords may be updated as the learning algorithm improves.īen-Or, M., Goldwasser, S., Wigderson, A.: Completeness theorems for non-cryptographic fault-tolerant distributed computation. These keywords were added by machine and not by the authors. Under standard assumptions (the existence of oblivious transfer), we show that Cleve’s lower bound is tight: we construct an r-round protocol with bias O(1/ r). In this paper we establish the optimal trade-off between the round complexity and the bias of two-party coin-flipping protocols. However, the best previously known protocol only guarantees \(O(1/\sqrt)\) bias, and the question of whether Cleve’s bound is tight has remained open for more than twenty years. A classical result by Cleve showed that for any two-party r-round coin-flipping protocol there exists an efficient adversary that can bias the output of the honest party by Ω(1/ r). Coin-flipping protocols allow mutually distrustful parties to generate a common unbiased random bit, guaranteeing that even if one of the parties is malicious, it cannot significantly bias the output of the honest party. We address one of the foundational problems in cryptography: the bias of coin-flipping protocols.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |