Obfuscated databases and group privacy

ABSTRACT

We investigate whether it is possible to encrypt a database and then give it away in such a form that users can still access it, but only in a restricted way. In contrast to conventional privacy mechanisms that aim to prevent any access to individual records, we aim to restrict the set of queries that can be feasibly evaluated on the encrypted database.We start with a simple form of database obfuscation which makes database records indistinguishable from lookup functions. The only feasible operation on an obfuscated record is to look up some attribute Y by supplying the value of another attribute X that appears in the same record (i.e., someone who does not know X cannot feasibly retrieve Y). We then (i) generalize our construction to conjunctions of equality tests on any attributes of the database, and (ii) achieve a new property we call group privacy. This property ensures that it is easy to retrieve individual records or small subsets of records from the encrypted database by identifying them precisely, but ``mass harvesting'' queries matching a large number of records are computationally infeasible.Our constructions are non-interactive. The database is transformed in such a way that all queries except those explicitly allowed by the privacy policy become computationally infeasible, i.e.,, our solutions do not rely on any access-control software or hardware.

REFERENCES

• 1: David Aucsmith, Tamper Resistant Software: An Implementation, Proceedings of the First International Workshop on Information Hiding, p.317-333, May 30-June 01, 1996
• 2: Boaz Barak , Oded Goldreich , Russell Impagliazzo , Steven Rudich , Amit Sahai , Salil P. Vadhan , Ke Yang, On the (Im)possibility of Obfuscating Programs, Proceedings of the 21st Annual International Cryptology Conference on Advances in Cryptology, p.1-18, August 19-23, 2001
• 3: D. Beaver, J. Feigenbaum, J. Kilian, and P. Rogaway. Locally random reductions: improvements and applications. J. Cryptology, 10:17--36, 1997.
• 4: D. Boneh, G. Di Crescenzo, R. Ostrovsky, and G. Persiano. Public key encryption with keyword search. In Proc. Advances in Cryptology - EUROCRYPT 2004, volume 3027 of LNCS, pages 506--522. Springer, 2004.
• 5: Ran Canetti, Towards Realizing Random Oracles: Hash Functions That Hide All Partial Information, Proceedings of the 17th Annual International Cryptology Conference on Advances in Cryptology, p.455-469, August 17-21, 1997
• 6: Ran Canetti , Daniele Micciancio , Omer Reingold, Perfectly one-way probabilistic hash functions (preliminary version), Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.131-140, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276721]
• 7: S. Chawla, C. Dwork, F. McSherry, A. Smith, and H. Wee. Towards privacy in public databases. In Proc. 2nd Theory of Cryptography Conference (TCC), volume 3378 of LNCS, pages 363--385. Springer, 2005.
• 8: Benny Chor , Eyal Kushilevitz , Oded Goldreich , Madhu Sudan, Private information retrieval, Journal of the ACM (JACM), v.45 n.6, p.965-981, Nov. 1998 [doi>10.1145/293347.293350]
• 9: Stanley Chow , Philip A. Eisen , Harold Johnson , Paul C. van Oorschot, White-Box Cryptography and an AES Implementation, Revised Papers from the 9th Annual International Workshop on Selected Areas in Cryptography, p.250-270, August 15-16, 2002
• 10: S. Chow, P. Eisen, H. Johnson, and P. van Oorschot. A white-box DES implementation for DRM applications. In ACM Digital Rights Management Workshop, volume 2696 of LNCS, pages 1--15. Springer, 2003.
• 11: Christian S. Collberg , Clark Thomborson, Watermarking, tamper-proffing, and obfuscation: tools for software protection, IEEE Transactions on Software Engineering, v.28 n.8, p.735-746, August 2002 [doi>10.1109/TSE.2002.1027797]
• 12: C. Collberg, C. Thomborson, and D. Low. A taxonomy of obfuscating transformations. Technical Report 148, Department of Computer Sciences, The University of Auckland, July 1997.
• 13: Christian Collberg , Clark Thomborson , Douglas Low, Manufacturing cheap, resilient, and stealthy opaque constructs, Proceedings of the 25th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.184-196, January 19-21, 1998, San Diego, California, United States [doi>10.1145/268946.268962]
• 14: D. Dean and A. Stubblefield. Using client puzzles to protect TLS. In Proc. 10th USENIX Security Symposium, pages 1--8. USENIX, 2001.
• 15: Yevgeniy Dodis , Adam Smith, Correcting errors without leaking partial information, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060688]
• 16: Cynthia Dwork , Moni Naor, Pricing via Processing or Combatting Junk Mail, Proceedings of the 12th Annual International Cryptology Conference on Advances in Cryptology, p.139-147, August 16-20, 1992
• 17: Matthew K. Franklin , Dahlia Malkhi, Auditable metering with lighweight security, Journal of Computer Security, v.6 n.4, p.237-255, July 1998
• 18: Yael Gertner , Yuval Ishai , Eyal Kushilevitz , Tal Malkin, Protecting data privacy in private information retrieval schemes, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.151-160, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276723]
• 19: Oded Goldreich , Rafail Ostrovsky, Software protection and simulation on oblivious RAMs, Journal of the ACM (JACM), v.43 n.3, p.431-473, May 1996 [doi>10.1145/233551.233553]
• 20: Y. Ishai, A. Sahai, and D. Wagner. Private circuits: securing hardware against probing attacks. In Proc. Advances in Cryptology - CRYPTO 2003, volume 2729 of LNCS, pages 463--481. Springer, 2003.
• 21: A. Juels and J. Brainard. Client puzzles: a cryptographic defense against connection depletion. In Proc. Network and Distributed System Security Symposium (NDSS), pages 151--165. The Internet Society, 1999.
• 22: B. Lynn, M. Prabhakaran, and A. Sahai. Positive results and techniques for obfuscation. In Proc. Advances in Cryptology - EUROCRYPT 2004, volume 3027 of LNCS, pages 20--39. Springer, 2004.
• 23: R. Rivest. Partial-match retrieval algorithms. SIAM Journal of Computing, 5(1):19--50, 1976.
• 24: Adi Shamir, How to share a secret, Communications of the ACM, v.22 n.11, p.612-613, Nov. 1979 [doi>10.1145/359168.359176]
• 25: Dawn Xiaodong Song , David Wagner , Adrian Perrig, Practical Techniques for Searches on Encrypted Data, Proceedings of the 2000 IEEE Symposium on Security and Privacy, p.44, May 14-17, 2000
• 26: XiaoFeng Wang , Michael K. Reiter, Defending Against Denial-of-Service Attacks with Puzzle Auctions, Proceedings of the 2003 IEEE Symposium on Security and Privacy, p.78, May 11-14, 2003
• 27: Hoeteck Wee, On obfuscating point functions, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060669]

INDEX TERMS

Primary Classification:
  E. Data
  E.3 DATA ENCRYPTION

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.7 Database Administration
          Subjects: Security, integrity, and protection

General Terms:
Security

Keywords:
database privacy, obfuscation