Abstract
We consider the problem of designing an efficient and robust distributed random number generator for peer-to-peer systems that is easy to implement and works even if all communication channels are public. A robust random number generator is crucial for avoiding adversarial join-leave attacks on peer-to-peer overlay networks. We show that our new generator together with a light-weight rule recently proposed in [4] for keeping peers well-distributed can keep various structured overlay networks in a robust state even under a constant fraction of adversarial peers.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
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
Aspnes, J., Shah, G.: Skip graphs. In: Proc. of the 14th ACM Symp. on Discrete Algorithms (SODA), pp. 384–393 (2003)
Awerbuch, B., Scheideler, C.: Group Spreading: A protocol for provably secure distributed name service. In: Proc. of the 31st International Colloquium on Automata, Languages and Programming (ICALP) (2004)
Awerbuch, B., Scheideler, C.: Robust distributed name service. In: Voelker, G.M., Shenker, S. (eds.) IPTPS 2004. LNCS, vol. 3279, pp. 237–249. Springer, Heidelberg (2005)
Awerbuch, B., Scheideler, C.: Towards a scalable and robust DHT. In: Proc. of the 18th ACM Symp. on Parallel Algorithms and Architectures (SPAA) (2006), See also, http://www14.in.tum.de/personen/scheideler
Ben-Or, M., Kelmer, B., Rabin, T.: Asynchronous secure computations with optimal resilience. In: Proc. of the 13th ACM Symp. on Principles of Distributed Computing (PODC), pp. 183–192 (1994)
Castro, M., Druschel, P., Ganesh, A., Rowstron, A., Wallach, D.: Security for structured peer-to-peer overlay networks. In: Proc. of the 5th Usenix Symp. on Operating Systems Design and Implementation (OSDI) (2002)
Castro, M., Liskov, B.: Practical Byzantine fault tolerance. In: Proc. of the 2nd Usenix Symp. on Operating Systems Design and Implementation (OSDI) (1999)
Crosby, S., Wallach, D.: Denial of service via algorithmic complexity attacks. In: Usenix Security (2003)
Douceur, J.R.: The sybil attack. In: Proc. of the 1st International Workshop on Peer-to-Peer Systems (IPTPS) (2002)
Fiat, A., Saia, J., Young, M.: Making Chord Robust to Byzantine Attacks. In: Brodal, G.S., Leonardi, S. (eds.) ESA 2005. LNCS, vol. 3669, pp. 803–814. Springer, Heidelberg (2005)
Goldreich, O.: Modern Cryptography, Probabilistic Proofs and Pseudorandomness. Algorithms and Combinatorics, vol. 17. Springer, Heidelberg (1998)
Halevi, S., Micali, S.: Practical and provably-secure commitment schemes from collision-free hashing. In: Koblitz, N. (ed.) CRYPTO 1996. LNCS, vol. 1109, pp. 201–215. Springer, Heidelberg (1996)
Karger, D., Lehman, E., Leighton, T., Levine, M., Lewin, D., Panigrahi, R.: Consistent hashing and random trees: Distributed caching protocols for relieving hot spots on the World Wide Web. In: 29th ACM Symp. on Theory of Computing (STOC), pp. 654–663 (1997)
King, V., Saia, J., Sanwalani, V., Vee, E.: Towards a secure and scalable computation in peer-to-peer networks. In: Proc. of the 47th IEEE Symp. on Foundations of Computer Science (FOCS) (2006)
Kuhn, F., Schmid, S., Wattenhofer, R.: A self-repairing peer-to-peer system resilient to dynamic adversarial churn. In: Castro, M., van Renesse, R. (eds.) IPTPS 2005. LNCS, vol. 3640, pp. 13–23. Springer, Heidelberg (2005)
Luby, M.: Pseudorandomness and Cryptographic Applications. Princeton University Press, Princeton (1996)
Naor, M.: Bit commitment using pseudorandomness. Journal of Cryptology 4(2), 151–158 (1991)
Naor, M., Wieder, U.: Novel architectures for P2P applications: the continuous-discrete approach. In: Proc. of the 15th ACM Symp. on Parallel Algorithms and Architectures (SPAA) (2003)
Nielson, S.J., Crosby, S.A., Wallach, D.S.: A taxonomy of rational attacks. In: Castro, M., van Renesse, R. (eds.) IPTPS 2005. LNCS, vol. 3640, pp. 36–46. Springer, Heidelberg (2005)
Plaxton, G., Rajaraman, R., Richa, A.W.: Accessing nearby copies of replicated objects in a distributed environment. In: Proc. of the 9th ACM Symp. on Parallel Algorithms and Architectures (SPAA), pp. 311–320 (1997)
Ramasamy, H.V., Cachin, C.: Parsimonious asynchronous byzantine-fault-tolerant atomic broadcast. In: Anderson, J.H., Prencipe, G., Wattenhofer, R. (eds.) OPODIS 2005. LNCS, vol. 3974, pp. 88–102. Springer, Heidelberg (2006)
Rhea, S., Geels, D., Roscoe, T., Kubiatowicz, J.: Handling churn in a DHT. In: USENIX Annual Technical Conference (2004)
Ritter, T.: RNG implementations: A literature survey, http://www.ciphersbyritter.com/RES/RNGENS.HTM
Saia, J., Fiat, A., Gribble, S.D., Karlin, A.R., Saroiu, S.: Dynamically fault-tolerant content addressable networks. In: Druschel, P., Kaashoek, M.F., Rowstron, A. (eds.) IPTPS 2002. LNCS, vol. 2429, p. 270. Springer, Heidelberg (2002)
Scheideler, C.: How to spread adversarial nodes? Rotate? In: Proc. of the 37th ACM Symp. on Theory of Computing (STOC), pp. 704–713 (2005)
Singh, A., Castro, M., Rowstron, A., Druschel, P.: Defending against Eclipse attacks on overlay networks. In: Proc. of the 11th ACM SIGOPS European Workshop (2004)
Sit, E., Morris, R.: Security considerations for peer-to-peer distributed hash tables. In: Druschel, P., Kaashoek, M.F., Rowstron, A. (eds.) IPTPS 2002. LNCS, vol. 2429, p. 261. Springer, Heidelberg (2002)
Srinathan, K., Rangan, C.P.: Efficient asynchronous secure multiparty distributed computation. In: Proc. of the 1st Int. Conference on Progress in Cryptology, pp. 117–129 (2000)
Srivatsa, M., Liu, L.: Vulnerabilities and security threats in structured overlay networks: A quantitative analysis. In: ACSAC (2004)
Stoica, I., Morris, R., Karger, D., Kaashoek, M.F., Balakrishnan, H.: Chord: A scalable peer-to-peer lookup service for Internet applications. In: Proc. of the ACM SIGCOMM 2001 (2001); See also, http://www.pdos.lcs.mit.edu/chord/
Viega, J.: Practical random number generation in software. In: Proc. of the 19th Annual Computer Security Applications Conference (2003)
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
Awerbuch, B., Scheideler, C. (2006). Robust Random Number Generation for Peer-to-Peer Systems. In: Shvartsman, M.M.A.A. (eds) Principles of Distributed Systems. OPODIS 2006. Lecture Notes in Computer Science, vol 4305. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11945529_20
Download citation
DOI: https://doi.org/10.1007/11945529_20
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-49990-9
Online ISBN: 978-3-540-49991-6
eBook Packages: Computer ScienceComputer Science (R0)