Abstract
We study a new model for data authentication over peer-to-peer (p2p) storage networks, where data items are stored, queried and authenticated in a totally decentralized fashion. The model captures the security requirements of emerging distributed computing applications. We present an efficient construction of a distributed Merkle tree (DMT), which realizes an authentication tree over a p2p network, thus extending a fundamental cryptographic technique to distributed environments. We show how our DMT can be used to design an authenticated distributed hash table that is secure against replay attacks and consistent with the update history. Our scheme is built on top of a broad class of existing p2p overlay networks and achieves generality by using only the basic functionality of object location. We use this scheme to design the first efficient distributed authenticated dictionary.
Research supported in part by IAM Technology, Inc., the National Science Foundation under grants IIS–0324846 and CCF–0311510, and the Institute for Information Infrastructure Protection (I3P) under an award from the Science and Technology Directorate at the Department of Homeland Security. Points of view or opinions in this document are those of the authors and do not represent the official position or policies of the U.S. Department of Homeland Security.
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
Anagnostopoulos, A., Goodrich, M.T., Tamassia, R.: Persistent authenticated dictionaries and their applications. In: Davida, G.I., Frankel, Y. (eds.) ISC 2001. LNCS, vol. 2200, pp. 379–393. Springer, Heidelberg (2001)
Aspnes, J., Shah, G.: Skip graphs. In: Proc. ACM-SIAM Symposium on Discrete Algorithms, pp. 384–393 (2003)
Castro, M., Druschel, P., Ganesh, A.J., Rowstron, A., Wallach, D.S.: Secure routing for structured p2p overlay networks. In: Proc. OSDI, pp. 299–314 (2002)
Dabek, F., Kaashoek, M.F., Karger, D., Morris, R., Stoica, I.: Wide-area cooperative storage with CFS. In: Proc. SOSP, pp. 202–215 (2001)
Devanbu, P., Gertz, M., Kwong, A., Martel, C., Nuckolls, G., Stubblebine, S.: Flexible authentication of XML documents. In: Proc. CCS, pp. 136–145 (2001)
Devanbu, P., Gertz, M., Martel, C., Stubblebine, S.G.: Authentic data publication over the Internet. Journal of Computer Security 11(3), 291–314 (2003)
Druschel, P., Rowstron, A.: Past: A large-scale, persistent peer-to-peer storage utility. In: Proc. HOTOS, p. 75 (2001)
Fiat, A., Saia, J.: Censorship resistant peer-to-peer content addressable networks. In: Proc. of Symposium on Discrete Algorithms, pp. 1–23 (2002)
Fu, K., Kaashoek, M.F., Mazieres, D.: Fast and secure distributed read-only file system. Computer Systems 20(1), 1–24 (2002)
Goodrich, M.T., Nelson, M.J., Sun, J.Z.: The rainbow skip graph: a fault-tolerant constant-degree distributed data structure. In: Proc. SODA, pp. 384–393 (2006)
Goodrich, M.T., Tamassia, R., Triandopoulos, N.: Authenticated data structures for graph and geometric searching. In: Joye, M. (ed.) CT-RSA 2003. LNCS, vol. 2612, pp. 295–313. Springer, Heidelberg (2003)
Hall, E., Julta, C.S.: Parallelizable authentication trees. In: Cryptology ePrint Archive (December 2002)
Harvey, N.J.A., Jones, M.B., Saroiu, S., Theimer, M., Wolman, A.: SkipNet: A scalable overlay network with practical locality properties. In: Proc. USENIX Symp. on Internet Technologies and Systems (2003)
Huebsch, R., Chun, B., Hellerstein, J., Loo, B., Maniatis, P., Roscoe, T., Shenker, S., Stoica, I., Yumerefendi, A.: The architecture of PIER: an internet-scale query processor. In: Proc. of CIDR, pp. 28–43 (2005)
Jagadish, H.V., Ooi, B.C., Vu, Q.H.: Baton: a balanced tree structure for peer-to-peer networks. In: Proc. VLDB, pp. 661–672 (2005)
Kaashoek, F., Karger, D.R.: Koorde: A simple degree-optimal distributed hash table. In: Kaashoek, M.F., Stoica, I. (eds.) IPTPS 2003. LNCS, vol. 2735, Springer, Heidelberg (2003)
Kocher, P.C.: On certificate revocation and validation. In: Hirschfeld, R. (ed.) FC 1998. LNCS, vol. 1465, pp. 172–177. Springer, Heidelberg (1998)
Li, F., Hadjieleftheriou, M., Kollios, G., Reyzin, L.: Dynamic authenticated index structures for outsourced databases. In: Proc. of ACM SIGMOD, pp. 121–132 (2006)
Li, J., Sollins, K., Lim, D.-Y.: Implementing aggregation and broadcast over distributed hash tables. ACM SIGCOMM Computer Communication Review 35(1), 81–92 (2005)
Manku, G.S., Bawa, M., Raghavan, P.: Symphony: Distributed hashing in a small world. In: Proc. USENIX Symp. on Internet Technologies and Systems, pp. 127–140 (2003)
Martel, C., Nuckolls, G., Devanbu, P., Gertz, M., Kwong, A., Stubblebine, S.G.: A general model for authenticated data structures. Algorithmica 39(1), 21–41 (2004)
Mehlhorn, K.: Data Structures and Algorithms 1: Sorting and Searching. EATCS Monographs on Theoretical Computer Science, vol. 1. Springer, Heidelberg (1984)
Merkle, R.C.: A certified digital signature. In: Brassard, G. (ed.) CRYPTO 1989. LNCS, vol. 435, pp. 218–238. Springer, Heidelberg (1990)
Miklau, G., Suciu, D.: Implementing a tamper-evident database system. In: Grumbach, S., Sui, L., Vianu, V. (eds.) ASIAN 2005. LNCS, vol. 3818, pp. 28–48. Springer, Heidelberg (2005)
Mykletun, E., Narasimha, M., Tsudik, G.: Authentication and integrity in outsourced databases. In: Proc. of Network and Distr. System Security (2004)
Naor, M., Nissim, K.: Certificate revocation and certificate update. In: Proc. of USENIX Security Symposium, pp. 217–228 (1998)
Naor, M., Wieder, U.: Novel architectures for p2p applications: the continuous-discrete approach. In: Proc. SPAA, pp. 50–59 (2002)
Nuckolls, G.: Verified query results from hybrid authentication trees. In: Proc. of Database Security, pp. 84–98 (2005)
Plaxton, C.G., Rajaraman, R., Richa, A.W.: Accessing nearby copies of replicated objects in a distributed environment. In: Proc. SPAA, pp. 311–320 (1997)
Ramabhadran, S., Hellerstein, J., Ratnasamy, S., Shenker, S.: Prefix hash tree - an indexing data structure over distributed hash tables. In: Proc. of ACM PODC, pp. 368–368 (2004)
Ratnasamy, S., Francis, P., Handley, M., Karp, R.M., Shenker, S.: A scalable content-addressable network. In: Proc. SIGCOMM, pp. 161–172 (2001)
Rhea, S., Godfrey, B., Karp, B., Kubiatowicz, J., Ratnasamy, S., Shenker, S., Stoica, I., Yu, H.: OpenDHT: A public DHT service and its uses. In: Proc. SIGCOMM, pp. 73–84 (2005)
Rowstron, A., Druschel, P.: Pastry: Scalable, decentralized object location, and routing for large-scale peer-to-peer systems. In: Guerraoui, R. (ed.) Middleware 2001. LNCS, vol. 2218, p. 329. Springer, Heidelberg (2001)
Rowstron, A., Kermarrec, A.-M., Castro, M., Druschel, P.: SCRIBE: The design of a large-scale event notification infrastructure. In: Crowcroft, J., Hofmann, M. (eds.) NGC 2001. LNCS, vol. 2233, pp. 30–43. Springer, Heidelberg (2001)
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, pp. 261–269. Springer, Heidelberg (2002)
Stoica, I., Morris, R., Karger, D., Kaashoek, F., Balakrishnan, H.: Chord: A scalable Peer-To-Peer lookup service for internet applications. In: Proc. SIGCOMM, pp. 149–160 (2001)
Tamassia, R.: Authenticated data structures. In: Di Battista, G., Zwick, U. (eds.) ESA 2003. LNCS, vol. 2832, pp. 2–5. Springer, Heidelberg (2003)
Tamassia, R., Triandopoulos, N.: Computational bounds on hierarchical data processing with applications to information security. In: Caires, L., Italiano, G.F., Monteiro, L., Palamidessi, C., Yung, M. (eds.) ICALP 2005. LNCS, vol. 3580, pp. 153–165. Springer, Heidelberg (2005)
Wallach, D.S.: A survey of peer-to-peer security issues. In: Okada, M., Pierce, B.C., Scedrov, A., Tokuda, H., Yonezawa, A. (eds.) ISSS 2002. LNCS, vol. 2609, pp. 42–57. Springer, Heidelberg (2003)
Zhao, B.Y., Kubiatowicz, J.D., Joseph, A.D.: Tapestry: An infrastructure for fault-tolerant wide-area location and routing. Technical Report UCB/CSD-01-1141, UC Berkeley (Apr. 2001)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2007 Springer Berlin Heidelberg
About this paper
Cite this paper
Tamassia, R., Triandopoulos, N. (2007). Efficient Content Authentication in Peer-to-Peer Networks . In: Katz, J., Yung, M. (eds) Applied Cryptography and Network Security. ACNS 2007. Lecture Notes in Computer Science, vol 4521. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-72738-5_23
Download citation
DOI: https://doi.org/10.1007/978-3-540-72738-5_23
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-72737-8
Online ISBN: 978-3-540-72738-5
eBook Packages: Computer ScienceComputer Science (R0)