APR-Quad: an update efficient authenticated dictionary for spatial data

ABSTRACT

We present an update-efficient authenticated dictionary towards the goal of providing public verification of outsourced dynamic geospatial data consolidated from a dynamic set of contributing sources. We introduce an on-disk authenticated bucket-based PR-quadtree for point and range queries over multiple attributes with minimal tree realignment upon updates. Our design minimizes cryptographic proof overhead using large, block-aligned tree nodes for high fanout and incremental cumulative hashing to consolidate neighboring elements required for verifying completeness. We introduce block-dependent indexing to reduce cryptographic recalculations required upon updates. Collectively, our design decisions result in an authenticated dictionary capable of efficiently incorporating individual updates or entire pre-existing data sets. We validate our approach with simulated data sets derived from experiences managing the Mississippi River floods of May 2011.

References

1. Bellare, M., et al. A new paradigm for collision-free hashing: Incrementality at reduced cost. In Eurocrypt97 (1997).
2. Belopotosky, D. Data mining helps uncover fraud in disaster relief. http://www.nationaljournal.com/, June 2006.
3. Boldyreva, A. Efficient threshold signature, multisignature and blind signature schemes based on the gap-diffie-hellman-group signature scheme. In Proceedings of PKC 2003 (2003).
4. Chen, S., et al. Fractal prefetching B+-trees: optimizing both cache and disk performance. In SIGMOD International Conference on Management of Data (2002), ACM Press.
5. Cheng, W., et al. Authenticating multi-dimensional query results in data publishing. In DBSec (2006).
6. Devanbu, P. T., et al. Authentic third-party data publication. In Annual Working Conference on Database Security (2001).
7. Goh, E., et al. Sirius: Securing remote untrusted storage. In Network and Distributed Systems Security Symposium (2003).
8. Goodrich, M. T., et al. Authenticated dictionaries for fresh attribute credentials. In 1st international conference on Trust management (2003).
9. Hacigumus, H., et al. Providing database as a service. In 18th International Conference on Data Engineering (2002), ICDE '02.
10. Hu, L., et al. Verifying spatial queries using voronoi neighbors. In 18th SIGSPATIAL International Conference on Advances in Geographic Information Systems (2010).
11. Li, F., et al. Dynamic authenticated index structures for outsourced databases. In SIGMOD (2006), SIGMOD.
12. Li, F., et al. Authenticated index structures for aggregation queries. ACM Trans. Inf. Syst. Secur. 13 (2010).
13. Lomet, D. The evolution of effective B-tree: Page organization and techniques: A personal account. In ACM SIGMOD Record (Sept. 2001).
14. Merkle, R. A certified digital signature. Advances in Cryptology 435 (1990).
15. Mouratidis, K., Sacharidis, D., and Pang, H. Partially materialized digest scheme: an efficient verification method for outsourced databases. The VLDB Journal 18, 1 (2009), 363--381.
16. Naor, M., and Nissim, K. Certificate revocation and certificate update. Journal on Selected Areas in Communications 18, 4 (Apr. 1999).
17. Narasimha, M., and Tsudik, G. Authentication of outsourced databases using signature aggregation and chaining. In Database Systems for Advanced Applications (2006).
18. Nelson, R. C., and Samet, H. A consistent hierarchical representation for vector data. SIGGRAPH Comput. Graph. 20 (August 1986).
19. Nuckolls, G., et al. Certifying data from multiple sources {extended abstract}. In ACM Conference on Electronic Commerce (2003).
20. Papadopoulos, S., et al. Continuous spatial authentication. In Symposium on Advances in Spatial and Temporal Databases (2009).
21. Samet, H. Foundations of Multidimensional and Metric Data Structures. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 2005.
22. Ware, J. Geospatial data fusion: Training gis for disaster relief operations. In National Geospatial Intelligence School (2009).
23. Yang, Y., et al. Authenticated join processing in outsourced databases. In SIGMOD international conference on Management of data (2009).
24. Yang, Y., Papadopoulos, S., Papadias, D., and Kollios, G. Spatial outsourcing for location-based services. In ICDE (2008).
25. Yang, Y., Papadopoulos, S., Papadias, D., and Kollios, G. Authenticated indexing for outsourced spatial databases. The VLDB Journal 18 (June 2009), 631--648.
26. Yumerefendi, A. R., and Chase, J. S. Strong accountability for network storage. Transactions on Storage (2007).

Index Terms

• Human-centered computing

  • Visualization

    • Visualization application domains

      • Geographic visualization

• Information systems

  • Information systems applications

    • Spatial-temporal systems

• Security and privacy

  • Database and storage security

• Social and professional topics

  • Computing / technology policy

    • Computer crime

• Theory of computation

  • Theory and algorithms for application domains

    • Database theory

      • Theory of database privacy and security