The round complexity of two-party random selection

ABSTRACT

We study the round complexity of two-party protocols for generating a random n-bit string such that the output is guaranteed to have bounded bias (according to some measure) even if one of the two parties deviates from the protocol (even using unlimited computational resources). Specifically, we require that the output's statistical difference from the uniform distribution on zoⁿ is bounded by a constant less than 1.We present a protocol for the above problem that has 2 log^*n+O(1) rounds, improving a 2n-round protocol that follows from the work of Goldreich, Goldwasser, and Linial (FOCS'91). Like the GGL protocol, our protocol actually provides a stronger guarantee, ensuring that the output lands in any set T⊆zoⁿ of density μ with probability at most O(√μ+δ), where δ is an arbitarily small constant.We then prove a matching lower bound, showing that any protocol guaranteeing bounded statistical difference requires at least log^*n - log^* log^*n-O(1) rounds. As far as we know, this is the first nontrivial lower bound on the round complexity of random selection protocols (of any type) that does not impose additional constraints (e.g. on communication or "simulatability").We also state several results for the case when the output's bias is measured by the maximum multiplicative factor by which a party can increase the probability of a set T ⊆ zoⁿ.

REFERENCES

• 1: N. Alon and M. Naor. Coin-flipping games immune against linear-sized coalitions. In Proc. 31st FOCS, 1990.
• 2: M. Ben-Or and N. Linial. Collective coin-flipping.Randomness and Computation, S. Micali ed., Academic Press, New York, 1989.
• 3: M. Blum. Coin flipping by telephone. In IEEE Spring COMPCOM, 1982.
• 4: Ravi B. Boppana , Babu O. Narayanan, Perfect-Information Leader Election with Optimal Resilience, SIAM Journal on Computing, v.29 n.4, p.1304-1320, Feb. 2000 to March 2000 [doi>10.1137/S0097539796307182]
• 5: Christian Cachin , Claude Crepeau , Julien Marcil, Oblivious Transfer with a Memory-Bounded Receiver, Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.493, November 08-11, 1998
• 6: I. Damgard. Interactive hashing can simplify zero-knowledge protocol design. In Proc. CRYPTO '95, Springer LNCS 403, 1994.
• 7: I. Damgard, O. Goldreich, and A. Wigderson. Hashing functions can simplify zero-knowledge protocol design (too). TR RS-94-39. BRICS, 1994.
• 8: Y. Ding, D. Harnik, A. Rosen, and R. Shaltiel. Constant-round oblivious transfer in the bounded storage model. In Proc. 1st TCC, Springer LNCS 2951, 2004.
• 9: Uriel Feige, Noncryptographic Selection Protocols, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.142, October 17-18, 1999
• 10: Oded Goldreich , Shafi Goldwasser , Nathan Linial, Fault-tolerant Computation in the Full Information Model, SIAM Journal on Computing, v.27 n.2, p.506-544, April 1998 [doi>10.1137/S0097539793246689]
• 11: Oded Goldreich , Silvio Micali , Avi Wigderson, Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems, Journal of the ACM (JACM), v.38 n.3, p.690-728, July 1991 [doi>10.1145/116825.116852]
• 12: Oded Goldreich , Amit Sahai , Salil Vadhan, Honest-verifier statistical zero-knowledge equals general statistical zero-knowledge, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.399-408, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276852]
• 13: J. Katz and R. Ostrovsky. Round-optimal secure two-party computation. In Proc. CRYPTO '04. Springer LNCS 3152, 2004.
• 14: C. Lautemann. BPP and the polynomial hierarchy. IPL 14, 1983.
• 15: Yehuda Lindell, Parallel Coin-Tossing and Constant-Round Secure Two-Party Computation, Proceedings of the 21st Annual International Cryptology Conference on Advances in Cryptology, p.171-189, August 19-23, 2001
• 16: M. Naor, R. Ostrovsky, R. Venkatesan, and M. Yung. Perfect zero-knowledge arguments for NP can be based on general complexity assumptions. J. Cryptology 11, 1998.
• 17: Rafail Ostrovsky , Sridhar Rajagopalan , Umesh Vazirani, Simple and efficient leader election in the full information model, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.234-242, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195141]
• 18: Alexander Russell , Michael Saks , David Zuckerman, Lower bounds for leader election and collective coin-flipping in the perfect information model, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.339-347, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301337]
• 19: Alexander Russell , David Zuckerman, Perfect Information Leader Election in log^* n + O(1) Rounds, Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.576, November 08-11, 1998
• 20: Michael Saks, A robust noncrytographic protocol for collective coin flipping, SIAM Journal on Discrete Mathematics, v.2 n.2, p.240-244, May 1989 [doi>10.1137/0402020]
• 21: S. Sanghvi. A study of two-party random selection protocols. Undergraduate Thesis. Harvard University, 2004.
• 22: A. Yao. How to generate and exchange secrets. In Proc. 27th FOCS, 1986.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Interactive and reactive computation

General Terms:
Algorithms, Security, Theory

Keywords:
coin-flipping, cryptography, distributed computing