How to spread adversarial nodes?: rotate!

ABSTRACT

In this paper we study the problem of how to keep a dynamic system of nodes well-mixed even under adversarial behavior. This problem is very important in the context of distributed systems.More specifically, we consider the following game: There are n white pebbles and ε n black pebbles for some fixed constant ε < 1. Initially, all of the white pebbles are laid down in a ring, and the adversary has all of the black pebbles in its bag. In each round, the adversary can look at the entire ring and can select to add a black pebble to the ring (if its bag is not empty) or to take any black pebble from the ring and put it back into its bag (i.e. we consider adaptive adversaries). However, the adversary cannot place a black pebble into any position it likes. This is handled by a join strategy to be specified by the system. The goal is to find an oblivious join strategy, i.e. a strategy that cannot distinguish between the white and black pebbles in the ring, that integrates the black pebbles into this ring and may do some further rearrangements so that for a polynomial number of rounds the adversary will not manage to include its black pebbles into the ring so that there is a sequence of s=Θ(log n) consecutive pebbles in which at least half of the pebbles are black. If this is achieved by the join strategy, it wins. Otherwise, the adversary wins.Of course, the brute-force strategy of rearranging all of the pebbles in the ring at random after each insertion of a black pebble will achieve the stated goal, with high probability, but this would be a very expensive strategy. The challenge is to find a join strategy that needs as little randomness and as few rearrangements as possible in order to win with high probability. In this paper, we present and analyze a very simple strategy called k-rotation that chooses k-1 existing positions uniformly at random in the ring, creates a new position uniformly at random in the ring, and then rotates the new pebble and the k-1 old pebbles along these positions. Interestingly, even if the adversary has just $s$ pebbles, it can still win for k=2. But the k-rotation rule wins with high probability for k=3 as long as ε<2/3, demonstrating that there is a sharp threshold for keeping pebbles in a sufficiently perturbed state.

REFERENCES

• 1: I. Abraham and D. Malkhi. Probabilistic quorums for dynamic systems. In Proc. of the 18th Annual Conference on Distributed Computing (DISC), 2003.
• 2: James Aspnes , Gauri Shah, Skip graphs, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 3: B. Awerbuch and C. Scheideler. Group Spreading: A protocol for provably secure distributed name service. In Proc. of the 31st International Colloquium on Automata, Languages and Programming (ICALP), 2004.
• 4: Michael Ben-Or , Shafi Goldwasser , Avi Wigderson, Completeness theorems for non-cryptographic fault-tolerant distributed computation, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.1-10, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62213]
• 5: Dan Boneh , Matthew K. Franklin, Efficient Generation of Shared RSA Keys (Extended Abstract), Proceedings of the 17th Annual International Cryptology Conference on Advances in Cryptology, p.425-439, August 17-21, 1997
• 6: Christian Cachin , Klaus Kursawe , Anna Lysyanskaya , Reto Strobl, Asynchronous verifiable secret sharing and proactive cryptosystems, Proceedings of the 9th ACM conference on Computer and communications security, November 18-22, 2002, Washington, DC, USA [doi>10.1145/586110.586124]
• 7: R. Canetti, R. Gennaro, A. Herzberg, and D. Naor Proactive security: Long-term protection against break-ins. RSA CryptoBytes, 3(1):1--8, 1997.
• 8: R. Canetti, S. Halevi, and A. Herzberg. Maintaining authenticated communication in the presence of break-ins. Journal of Cryptology, 13(1):61--106, 2000.
• 9: Ran Canetti , Amir Herzberg, Maintaining Security in the Presence of Transient Faults, Proceedings of the 14th Annual International Cryptology Conference on Advances in Cryptology, p.425-438, August 21-25, 1994
• 10: Miguel Castro , Peter Druschel , Ayalvadi Ganesh , Antony Rowstron , Dan S. Wallach, Secure routing for structured peer-to-peer overlay networks, Proceedings of the 5th symposium on Operating systems design and implementation

  Due to copyright restrictions we are not able to make the PDFs for this conference available for downloading

  , December 09-11, 2002, Boston, Massachusetts [doi>10.1145/1060289.1060317]
