Abstract
We consider the problem of random selection, where p players follow a protocol to jointly select a random element of a universe of size n. However, some of the players may be adversarial and collude to force the output to lie in a small subset of the universe. We describe essentially the first protocols that solve this problem in the presence of a dishonest majority in the full-information model (where the adversary is computationally unbounded and all communication is via non-simultaneous broadcast). Our protocols are nearly optimal in several parameters, including the round complexity (as a function of n), the randomness complexity, the communication complexity, and the tradeoffs between the fraction of honest players, the probability that the output lies in a small subset of the universe, and the density of this subset.
The full version of this paper is available on ECCC [22].
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Alon, N., Naor, M.: Coin-flipping games immune against linear-sized coalitions. SIAM J. Computing 22(2), 403–417 (1993)
Antonakopoulos, S.: Fast leader-election protocols with bounded cheaters’ edge. In: Proc. 38th STOC, pp. 187–196 (2006)
Barak, B.: Constant-round coin-tossing with a man in the middle or realizing the shared random string model. In: 43rd FOCS (2002)
Blum, M.: Coin flipping by telephone. In: IEEE Spring COMPCOM (1982)
Beaver, D., Goldwasser, S.: Multiparty computation with faulty majority. In: Brassard, G. (ed.) CRYPTO 1989. LNCS, vol. 435, pp. 589–590. Springer, Heidelberg (1990)
Ben-Or, M., Goldwasser, S., Wigderson, A.: Completeness theorems for non-cryptographic fault-tolerant distributed computation. In: 20th STOC, pp. 1–10 (1988)
Ben-Or, M., Linial, N.: Collective coin fliping. In: Advances in Computing Research. Randomness and Computation, vol. 5, pp. 91–115. JAI Press, Greenwich, CT (1989)
Boppana, R., Narayanan, B.: Perfect-information leader election with optimal resilience. SIAM J. Computing 29(4), 1304–1320 (2000)
Bellare, M., Rompel, J.: Randomness-efficient oblivious sampling. In: 35th FOCS (1994)
Chaum, D., Crépeau, C., Damgård, I.: Multiparty unconditionally secure protocols. In: 20th STOC, pp. 11–19 (1988)
Cooper, J., Linial, N.: Fast perfect-information leader-election protocols with linear immunity. Combinatorica 15, 319–332 (1995)
Damgård, I.B.: Interactive hashing can simplify zero-knowledge protocol design without computational assumptions (extended abstract). In: Stinson, D.R. (ed.) CRYPTO 1993. LNCS, vol. 773, pp. 100–109. Springer, Heidelberg (1994)
Damgård, I., Goldreich, O., Wigderson, A.: Hashing functions can simplify zero-knowledge protocol design (too). TR RS-94-39. BRICS (1994)
Ding, Y.Z., Harnik, D., Rosen, A., Shaltiel, R.: Constant-round oblivious transfer in the bounded storage model. In: Naor, M. (ed.) TCC 2004. LNCS, vol. 2951, pp. 446–472. Springer, Heidelberg (2004)
Feige, U.: Noncryptographic selection protocols. In: 40th FOCS, pp. 142–152 (1999)
Goldreich, O.: A sample of samplers - a computational perspective on sampling (survey). Report 97-020, Electronic Colloquium on Computational Complexity (1997)
Goldreich, O., Goldwasser, S., Linial, N.: Fault-tolerant computation in the full information model. SIAM J. Computing 27(2) (1998)
Goldwasser, S., Levin, L.A.: Fair computation of general functions in presence of immoral majority. In: Menezes, A., Vanstone, S.A. (eds.) CRYPTO 1990. LNCS, vol. 537, pp. 77–93. Springer, Heidelberg (1991)
Goldwasser, S., Lindell, Y.: Secure computation without agreement. In: Malkhi, D. (ed.) DISC 2002. LNCS, vol. 2508, pp. 17–32. Springer, Heidelberg (2002)
Goldreich, O., Micali, S., Wigderson, A.: How to play ANY mental game. In: 19th STOC, pp. 218–229 (1987)
Goldreich, O., Sahai, A., Vadhan, S.: Honest-verifier statistical zero-knowledge equals general statistical zero-knowledge. In: 30th STOC (1998)
Gradwohl, R., Vadhan, S., Zuckerman, D.: Random Selection with an Adversarial Majority. Report TR06-26, Electronic Colloquium on Computational Complexity (February 2006)
Katz, J., Ostrovsky, R.: Round-optimal secure two-party computation. In: Franklin, M. (ed.) CRYPTO 2004. LNCS, vol. 3152, pp. 335–354. Springer, Heidelberg (2004)
Katz, J., Ostrovsky, R., Smith, A.: Round efficiency of multi-party computation with a dishonest majority. In: Biham, E. (ed.) EUROCRYPT 2003. LNCS, vol. 2656, pp. 578–595. Springer, Heidelberg (2003)
Lindell, Y.: Parallel coin-tossing and constant-round secure two-party computation. In: Kilian, J. (ed.) CRYPTO 2001. LNCS, vol. 2139, p. 171. Springer, Heidelberg (2001)
Pease, M., Shostak, R., Lamport, L.: Reaching agreement in the presence of faults. J. ACM 27(2), 228–234 (1980)
Lu, C., Reingold, O., Vadhan, S., Wigderson, A.: Extractors: Optimal up to constant factors. In: 35th STOC (2003)
Naor, M., Ostrovsky, R., Venkatesan, R., Yung, M.: Perfect zero-knowledge arguments for NP can be based on general complexity assumptions. J. Cryptology 11 (1998)
Nisan, N., Zuckerman, D.: Randomness is linear in space. J. Computer and System Sci. 52(1), 43–52 (1996)
Okamoto, T.: On relationships between statistical zero-knowledge proofs. J. Computer and System Sci. 60(1), 47–108 (2000)
Ostrovsky, R., Rajagopalan, S., Vazirani, U.: Simple and efficient leader election in the full information model. In: Proc. 26th STOC, pp. 234–242 (1994)
Ostrovsky, R., Venkatesan, R., Yung, M.: Interactive hashing simplifies zero-knowledge protocol design. In: Helleseth, T. (ed.) EUROCRYPT 1993. LNCS, vol. 765, pp. 267–273. Springer, Heidelberg (1994)
Raz, R., Reingold, O., Vadhan, S.: Extracting all the randomness and reducing the error in Trevisan’s extractors. J. Computer and System Sc. 65(1), 97–128 (2002)
Raz, R., Reingold, O., Vadhan, S.: Error Reduction for Extractors. In: 40th FOCS (1999)
Russell, A., Saks, M., Zuckerman, D.: Lower bounds for leader election and collective coin- flipping in the perfect information model. SIAM J. Computing 31, 1645–1662 (2002)
Radhakrishnan, J., Ta-Shma, A.: Bounds for dispersers, extractors, and depth-two superconcentrators. SIAM J. Discrete Math. 13(1), 2–24 (2000)
Russell, A., Zuckerman, D.: Perfect-information leader election in log* n + O(1) rounds. J. Computer and System Sci. 63, 612–626 (2001)
Saks, M.: A robust noncryptographic protocol for collective coin flipping. SIAM J. Discrete Math. 2(2), 240–244 (1989)
Sanghvi, S., Vadhan, S.: The round complexity of two-party random selection. In: 37th STOC (2005)
Vadhan, S.: Constructing locally computable extractors and cryptosystems in the bounded-storage model. J. Cryptology 17(1), 43–77 (2004)
Wigderson, A., Zuckerman, D.: Expanders that beat the eigenvalue bound: explicit construction and applications. Combinatorica 19(17), 125–138 (1999)
Yao, A.: How to generate and exchange secrets. In: Proc. 27th FOCS (1986)
Zuckerman, D.: Randomness-optimal oblivious sampling. Random Structures and Algorithms 11(4), 345–367 (1997)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Gradwohl, R., Vadhan, S., Zuckerman, D. (2006). Random Selection with an Adversarial Majority. In: Dwork, C. (eds) Advances in Cryptology - CRYPTO 2006. CRYPTO 2006. Lecture Notes in Computer Science, vol 4117. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11818175_25
Download citation
DOI: https://doi.org/10.1007/11818175_25
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-37432-9
Online ISBN: 978-3-540-37433-6
eBook Packages: Computer ScienceComputer Science (R0)