GhostDB: querying visible and hidden data without leaks

ABSTRACT

Imagine that you have been entrusted with private data, such as corporate product information, sensitive government information, or symptom and treatment information about hospital patients. You may want to issue queries whose result will combine private and public data, but private data must not be revealed. GhostDB is an architecture and system to achieve this. You carry private data in a smart USB key (a large Flash persistent store combined with a tamper and snoop-resistant CPU and small RAM). When the key is plugged in, you can issue queries that link private and public data and be sure that the only information revealed to a potential spy is which queries you pose. Queries linking public and private data entail novel distributed processing techniques on extremely unequal devices (standard computer and smart USB key). This paper presents the basic framework to make this all work intuitively and efficiently.

REFERENCES

• 1: Agrawal, R., Kiernan, J., Srikant, R., Xu, Y., Hippocratic Databases. The International Conference on Very Large Databases: Pages 143--154, 2002.
• 2: Burton H. Bloom, Space/time trade-offs in hash coding with allowable errors, Communications of the ACM, v.13 n.7, p.422-426, July 1970 [doi>10.1145/362686.362692]
• 3: Cristiana Bolchini , Fabio Salice , Fabio A. Schreiber , Letizia Tanca, Logical and physical design issues for smart card databases, ACM Transactions on Information Systems (TOIS), v.21 n.3, p.254-285, July 2003 [doi>10.1145/858476.858478]
• 4: Kjell Bratbergsengen, Hashing Methods and Relational Algebra Operations, Proceedings of the 10th International Conference on Very Large Data Bases, p.323-333, August 27-31, 1984
• 5: Computer Security Institute, CSI/FBI Computer Crime and Security Survey, http://www.gocsi.com, 2006.
• 6: Ernesto Damiani , S. De Capitani Vimercati , Sushil Jajodia , Stefano Paraboschi , Pierangela Samarati, Balancing confidentiality and efficiency in untrusted relational DBMSs, Proceedings of the 10th ACM conference on Computer and communications security, October 27-30, 2003, Washington D.C., USA [doi>10.1145/948109.948124]
• 7: Desai, S., Netravali, A., Thompson, M., Carbon fibers as a novel material for high-performance microelectromechanical systems (MEMS), Journal of Micromechanics and Microengineering, 16, 7, (2006).
• 8: European Directive 95/46/EC, Protection of individuals with regard the processing of personal data, Official Journal L 281, 1995.
• 9: Laura M. Haas , Michael J. Carey , Miron Livny , Amit Shukla, Sing the truth about ad hoc join costs, The VLDB Journal — The International Journal on Very Large Data Bases, v.6 n.3, p.241-256, August 1997 [doi>10.1007/s007780050043]
• 10: Hakan Hacigümüş , Bala Iyer , Chen Li , Sharad Mehrotra, Executing SQL over encrypted data in the database-service-provider model, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564717]
• 11: Neil J. Henderson , Neil M. White , Pieter H. Hartel, iButton Enrolment and Verification Requirements for the Pressure Sequence Smartcard Biometric, Proceedings of the International Conference on Research in Smart Cards: Smart Card Programming and Security, p.124-134, September 19-21, 2001
• 12: IBM corporation, IBM Data Encryption for IMS and DB2 Databases v. 1.1, http://www-306.ibm.com/software/data/db2imstools/html/ibmdataencryp.html, 2003.
• 13: Lane, P., Oracle9i Data Warehousing Guide, Release 1 (9.0.1). Oracle Corporation, 2001.
• 14: Zhe Li , Kenneth A. Ross, Fast joins using join indices, The VLDB Journal — The International Journal on Very Large Data Bases, v.8 n.1, p.1-24, April 1999 [doi>10.1007/s007780050071]
• 15: Machanavajjhala, A., Kifer, D., Gehrke, J., Venkitasubramaniam, M., L-Diversity: Privacy beyond K-Anonymity. International Conference on Data Engineering (ICDE), 2006.
• 16: Mitzenmacher, M., Compressed Bloom Filters. ACM PODC: Pages 144--150, 2001.
• 17: Patrick O'Neil , Goetz Graefe, Multi-table joins through bitmapped join indices, ACM SIGMOD Record, v.24 n.3, p.8-11, Sept. 1995 [doi>10.1145/211990.212001]
• 18: Oracle Corporation. Oracle Database, Advanced Security Administrator's Guide, 10g Release 2 (10.2). Oracle documentation B14268-02, 2005.
• 19: Philippe Pucheral , Luc Bouganim , Patrick Valduriez , Christophe Bobineau, PicoDBMS: Scaling down database techniques for the smartcard, The VLDB Journal — The International Journal on Very Large Data Bases, v.10 n.2-3, p.120-132, September 2001
• 20: Praca, D., Next Generation Smart Card: New Features, New Architecture and System Integration, deliverable of the Inspired IST project, 2005.
• 21: Privacy Protection Study Commission, Personal Privacy in an Information Society, Chapter 15: The Citizen As Participant in Research and Statistical Studies. Report transmitted to President Jimmy Carter on July 12, 1977.
• 22: Sullivan, B., Privacy under attack, but does anybody care? MSNBC article, Oct. 17, 2006.
• 23: Latanya Sweeney, k-anonymity: a model for protecting privacy, International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems, v.10 n.5, p.557-570, October 2002 [doi>10.1142/S0218488502001648]
• 24: The Privacy Act, 5 U.S.C. § 552a, 1974. http://www.usdoj.gov/04foia/privstat.htm.
• 25: Patrick Valduriez, Join indices, ACM Transactions on Database Systems (TODS), v.12 n.2, p.218-246, June 1987 [doi>10.1145/22952.22955]
• 26: Vingralek, R., Gnatdb: A small-footprint, secure database system, International Conference on Very Large Databases (VLDB): Pages 884--893, 2002.
• 27: Andreas Weininger, Efficient execution of joins in a star schema, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564754]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.7 Database Administration
          Subjects: Security, integrity, and protection
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.1 Content Analysis and Indexing
          Subjects: Indexing methods

General Terms:
Design, Security

Keywords:
privacy, secure device, storage model