• 11: B. Chor, S. Goldwasser, S. Micali, and B. Awerbuch. Verifiable secret sharing and achieving simultaneity in the presence of faults. In Proc. of the 26th IEEE Symp. on Foundations of Computer Science (FOCS), pages 383--395, 1986.
• 12: C.S. Chow and A. Herzberg. Network randomization protocol: A proactive pseudo-random generator. In Proc. of the 5th USENIX UNIX Security Symposium, pages 55--63, 1995.
• 13: S. Crosby and D. Wallach. Denial of service via algorithmic complexity attacks. In Usenix Security, 2003.
• 14: P. Diaconis and M. Shahshahani. Generating a random permutation with random transpositions. Z. Wahrscheinlichkeitstheorie verw. Gebiete, 57:159--179, 1981.
• 15: John R. Douceur, The Sybil Attack, Revised Papers from the First International Workshop on Peer-to-Peer Systems, p.251-260, March 07-08, 2002
• 16: Antony I. T. Rowstron , Peter Druschel, Pastry: Scalable, Decentralized Object Location, and Routing for Large-Scale Peer-to-Peer Systems, Proceedings of the IFIP/ACM International Conference on Distributed Systems Platforms Heidelberg, p.329-350, November 12-16, 2001
• 17: Yair Frankel , Peter Gemmell , Philip D. MacKenzie , Moti Yung, Proactive RSA, Proceedings of the 17th Annual International Cryptology Conference on Advances in Cryptology, p.440-454, August 17-21, 1997
• 18: Y. Frankel , P. Gemmell , P. D. MacKenzie , Moti Yung, Optimal-resilience proactive public-key cryptosystems, Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS '97), p.384, October 19-22, 1997
• 19: Rosario Gennaro , Yuval Ishai , Eyal Kushilevitz , Tal Rabin, The round complexity of verifiable secret sharing and secure multicast, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.580-589, July 2001, Hersonissos, Greece [doi>10.1145/380752.380853]
• 20: Rosario Gennaro , Stanisław Jarecki , Hugo Krawczyk , Tal Rabin, Robust threshold DSS signatures, Information and Computation, v.164 n.1, p.54-84, Jan. 10, 2001 [doi>10.1006/inco.2000.2881]
• 21: Rosario Gennaro , Michael O. Rabin , Tal Rabin, Simplified VSS and fast-track multiparty computations with applications to threshold cryptography, Proceedings of the seventeenth annual ACM symposium on Principles of distributed computing, p.101-111, June 28-July 02, 1998, Puerto Vallarta, Mexico [doi>10.1145/277697.277716]
• 22: Amir Herzberg , Stanislaw Jarecki , Hugo Krawczyk , Moti Yung, Proactive Secret Sharing Or: How to Cope With Perpetual Leakage, Proceedings of the 15th Annual International Cryptology Conference on Advances in Cryptology, p.339-352, August 27-31, 1995
• 23: Amir Herzberg , Markus Jakobsson , Stanislław Jarecki , Hugo Krawczyk , Moti Yung, Proactive public key and signature systems, Proceedings of the 4th ACM conference on Computer and communications security, p.100-110, April 01-04, 1997, Zurich, Switzerland [doi>10.1145/266420.266442]
• 24: U. Nadav and M. Naor. Fault tolerant storage in a dynamic environment. In Proc. of the 18th Annual Conference on Distributed Computing (DISC), 2004.
• 25: Moni Naor , Udi Wieder, Scalable and dynamic quorum systems, Proceedings of the twenty-second annual symposium on Principles of distributed computing, p.114-122, July 13-16, 2003, Boston, Massachusetts [doi>10.1145/872035.872052]
• 26: S. Nielson, S. Crosby, and D. Wallach. Kill the messenger: A taxonomy of rational attacks. In Proc. of the 4th International Workshop on Peer-to-Peer Systems (IPTPS), 2005.
• 27: Rafail Ostrovsky , Moti Yung, How to withstand mobile virus attacks (extended abstract), Proceedings of the tenth annual ACM symposium on Principles of distributed computing, p.51-59, August 19-21, 1991, Montreal, Quebec, Canada [doi>10.1145/112600.112605]
• 28: Tal Rabin, A Simplified Approach to Threshold and Proactive RSA, Proceedings of the 18th Annual International Cryptology Conference on Advances in Cryptology, p.89-104, August 23-27, 1998
• 29: Sylvia Ratnasamy , Paul Francis , Mark Handley , Richard Karp , Scott Schenker, A scalable content-addressable network, Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, p.161-172, August 2001, San Diego, California, United States
• 30: C. Scheideler. Probabilistic Methods for Coordination Problems. HNI-Verlagsschriftenreihe 78, University of Paderborn, 2000. See also http://www.cs.jhu.edu/~scheideler.
• 31: Emil Sit , Robert Morris, Security Considerations for Peer-to-Peer Distributed Hash Tables, Revised Papers from the First International Workshop on Peer-to-Peer Systems, p.261-269, March 07-08, 2002
• 32: Mudhakar Srivatsa , Ling Liu, Vulnerabilities and Security Threats in Structured Overlay Networks: A Quantitative Analysis, Proceedings of the 20th Annual Computer Security Applications Conference (ACSAC'04), p.252-261, December 06-10, 2004 [doi>10.1109/CSAC.2004.50]
• 33: Ion Stoica , Robert Morris , David Karger , M. Frans Kaashoek , Hari Balakrishnan, Chord: A scalable peer-to-peer lookup service for internet applications, Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, p.149-160, August 2001, San Diego, California, United States
• 34: Ben Y. Zhao , John D. Kubiatowicz , Anthony D. Joseph, Tapestry: An Infrastructure for Fault-tolerant Wide-area Location and, University of California at Berkeley, Berkeley, CA, 2001

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Routing and layout

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Network problems; Graph algorithms

General Terms:
Algorithms, Theory

Keywords:
join-leave attacks, proactive security, random mixing